自动搬运

查看原文

来自洛谷，原作者为

	hater 光灌满了窗户，像风撑满船帆

搬运于2025-08-24 21:43:52，当前版本为作者最后更新于2019-06-29 20:22:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

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

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

递推

---

#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

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

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

小小的总结

---

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

但是洛谷多篇重复

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

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

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

有想法就要大胆的去实现

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

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

谢谢您尊重我的劳动成果