题目
源地址:
http://poj.org/problem?id=1562
理解
使用DFS搜索石油所在的区块。
代码
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
using namespace std;
char map[100][100];
int vis[100][100];
int m, n;
int op[8][2] = { { -1, -1}, { -1, 0}, {1, 0}, {0, 1}, {1, 1}, { -1, 1}, {1, -1}, {0, -1} };
void search(int x, int y)
{
vis[x][y] = -1;
for (int i = 0; i < 8; i++)
if ((x + op[i][0] >= 0) && (x + op[i][0] < m) && (y + op[i][1] >= 0) && (y + op[i][1] < n) && (vis[x + op[i][0]][y + op[i][1]] != -1) && map[x + op[i][0]][y + op[i][1]] == '@')
search(x + op[i][0], y + op[i][1]);
}
int main(int argc, char const *argv[])
{
int i, j, sum;
while (scanf("%d %d", &m, &n) && m)
{
sum = 0;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
cin >> map[i][j];
memset(vis, 0, sizeof(vis));
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
if (vis[i][j] != -1 && map[i][j] == '@')
{
sum++;
search(i, j);
}
printf("%d\n", sum);
}
system("pause");
return 0;
}
更新日志
- 2014年08月12日 已AC。