自动搬运

查看原文

来自洛谷，原作者为

	犇犇犇犇 菜qaq

搬运于2025-08-24 21:53:22，当前版本为作者最后更新于2018-12-14 21:48:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先看数据范围，这道题n（1≤n≤100），所以一个dfs就可以过了。

但是还是把我卡了好久。

这道题稍微难一点的地方就是$dfs$的时候从$0$开始不碰到下一个0或者边界永不停止。
所以自然可以想到用$while$语句。
我们用$dx,dy$来表示向四个方向移动。用变量$s$来统计从这个$0$到下一个$0$的步数。

	int tx=x,ty=y,s=0;
    while(tx+dx[i]>0 && tx+dx[i]<=n && ty+dy[i]>0 && ty+dy[i]<=n) //碰到边界
    {
		tx+=dx[i];
		ty+=dy[i]; 
		s++;  //走到下一个点
        if(m[tx][ty]==0) break; //走到目标！
    }

下面就可以很愉快的打$dfs$模板了。

要注意的是，当我们的步数$s=1$时情况为两个$0$相连，同样不满足要求

上代码

#include <bits/stdc++.h>
using namespace std;     
int n,i,j,k,ans;
int m[105][105],f[105][105]; //m表示棋盘，f统计这个点是否走过
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1}; //dx,dy表示四向移动
void dfs(int x,int y,int step) 
{
	int i;
	ans=max(ans,step); //更新ans
    for(i=0;i<4;i++) 
	{
        int tx=x,ty=y,s=0;
        while(tx+dx[i]>0 && tx+dx[i]<=n && ty+dy[i]>0 && ty+dy[i]<=n) 
		{
			tx+=dx[i];
			ty+=dy[i];
			s++;
            if(m[tx][ty]==0) break;
        } //如上述
        if(tx>0 && tx<=n && ty>0 && ty<=n && f[tx][ty]==0 && m[tx][ty]==0 && s!=1) //碰壁，走过，当前格子为0，两个0相连都不能走
		{
            f[tx][ty]=1;
            dfs(tx,ty,step+s); //走到下一个点
            f[tx][ty]=0; //回溯
        }
    }
}
int main() 
{
    int x,y,i,j;
	cin>>n>>x>>y;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>m[i][j];
    f[x][y]=1; //出发点被走过了，所以要单独写
    dfs(x,y,0);	
    cout<<ans<<endl;
    return 0;	
}