原题链接
更好的阅读体验

题目描述

农民约翰一直努力让他的草地充满鲜美多汁而又健康的牧草。

可惜天不从人愿，他在植物大战人类中败下阵来。

邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

草地像往常一样，被分割成一个高度为Y, 宽度为X的直角网格。

(1,1)是左下角的格（也就是说坐标排布跟一般的X,Y坐标相同）。

乳草一开始占领了格(Mx,My)。

每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格（包括垂直与水平相邻的和对角线上相邻的格）内。

1周之后，这些新占领的格又可以把乳草传播到更多的格里面了。

达达想要在草地被乳草完全占领之前尽可能的享用所有的牧草。

她很好奇到底乳草要多久才能占领整个草地。

如果乳草在0时刻处于格(Mx,My)，那么几个星期以后它们可以完全占领入侵整片草地呢（对给定的数据总是会发生）？

在草地地图中，”.”表示草，而”*”表示大石。

比如这个X=4, Y=3的例子。

....
..*.
.**.

如果乳草一开始在左下角（第1排，第1列），那么草地的地图将会以如下态势发展：

      ....  ....  MMM.  MMMM  MMMM  
      ..*.  MM*.  MM*.  MM*M  MM*M  
      M**.  M**.  M**.  M**.  M**M  
星期数  0     1     2     3     4

乳草会在4星期后占领整片土地。

输入格式
第1行: 四个由空格隔开的整数: X, Y, Mx, My
第2到第Y+1行: 每行包含一个由X个字符（”.”表示草地，”*”表示大石）构成的字符串，共同描绘了草地的完整地图。

输出格式
输出一个整数，表示乳草完全占领草地所需要的星期数。

数据范围
$1≤X,Y≤100$

样例

输入样例：
4 3 1 1
....
..*.
.**.
输出样例：
4

广搜

这道题目除了读入有毒外,似乎没有什么难点.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
const int dx[8]= {1,-1,0,0,1,-1,1,-1};
const int dy[8]= {0,0,1,-1,1,-1,-1,1};
const int N=110;
pii st,now;
char s[N][N];
int cnt,n,m,vis[N][N],ans,dis[N][N];
queue<pii> q;
int check(int x,int y)//判断:在范围;没有被访问过;不是石头
{
    return x>=1 && x<=n && y>=1 && y<=m && vis[x][y]==0 && s[x][y]!='*';
}
int bfs()
{
    q.push(st);
    dis[st.first][st.second]=0;
    vis[st.first][st.second]=1;
    while(q.size())
    {
        now=q.front();
        q.pop();
        fir(i,0,7)
        {
            int x=now.first+dx[i],y=now.second+dy[i];//拓展
            if (check(x,y))
            {
                cnt--;
                vis[x][y]=1;
                dis[x][y]=dis[now.first][now.second]+1;
                ans=max(ans,dis[x][y]);//找出最大的dis,也就是最后答案
                q.push(mk(x,y));
                if (cnt==0)//所有的草地被占满了.
                    return 1;
            }
        }
    }
}
int main()
{
    scanf("%d%d%d%d\n",&m,&n,&st.second,&st.first);//读入真是博大精深啊!!!!!
    for(int i=n; i>=1; i--)
    {
        for(int j=1; j<=m; j++)
        {
            s[i][j]=getchar();
            if (s[i][j]=='.')
                cnt++;//统计有多少个空
        }
        getchar();
    }
    if (s[st.first][st.second]=='.')//刚开始就有一根乳草.
        cnt--;
    bfs();
    cout<<ans;
}