题解 P2960 【[USACO09OCT]Milkweed的入侵Invasion of the Milkweed】

· · 题解

由题目可知，草地的长和宽都不会超过 100 ，数据范围比较小。这个时候，我们就可以考虑使用搜索算法。

搜索算法包括深度优先搜索和广度优先搜索。通过题目描述和样例可以得知，题目要求的是乳草最快需要多少天占领整个草地。根据这一点，我们使用广度优先搜索解决问题。具体的实现流程如下：

  1. 读入草地地图时统计地图上有多少个点是牧草，结果记为 s ；
  2. 将乳草起始坐标加入队列，并把起点标记；
  3. 取出队首，向八个方向拓展；
  4. 将所有没有被乳草占领的点标记成不可以走的格子，即代表被乳草占领，同时在 s 中扣除相应的数量；
  5. 把这些格子加入队列；
  6. 重复3~5步，直到 s 为 0 。这时输出队尾【 因为最后要拓展到队尾，所以输出队尾时间 】。

最后再提一下这题的一些细节问题：

最终代码如下：

#include<iostream>
#include<cstdio>
#define rgt register int
#define ll long long
using namespace std;

const int mxn = 111;

char tmp[mxn][mxn],mp[mxn][mxn];

int n,m,sx,sy,hd=0,tl=1,s=0;   //hd和tl为队首和队尾指针

int px[8]={-1,-1,-1,0,0,1,1,1};
int py[8]={-1,0,1,-1,1,-1,0,1};

struct mode_que{
    int x;
    int y;
    int time;
}que[mxn*mxn]; 
//手写队列，个人感觉STL太慢

inline int work(){
    que[tl].time=0;  //起始时间为0
    que[tl].x=sx;
    que[tl].y=sy;
    mp[sx][sy]='*';  //标记
    s--;   //起点被乳草占领，s-1
    while(hd!=tl){
        hd++;
        for(rgt tpx,tpy,i=0;i<8;i++){
            tpx=que[hd].x+px[i];
            tpy=que[hd].y+py[i];   //拓展新的坐标
            if(tpx<=n&&tpy<=m&&tpx>0&&tpy>0&&mp[tpx][tpy]=='.'){
                s--;   //占领格子
                tl++;   //入队
                que[tl].x=tpx;
                que[tl].y=tpy;
                que[tl].time=que[hd].time+1;  
                mp[tpx][tpy]='*';   //标记
                if(s==0){   //占领完了
                    return que[tl].time;   //返回答案
                }
            }
        }
    }
}

int main()
{
    char tch;
    scanf("%d%d%d%d",&m,&n,&sy,&sx);   //x和y反过来读入，n和m反过来读入

    for(rgt i=1;i<=n;i++){
        scanf("%c",&tch);   //干掉换行符
        for(rgt j=1;j<=m;j++){
            scanf("%c",&tmp[i][j]);  //读入初始草场地图
            if(tmp[i][j]=='.')
                s++;  //统计牧草的格子
        }
    }

    for(rgt i=1;i<=n;i++){
        for(rgt j=1;j<=m;j++){
            mp[i][j]=tmp[n-i+1][j]; 
        }
    }  //反转地图

    printf("%d",work());

    return 0;
}