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;
}