题意分析

给定一个 $n \times n$ 的方格阵列，要求将其划分为 $n$ 个集合，每个集合包含恰好 $n$ 个格子，并且每个集合的所有格子必须构成一个连通区域（即任意两个格子可以通过相邻边连接）。题目要求判断给定的划分是否满足这些条件。

• 输入：
  • 第一行是 $n$（$0 < n < 100$），表示方格的大小。
  • 接下来的 $n-1$ 行，每行给出若干个坐标对 $(a_1, a_2), (a_3, a_4), \dots$，表示这些格子属于同一个集合。
  • 最后一个集合由所有未被提及的格子组成。
• 输出：
  • 如果划分是“好的”（每个集合连通），输出 good，否则输出 wrong。

解题思路

1. 数据存储：

   • 使用一个 $n \times n$ 的二维数组 grid 记录每个格子所属的集合编号（$1$ 到 $n$）。
   • 未被前 $n-1$ 行提及的格子自动归为第 $n$ 个集合。

2. 连通性检查：

   • 对于每个集合 $k$（$1 \leq k \leq n$），需要检查其所有格子是否构成一个连通区域。
   • 可以采用 BFS（广度优先搜索） 或 DFS（深度优先搜索） 来检查连通性：
     • 从该集合的任意一个格子出发，遍历所有相邻的格子（上下左右），并标记访问过的格子。
     • 如果遍历结束后，所有属于该集合的格子都被访问过，则该集合是连通的；否则不连通。

3. 算法流程：

   • 读取输入并填充 grid。
   • 对于每个集合 $k$：
     • 找到该集合的任意一个格子作为起点。
     • 使用 BFS/DFS 遍历所有属于 $k$ 的格子。
     • 如果遍历的格子数不等于 $n$，说明该集合不连通，直接判定为 wrong。
   • 如果所有集合均连通，输出 good，否则输出 wrong。

标程

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>

using namespace std;

const int dr[] = {0, 0, 1, -1};
const int dc[] = {1, -1, 0, 0};
const int L = sizeof dr / sizeof dr[0];

const int N = 100;
int n, g[N][N], vis[N][N];
char s[1024];

int dfs(int row, int col)
{
	vis[row][col] = 1;
	int sum = 1;
	for (int i = 0; i < L; i++) {
		int nextrow = row + dr[i];
		int nextcol = col + dc[i];
		if(0 <= nextrow && nextrow < n && 0 <= nextcol && nextcol < n &&
			vis[nextrow][nextcol] == 0 && g[nextrow][nextcol] == g[row][col])
			sum += dfs(nextrow, nextcol);
	}
	
	return sum;
}

int main()
{
	while (scanf("%d", &n) == 1 && n) {
		getchar();
		
		memset(g, 0, sizeof g);
		for (int i = 1; i < n; i++) {
			cin.getline(s, sizeof(s));
			int len = strlen(s);
			for (int j = 0; j < len;) {
				int r = 0, c = 0;
				while (j < len && !isdigit(s[j])) j++;
				if (j >= len) break;
				while (j < len && isdigit(s[j]))
					r = r * 10 + s[j++] - '0';
				while (j < len && !isdigit(s[j])) j++;
				while (j < len && isdigit(s[j]))
					c = c * 10 + s[j++] - '0';
				g[r - 1][c - 1] = i;
			}
		}
		
		memset(vis, 0, sizeof vis);
		int flag = 1;
		for (int i = 0; flag && i < n; i++)
			for (int j = 0; j < n; j++)
				if (vis[i][j] == 0) {
					if (dfs(i, j) != n) {
						flag = 0;
						break;
					}
				}
		
		puts(flag ? "good" : "wrong");
	}
	
	return 0;
}