UVa 657 The die is cast

題意：
　　定義上下左右如果有一樣的符號，這些符號為connected。
　　分辨骰子某一面的點數，以'*'圍起來的面積代表那是骰子的某一面，在那裡面要計算有幾個點數，而且如果有多個'X'是connected，只能算作一個點數，例如sample input裡面左上為2，右上為1(因為'X'是connected)，左下為2，右下為4。

想法：
　　當碰到'*'的時候，代表有一塊區域，進入DFS_pixel走遍該區域，每走到一個點就將'*'變成'.'避免重複走過，如果碰到'X'，一樣代表有一塊X區域，計數器+1，並進入DFS_X走遍該區域，並將走到的點從'X'轉為'*'。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	char pic[51][51];
	int w, h;
	void DFS_X(int, int);
	void DFS_pixel (int i, int j, int &dots)
	{
	if (pic[i][j] == 'X') {
	dots++;
	DFS_X(i, j);
	}
	pic[i][j] = '.';
	if (i+1 < h && pic[i+1][j] != '.') DFS_pixel(i+1, j, dots);
	if (i-1 >=0 && pic[i-1][j] != '.') DFS_pixel(i-1, j, dots);
	if (j+1 < w && pic[i][j+1] != '.') DFS_pixel(i, j+1, dots);
	if (j-1 >=0 && pic[i][j-1] != '.') DFS_pixel(i, j-1, dots);
	}
	void DFS_X (int i, int j)
	{
	pic[i][j] = '*';
	if (i+1 < h && pic[i+1][j] == 'X') DFS_X(i+1, j);
	if (i-1 >=0 && pic[i-1][j] == 'X') DFS_X(i-1, j);
	if (j+1 < w && pic[i][j+1] == 'X') DFS_X(i, j+1);
	if (j-1 >=0 && pic[i][j-1] == 'X') DFS_X(i, j-1);
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d%d", &w, &h)){
	if (!w && !h) break;
	getchar();
	for (int i = 0; i < h; i++)
	gets(pic[i]);
	int ans[100] = {0}, nOfans = 0;
	for (int i = 0; i < h; i++)
	for (int j = 0; j < w; j++)
	if (pic[i][j] == '*'){
	DFS_pixel(i, j, ans[nOfans]);
	nOfans++;
	}
	sort(ans, ans + nOfans);
	printf("Throw %d\n", Case++);
	for (int i = 0; i < nOfans; i++){
	if (i) printf(" ");
	printf("%d", ans[i]);
	}
	printf("\n\n");
	}
	return 0;
	}

view raw [UVa] 657 The die is cast.cpp hosted with ❤ by GitHub