UVa 352 The Seasonal War

題意：
　　要確認畫面中有幾隻Eagles，每個pixel如果是'1'代表為一隻Eagles，但上下左右(包含斜角共8個方向)相連的'1'只能算是同一隻。

想法：
　　使用DFS找'1'有幾個區域。

	#include <cstdio>
	using namespace std;
	char image[30][30];
	void DFS(int &n, int i, int j)
	{
	image[i][j] = '0';
	if (i-1 >= 0 && image[i-1][j] == '1') DFS(n, i-1, j);
	if (i+1 < n && image[i+1][j] == '1') DFS(n, i+1, j);
	if (j-1 >= 0 && image[i][j-1] == '1') DFS(n, i, j-1);
	if (j+1 < n && image[i][j+1] == '1') DFS(n, i, j+1);
	if (i-1 >= 0 && j-1 >= 0 && image[i-1][j-1] == '1') DFS(n, i-1, j-1);
	if (i-1 >= 0 && j+1 < n && image[i-1][j+1] == '1') DFS(n, i-1, j+1);
	if (i+1 < n && j-1 >= 0 && image[i+1][j-1] == '1') DFS(n, i+1, j-1);
	if (i+1 < n && j+1 < n && image[i+1][j+1] == '1') DFS(n, i+1, j+1);
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int n,Case = 1;
	while (scanf("%d", &n) != EOF){
	getchar();
	for (int i = 0; i < n; ++i)
	gets(image[i]);
	int num = 0;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (image[i][j] == '1'){
	DFS(n, i, j);
	++num;
	}
	printf("Image number %d contains %d war eagles.\n", Case++, num);
	}
	return 0;
	}

view raw [UVa] 352 The Seasonal War.cpp hosted with ❤ by GitHub