HDU 1241 Oil Deposits

题目如下：

在第一次植物僵尸世界大战中，植物国的黑玫瑰王子使用了植物国的超超超超级无敌禁术-----”BUG”,开启了异次元的大门，在一位超超超超...级**的指挥官”辅助器”带领下，打败了僵尸王国，但是也因此植物国大伤元气，无法再得到异次元的帮助。 过了10000年后，僵尸国王子为了国家的荣誉和发扬祖先的”诺克萨斯”精神，打算采取”闪电战”战术，一举歼灭植物国的战略要塞，吹起第二次植物僵尸世界大战的号角，但是僵尸王子需要知道植物国现在有几个战略要塞，才能采取进一步措施，于是开始研究植物国的军事图。

因为僵尸国卫星技术先进，该军事图十分清楚明了，是一个二维的电子网格图，图中只有黑色和白色，只要图中的白色方块外一圈的八个方块中有白色方块，说明它们属于同一个战略要塞。

Input

多组输入（m = 0结束输入）。

军事图是mn的二维图，图中”@”表示白色，””表示黑色。

第一行包含m,n（1<=n,m<=100）,

接下来m行，每行n个字符。

Output

对于每组输入，输出植物国的战略要塞数量。

Sample Input

1 1

*

3 5

@@*

@

@@*

1 8

@@***@

5 5

****@

@@@

*@**@

@@@*@

@@**@

0 0

Sample Output

0

1

2

2

解题思路：

这题是一道dfs的经典题目，详细思路就不说了。详情见Lake Counting笔记。

笔记：https://www.cnblogs.com/gao79135/p/13979047.html

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int m, n;
char Graph[100][100];
int Count = 0;                    //代表要塞数量
void dfs(int x, int y);           //代表进行dfs的函数


void dfs(int x, int y)
{
	int movex, movey;
	int i, j;
	Graph[x][y] = ‘*‘;            //把已经遍历过的‘@‘变成‘*‘,以免重复遍历
	for (i = -1; i <= 1; i++)
	{
		for (j = -1; j <= 1; j++) //进行八个方向的遍历
		{
			movex = x + i;        //进行移动
			movey = y + j; 
			if (movex >= 0 && movex < m && movey >= 0 && movey < n && Graph[movex][movey] == ‘@‘)
			{
				dfs(movex, movey);   //继续向下遍历
			}
		}
	}
}

int main()
{
	int i, j;
	while (scanf("%d %d", &m, &n) != EOF)
	{
		if (m == 0 && n == 0)
		{
			return 0;
		}
		for (i = 0; i < m; i++)
		{
			for (j = 0; j < n; j++)
			{
				cin >> Graph[i][j];
			}
		}
		for (i = 0; i < m; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (Graph[i][j] == ‘@‘)
				{
					dfs(i, j);
					Count++;
				}
			}
		}
		cout << Count << endl;
		Count = 0;
	}

}

原文：https://www.cnblogs.com/gao79135/p/14085526.html