JOI 春合宿 2008-day1 Sheet

問題文 : 色紙

解法 :

各矩形のとりうる領域の最大値を計算し, その上にある別の色紙から自分に向かった辺をはったグラフを考える. このトポロジカル順序が答えとなる.
計算量は, 矩形の操作にO(NWH) 時間, トポロジカルソートにO(N) 時間で, 全体としてO(NWH) 時間となる.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> ord;
vector<int> G[1024];
bool vis[1024];

void dfs(int v)
{
	vis[v] = true;
	for (int i = 0; i < G[v].size(); i++)
		if (!vis[G[v][i]]) dfs(G[v][i]);
	ord.push_back(v);
}

int field[128][128];
int posx[1024][2], posy[1024][2];

int main()
{
	int N, W, H;
	scanf("%d %d %d", &N, &W, &H);
	
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			scanf("%d", &field[i][j]); --field[i][j];
		}
	}
	
	memset(posx, -1, sizeof(posx)); memset(posy, -1, sizeof(posy));
	
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			if (~field[i][j]){
				posx[field[i][j]][0] = min(~posx[field[i][j]][0] ? posx[field[i][j]][0] : 999999, j);
				posy[field[i][j]][0] = min(~posy[field[i][j]][0] ? posy[field[i][j]][0] : 999999, i);
				posx[field[i][j]][1] = max(posx[field[i][j]][1], j);
				posy[field[i][j]][1] = max(posy[field[i][j]][1], i);
			}
		}
	}
	
	int par[1024];
	memset(par, -1, sizeof(par));
	for (int i = 0; i < N; i++){
		if (~posx[i][0])
			for (int y = posy[i][0]; y <= posy[i][1]; y++)
				for (int x = posx[i][0]; x <= posx[i][1]; x++)
					if (~field[y][x] && field[y][x] != i){
						G[field[y][x]].push_back(i); par[i] = field[y][x];
					}
	}
	
	for (int i = 0; i < N; i++)
		if (!vis[i] && par[i] == -1) dfs(i);
	
	for (int i = 0; i < N; i++)
		printf("%d%c", ord[i] + 1, i == N - 1 ? '\n' : ' ');
		
	return (0);
}