UVa 657 - The die is cast 解题报告

题目链接：http://uva.onlinejudge.org/external/6/657.html

题目分析

这题看过去不难想到是用图的遍历来做，不过比较麻烦的是，要搜“X”时范围并不一定是正置的矩形，无法直接用两重循环来遍历。想了一会儿，觉得可以用 DFS 嵌套 DFS。为了方便，子勤用了两个数组（vis 和 searched）来标记已访问。其实可以把标记已访问的数组改成 int 型，这样可以合并到同一个数组。

输出前要进行排序，这里用了快排。由于数组的值只有 0～6 之间的整数，其实也可以用计数排序来做。不过，实测运行时间差距不大，可能是数据量比较小吧。

提交后 WA 了几次，改了几次之后发现原因是，在 search() 中只需要向“上下左右”四个方向扩展就可以了，而我起初对八个方向进行了扩展，所以 WA 掉了。改回来后终于 AC 了。

---

解答

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 60;
char bmp[MAXN][MAXN];
bool vis[MAXN][MAXN];
bool searched[MAXN][MAXN];

// 把整个点标记已访问
void dot_dfs(int x, int y)
{
	if (bmp[x][y] != 'X' or vis[x][y]) return;

	vis[x][y] = searched[x][y] = true;
	dot_dfs(x-1, y);	// 上
	dot_dfs(x, y-1);	// 左
	dot_dfs(x+1, y);	// 下
	dot_dfs(x, y+1);	// 右
}

int cnt;	// 计数
// DFS 对骰面上的点计数，结果为 cnt
void search(int x, int y)
{
	// 仅在有效区域内搜索
	if (bmp[x][y] == '.' or searched[x][y] or vis[x][y]) return;

	if (bmp[x][y] == 'X' and !vis[x][y]) {	// 到达点上
		++cnt;
		dot_dfs(x, y);
	}

	searched[x][y] = true;
	search(x-1, y);	// 上
	search(x, y-1);	// 左
	search(x+1, y);	// 下
	search(x, y+1);	// 右
}

int main()
{
	for (int i = 1; ; ++i) {
		int w, h;
		scanf("%d%d", &w, &h);
		if (!w and !h) break;

		memset(bmp, '.', sizeof(bmp));
		memset(vis, false, sizeof(vis));
		memset(searched, false, sizeof(searched));
		// 输入
		// 下标从 1 开始，周围套上一层 “.”，以简化边界处理
		for (int j = 1; j <= h; j++) {
			scanf("%s", bmp[j] + 1);
			bmp[j][w+1] = '.';
		}

		vector<int> ans;

		for (int j = 1; j <= h; j++)
			for (int k = 1; k <= w; k++)
				if (bmp[j][k] != '.' and !searched[j][k]) {	// 到达骰面上
					cnt = 0;
					search(j, k);
					if (cnt > 0 and cnt < 7)	// 忽略非法结果
						ans.push_back(cnt);
				}

		sort(ans.begin(), ans.end());

		// 输出
		printf("Throw %d\n", i);
		for (vector<int>::iterator j = ans.begin(); j != ans.end(); ++j) {
			if (j != ans.begin()) putchar(' ');	// 行末输出无空格
			printf("%d", *j);
		}
		printf("\n\n");
	}
	return 0;
}