题目描述

Farmer John has always done his best to keep the pastures full of luscious, delicious healthy grass for the cows. He has lost the battle, though, as the evil milkweed has attained a foothold in the northwest part of his farm.
The pasture, as usual, is partitioned into a rectilinear grid of height and width with (1,1) being in the lower left corner (i.e., arranged as a normal X,Y coordinate grid). The milkweed has initially begun growing at square (Mx,My). Each week the milkweed propagates to all non-rocky squares that surround any square it already occupies, as many as eight more squares (both the rectilinear squares and the diagonals). After only one week in those squares, it is ready to move on to more squares.
Bessie wants to enjoy all the grass she can before the pastures are taken over by milkweed. She wonders how long it can last. If the milkweed is in square (Mx,My) at time zero, at what time does it complete its invasion of the pasture (which, for the given input data, will always happen)?
POINTS: 125
The pasture is described by a picture with '.'s for grass and '*'s for boulders, like this example with X=4 and Y=3: .... ..*. .**. If the milkweed started in the lower left corner (row=1, column=1), then the map would progress like this: 
            ....   ....     MMM.  MMMM   MMMM 
            ..*.  MM*.  MM*.    MM*M    MM*M 
           M**.  M**.   M**.       M**.      M**M 
 week   0      1        2           3             4
    The milkweed has taken over the entire field after 4 weeks.

输入描述:

* Line 1: Four space-separated integers: X, Y, Mx, and My
* Lines 2..Y+1: Line y+1 describes row (Y+2-y) of the field with X characters ('.' for grass and '*' for a boulder)

输出描述:

* Line 1: A single integer that is the week number when the milkweed takes over the last remaining non-boulder square of the pasture.

示例1

输入
4 3 1 1 
.... 
..*. 
.**. 
输出
4

解答

首先这道题是一道经典的BFS。非常适合刚刚学习深搜的同学。
现在分析一下这个问题。首先，每周是八个方向。就是一圈。
也就是说入侵的范围关于时间是成辐射型扩散。让求最大时间。
也就是完美的BFS。算出来之后，维护一个最大用时就好。
不过说一句。这个数区范围对于一个不会stl的人来说可以直接手写队列。
好了上代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;//头文件不说
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,1,-1};//定义八个方向
int dis[102][102];//储存所需要的时间
int n,m;int ans;//ans是需要维护的最大值。
int head=1;int tail=1;//定义队列。注意队头队尾是1！；
bool book[102][102];//图
int q[10002][2];//手写队列，第二维一个是横坐标，一个是纵坐标
int mx;int my;//初始位置
int main()
{
    scanf("%d%d%d%d",&n,&m,&mx,&my);//输入并且处理
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char now;
            cin>>now;
            if(now=='.') book[i][j]=true;
            else book[i][j]=false;
        }
    }//注意我的建图顺序
/*    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",book[i][j]);
        }
        printf("\n");
    }
*///测试点
    q[1][0]=m-my+1;//把起始点压进队列
    q[1][1]=mx;
    dis[my][m-my+1]=0;//初始化
    while(head<=tail)//判断是否为空队列
    {
        int now_x=q[head][0];
        int now_y=q[head][1];
        int tx,ty;
        head++;//取出队头横纵坐标
        for(int i=0;i<8;i++)//八个方向
        {
            tx=now_x+dx[i];ty=now_y+dy[i];
            if(book[tx][ty]==true&&!dis[tx][ty])
            /*
            这里有个小优化。就是判断能不能走之后。如果搜过了（dis[tx][ty]！=0）就可以不搜了。因为一定会重，直接跳过。
            */
            {
                dis[tx][ty]=dis[now_x][now_y]+1;
                q[++tail][0]=tx;
                q[tail][1]=ty;//判断，更新，入队
            }
        }
    }
/*    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",dis[i][j]);
        }
        printf("\n");
    }*///测试数据
    
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                ans=max(ans,dis[i][j]);
            }
        }//找最大值
        printf("%d",ans);//输出
    return 0;//程序拜拜
}
实际上我最后67行开始可以有一个优化。就是在更新的时候就连ans一起维护了。就像这样
//54行开始
    if(book[tx][ty]==true&&!dis[tx][ty])
            {
                dis[tx][ty]=dis[now_x][now_y]+1;
                ans=max(ans,dis[tx][ty]);
                q[++tail][0]=tx;
                q[tail][1]=ty;
            }
        }
    }
    printf("%d",ans);
    return 0;


来源：Arcturus