POJ 3194 Equidivisions

問題

nxnのマスに1～nまでの数字がn個ずつ割り振られている。同じ数字が割り振られているマスがすべて4-連結しているか判定せよ。

入力形式が少しわかりにくくて、各テストケースのi行目が数字iを持つマスのy座標、x座標を連続で表している。テストケースはn-1行目までしかなく、nの数字を持つマスは1～n-1行目までに出てこないマスという考え方。

やりかた

単純にconnected component labelingして、あるラベルの連結している数を数えてきちんとn個になっているか調べればいい。

以下ソース。

int N;
int f[101][101];
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

void rec(int y, int x, int idx){
  f[y][x] = -1;
  for(int i = 0; i < 4; i++){
    int ny = y + dy[i], nx = x + dx[i];
    if(0 <= nx && nx < N && 0 <= ny && ny < N && 
       f[ny][nx] == idx)
      rec(ny, nx, idx);
  }
}
 
int main(int argc, char **argv){
  while(cin >> N, N){
    memset(f, -1, sizeof(f));
    for(int i = 0; i < N - 1; i++){
      for(int j = 0; j < N; j++){
	int y, x; cin >> y >> x;
	f[y - 1][x - 1] = i;
      }
    }

    for(int i = 0; i < N * N; i++)
      if(f[i / N][i % N] == -1) f[i / N][i % N] = N - 1;

    for(int i = 0; i < N; i++){
      for(int y = 0; y < N; y++)
	for(int x = 0; x < N; x++)
	  if(f[y][x] == i){
	    rec(y, x, i);
	    goto L1;
	  }
    L1:;
    }
    bool good = true;
    for(int y = 0; y < N; y++)
      for(int x = 0; x < N; x++)
	if(f[y][x] != -1) good = false;
    cout << (good ? "good" : "wrong") << endl;
  }
  return 0;
}