bfs 练习题,简单bfs
题意:给一块地图,找出油田的块的数量,这里要考虑油田的八个方向,上下左右(左右)上(左右)下,存在则可以并在一起。@是油田,*是土地,m是行,n是列。
解题思路:用一个二维数组表示8个方向,然后bfs即可。
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std; const int M = ;
char map[M][M];int m,n;
int res;
struct Oil
{
int x,y;
};
queue <Oil> oil;
int dire[][] = {{-,},{,},{,},{,-},{,},{-,-},{,-},{-,}}; //方向
void bfs()
{
while (!oil.empty())
{
Oil oo = oil.front();
oil.pop();
int dx = oo.x;
int dy = oo.y;
for (int i = ; i < ; i++)
{
int x = dx+dire[i][];
int y = dy+dire[i][];
if (x >= && x < m && y < n && y >= && map[x][y] == '@')
{
map[x][y] = '*';
Oil o;
o.x = x;
o.y = y;
oil.push(o);
}
}
}
}
int main()
{
while (cin >> m >> n && m)
{
res = ;
memset(visited,,sizeof (visited));
for (int i = ;i < m;i++)
for (int j = ;j < n;j++)
cin >> map[i][j];
for (int j = ; j < m; j++)
{
for (int k = ; k < n; k++)
{
if (map[j][k] == '@')
{
map[j][k] = '*';
Oil oo;
oo.x = j;
oo.y = k;
oil.push(oo);
res++;
bfs();
}
}
}
cout << res << endl;
}
return ;
}