首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BFS练习-POJ.2386

BFS练习-POJ.2386

作者头像
Enterprise_
发布2019-02-21 17:40:19
4050
发布2019-02-21 17:40:19
举报
文章被收录于专栏:小L的魔法馆小L的魔法馆

Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 35122 Accepted: 17437 Description

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John’s field, determine how many ponds he has. Input

  • Line 1: Two space-separated integers: N and M
  • Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them. Output
  • Line 1: The number of ponds in Farmer John’s field. Sample Input

10 12 W……..WW. .WWW…..WWW ….WW…WW. ………WW. ………W.. ..W……W.. .W.W…..WW. W.W.W…..W. .W.W……W. ..W…….W. Sample Output

3 Hint

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

我的理解是每一次BFS之后一个水洼就都被替换成’W’,当不存在’W’的时候,说明没有水洼了,那么BFS的次数就是水洼的数目,每个点只扫描一次。

#include<iostream>
#include<queue>
#define N 110                               //比题目指定的N范围大一点
#define M 110
using namespace std;

typedef pair<int, int> point;               //这个时候写pair比结构体要方便一点
int res = 0;                                //符合要求的水洼数目
char maze[N][M];                            //记录整个地图
void BFS(int x,int y)                       
{
    queue<point>que;                        //建立队列
    point current;                          //记录当前的点的信息
    int i, j, dx, dy, dir_1, dir_2;
    for (i = 0; i < x; i++)
    {
        for (j = 0; j < y; j++)
        {
            if (maze[i][j] == 'W')          //如果当前这个点是积水
            {
                que.push(point(i,j));       //就加入队列
                maze[i][j] = '.';           //标记已经搜索过了这个点
                while (!que.empty())        //判断队列是否为空
                {
                    current = que.front();  //取出队首元素
                    que.pop();              //弹出第一个元素,不返回
                    for (dir_1 = -1; dir_1 <= 1; dir_1++)           //8个方向的遍历
                    {
                        for (dir_2 = -1; dir_2 <= 1; dir_2++)
                        {
                            dx = current.first + dir_1, dy = current.second + dir_2;            //坐标的变化
                            if (dx >= 0 && dx < x&&dy >= 0 && dy < y&&maze[dx][dy] != '.')      //判断是否这个点合法
                            {   
                                que.push(point(dx, dy));                                        //合法则加入队列
                                maze[dx][dy] = '.';                                             //标记这个点已经搜索过了
                            }
                        }
                    }
                }
                res++;                                                                          //水洼数目+1
            }
        }
    }
}

void solve()
{
    int k = 0, x, y;
    cin >> x >> y;
    for (k = 0; k < x; k++)
    {
        cin >> maze[k];
    }
    BFS(x,y);
    cout << res << endl;
}
int main(void)
{
    solve();
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年06月24日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档