POJ 3620 避开湖泊

【题目链接】

广度优先搜索基本模型

while (head<tail)
{
    for (遍历四个方向)
    { 
        tx=预测下一步的横坐标 
        ty=预测下一步的纵坐标 
        if (越界)
        continue;
        if (这个点可以走&&这个点没有被标记)
        {
            将这个点加入到que中
            并标记这个点 
        }
    }
    由于这个点的四个方向都遍历完了,
    将这个点从队列中删除 
}

AC代码

/* input 3 4 5 3 2 2 2 3 1 2 3 1 1 output 4 */
#include<iostream>
#include<cstring>
using namespace std;
typedef struct
{
    int x;
    int y;
}Node;
int main()
{
    int next[][2]={1,0,0,1,-1,0,0,-1};
    int n,m,k,a,b,max=0;
    cin>>n>>m>>k;
    Node que[10005];
    int map[105][105],book[105][105];
    memset(map,0,sizeof(map));
    memset(book,0,sizeof(book));
    for (int i=0;i<k;i++)
    {
        cin>>a>>b;
        map[a][b]=1;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (map[i][j]==1)
            {
                int tx,ty,head=0,tail=0;
                que[tail].x=i;
                que[tail++].y=j;
                book[i][j]=1;
                while (head<tail)
                {
                    for (int k=0;k<4;k++)
                    {
                        tx=que[head].x+next[k][0];
                        ty=que[head].y+next[k][1];
                        if (tx<1||tx>n||ty<1||ty>m)
                        continue;
                        if (map[tx][ty]==1&&book[tx][ty]==0)
                        {
                            que[tail].x=tx;
                            que[tail++].y=ty;
                            book[tx][ty]=1;
                        }
                    }
                    head++;
                }
                max=max>tail?max:tail;
            }
        }
    }
    cout<<max;
}
全部评论

相关推荐

不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:24
大家还是用ai改吧,我心疼得要死,就当花钱买教训吧,人家直接拿完钱就跑路了
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务