• 题目描述：
  • 在一个被分成n*n个格子的平原上，有一些格子有铁矿，两格铁矿如果相邻那么就认为他们属于同一个矿床，每个矿床都包含一个或更多个铁矿，问一共有几个矿床。
    两个格子只要有公共边或公共点就算相邻。
  • 输入：第一行为一个正整数n，n<=1000 接下来有n行，每行有n个字符，表示平原的对应位置有没有铁矿，*代表没有，#代表有。
  • 输出：矿床个数
• 实例：
  • 输入：

6
####
####
##**
#**
###
**

• 输出：2
  • 总结
• 本人采用递归遍历的方法暴力求解，应该有更好的解决办法

include

using namespace std;
int n;
int* d;
//递归遍历
void traverse(int i, int j)
{
if (d[i][j] == 0) return;
d[i][j] = 0;
//判断上下左右和对角处有无矿产
if (i + 1 < n && d[i + 1][j] == 1) traverse(i + 1, j);
if (j + 1 < n && d[i][j + 1] == 1) traverse(i, j + 1);
if (i - 1 >= 0 && d[i - 1][j] == 1) traverse(i - 1, j);
if (j - 1 >= 0 && d[i][j - 1] == 1) traverse(i, j - 1);
if (i + 1 < n && j + 1 < n && d[i + 1][j + 1] == 1) traverse(i + 1, j + 1);
if (i - 1 >= 0 && j + 1 < n && d[i - 1][j + 1] == 1) traverse(i - 1, j + 1);
if (i - 1 >= 0 && j - 1 >= 0 && d[i - 1][j - 1] == 1) traverse(i - 1, j - 1);
if (i + 1 < n && j - 1 >= 0 && d[i + 1][j - 1] == 1) traverse(i + 1, j - 1);
}
int main()
{
char ch;
int count = 0;
scanf(“%d”, &n);

d = new int [n];
for (int i = 0; i < n; i++) d[i] = new int[n];

for (int i = 0; i < n n; i++)
{
scanf(“%c”, &ch);
if (ch == ‘#’) d[i / n][i % n] = 1;
else if (ch == ‘‘) d[i / n][i % n] = 0;
else i—;
}

for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (d[i][j] == 1) count++;
traverse(i, j);
}
}

cout << count << endl;
return 0;
}