S1746 @ 2023-08-03 14:59:47
#include<iostream>
using namespace std;
int n,x1,y1,x2,y2,ss,ans=2E31-1,a[1010][1010],vis[1010][1010];
void dfs(int x,int y)
{
vis[x][y]=1;
if(x==x2&&y==y2)
{
if(ss<ans)
{
ans=ss;
}
ss--;
return;
}
if(x<n&&a[x+1][y]==0&&vis[x+1][y]==0)
{
ss++;
dfs(x+1,y);
}
if(y<n&&a[x][y+1]==0&&vis[x][y+1]==0)
{
ss++;
dfs(x,y+1);
}
if(x>1&&a[x-1][y]==0&&vis[x-1][y]==0)
{
ss++;
dfs(x-1,y);
}
if(y>1&&a[x][y-1]==0&&vis[x][y-1]==0)
{
ss++;
dfs(x,y-1);
}
ss--;
}
int main()
{
string s[1010];
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>s[i];
for(int ii=0; ii<n; ii++)
{
a[i][ii+1]=s[i][ii]-'0';
}
}
cin>>x1>>y1>>x2>>y2;
dfs(x1,y1);
cout<<ans;
return 0;
}
by bytfr @ 2023-08-04 16:16:48
建议用bfs
by bytfr @ 2023-08-04 16:17:49
ss++也只能写一个,你这样加了4个步长