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

· · 题解

这是一道对懒得看题意的我 没错就是我人非常不友好的一道题

令人发指的横坐标与纵坐标 与 起点坐标 坑了我很久

看了讨论区的帖子才知道自己的问题

话不多说了 先看第一种解法

递推

#include<bits/stdc++.h>
using namespace std;
int f[105][105],tot=1,n,m,sx,sy,Time=1,sum;
char Map[105][105];
int l[8][2]={{1,0},{0,1},{-1,0},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
int main()
{
    memset(f,-1,sizeof(f));
    cin>>m>>n>>sy>>sx;
    for(int i=n;i>0;i--)
     for(int j=1;j<=m;j++)
       {
          cin>>Map[i][j];
          if(Map[i][j]=='.') sum++;
       }
    f[sx][sy]=0; 
    while(tot!=sum)
    {
        for(int i=1;i<=n;i++)
           for(int j=1;j<=m;j++)
              {
                 bool flag=0;
                     if(f[i][j]>0) continue;
                 if(Map[i][j]=='*') continue;
                 for(int q=0;q<8;q++)
                 {
                 int tx=i+l[q][0];
                 int ty=j+l[q][1];
                 if(tx<1||tx>n||ty<1||ty>m) continue;
                 if(Map[tx][ty]=='*') continue;
                 if(f[tx][ty]!=Time-1) continue;
                 f[i][j]=Time; flag=1;
                 }
                 if(flag) tot++;
           }
        Time++;
    }
    cout<<Time<<endl;
    return 0;
}

sum表示草的数量 tot表示已经占领的草的数量

Time 表示已经到第几天了

f 数组存储着每个草点第一次被占领的时间

第一层循环表示 ： 如果还有草地没被占领 （tot！=sum）

就继续扩展

第二三层循环枚举点

显然点本身不能是石头且没被占领过

第四层循环枚举邻近的点

如果旁边有被占领的点并且它是被上一次扩展占领的

那么就标记这个点 被占领的点（tot）++

结果

似乎令人悲愤

开了o2也只有18分

不过细想实际上是情理之中

分析一下算法 ：

后三重循环都是确定的（1001008）

只有第一重循环不确定（时间）

当时间多起来的时候 程序就跑的很慢很慢

但是反而在第十个点 n m 大 但是时间小的时候

递推还是跑的可以的

深搜

有宽搜AC的地方就会有深搜的骗分记录

本蒟蒻用深搜尝试了一下 

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,ans[105][105];
char Map[105][105];
int l[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
inline void dfs(int x,int y,int step)
{
    ans[x][y]=step;
    int tx,ty;
    for(register int i=0;i<8;i++)
    {
        tx=x+l[i][0]; ty=y+l[i][1];
        if(tx<1||tx>n||ty<1||ty>m) continue;
        if(Map[tx][ty]=='*') continue;
        if(step+1>=ans[tx][ty]) continue;
        dfs(tx,ty,step+1);
    }
}
int main()
{
    memset(ans,0x3f,sizeof(ans));
    cin>>m>>n>>sy>>sx;
    for(register int i=n;i>0;i--)
      for(register int j=1;j<=m;j++)
        cin>>Map[i][j];
    dfs(sx,sy,0); 
    int cnt=0;
    for(register int i=1;i<=n;i++)
      for(register int j=1;j<=m;j++)
        if(Map[i][j]!='*') cnt=max(cnt,ans[i][j]);
    cout<<cnt<<endl;
    return 0;
}

基本上用深搜写迷宫是要用记忆化的

用一个数组来记录最小到达的时间

假设 ： 你走到这用了x步 但是有人用更少的步数走到了这里过

你还要继续走吗 ？ 你继续走会使答案变小吗？

显然不会的 那么遇到这种情况就别搜了

这就叫最优解剪枝

最后一遍循环寻找最大值

结果

似乎令人忧伤

不开o2 63分 吸氧后 90

即使我再加了一些register inline 但是也没有用

望哪位大佬来帮我修到AC

正解 ———— 宽搜

实际上蒟蒻一开始就想到宽搜

但是为了尝试提供新的思路 连续失败多次

发现这题还是得用宽搜 

#include<bits/stdc++.h>
using namespace std;
char Map[105][105];
int n,m,l[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
bool vis[105][105];
struct mmp
{
    int x,y,step;
}f,v;
queue <mmp> q; 
int bfs()
{
    int tot=0;
    f.step=0; q.push(f);
    while(!q.empty())
    {
        f=q.front();
        q.pop(); tot=max(tot,f.step);
        for(int i=0;i<8;i++)
        {
            v.x=f.x+l[i][0];
            v.y=f.y+l[i][1];
            v.step=f.step+1;
            if(v.x<1||v.x>n||v.y<1||v.y>m) continue;
            if(vis[v.x][v.y]) continue;
            if(Map[v.x][v.y]=='*') continue;
            q.push(v); vis[v.x][v.y]=1; 
        }
    }
    return tot;
}
int main()
{
    cin>>m>>n>>f.y>>f.x;
    vis[f.x][f.y]=1;
    for(int i=n;i>0;i--)
     for(int j=1;j<=m;j++)
      cin>>Map[i][j];
    cout<<bfs()<<endl;
    return 0;
}

洛谷缩进有小小的毛病但是别怪我哦QAQ

利用宽搜 我们只用输出最后出队列的点的步数就够了

主要是细节上的问题 不细心是要排错一会儿的

小小的总结

实际上只打算发宽搜的程序

但是洛谷多篇重复

蒟蒻就另辟蹊径 用其他稍劣的方法拿部分分

实际上就是想告诉看到这篇题解的大佬

一道题不要局限自己的一种思维

有想法就要大胆的去实现

这样做一题比做十题相同解法的题目的效果要好得多

最后感谢耐心看完蒟蒻题解的大佬 ！！！

谢谢您尊重我的劳动成果