szlh_XJS @ 2023-04-22 09:44:19
#include<iostream>
#include<string.h>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<time.h>
#include<stdlib.h>
#include<vector>
#include<stack>
#include<ctype.h>
#include<cstring>
using namespace std;
int n,a,b,c,d;
string nn[1005];
void dfs(int i,int j,int s)
{
if(i<1||j<0||i>n||j>n-1||nn[i][j]=='1')
{
return ;
}
if(i==c&&j==d)
{
cout<<s;
exit(0);
}
s++;
dfs(i+1,j,s);
dfs(i-1,j,s);
dfs(i,j-1,s);
dfs(i,j+1,s);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>nn[i];
}
cin>>a>>b>>c>>d;
dfs(a,b,0);
cout<<-1;
return 0;
}
第一次
#include<iostream>
#include<string.h>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<time.h>
#include<stdlib.h>
#include<vector>
#include<stack>
#include<ctype.h>
#include<cstring>
using namespace std;
int n,a,b,c,d;
string nn[1005];
void dfs(int x,int y,int s)
{
if(nn[x][y]=='1'||x<1||y<0||x>n||y>n-1)
{
return ;
}
if(x==c&&y==d-1)
{
cout<<s;
exit(0);
}
s++;
nn[x][y]='1';
dfs(x-1,y,s);
dfs(x,y+1,s);
dfs(x-1,y,s);
dfs(x,y+1,s);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>nn[i];
}
cin>>a>>b>>c>>d;
dfs(a,b-1,0);
cout<<-1;
return 0;
}
第二次
by _maojun__ @ 2023-04-22 09:49:55
@szlh6XJS 你这样 dfs 有可能绕了一圈然后给这个点打上一个不优的标记。
比如
01
32
其实 3 的那个点大可以一步走过去但是你直接标记了不让修改
by _maojun__ @ 2023-04-22 09:50:08
建议 bfs
by zjw806903 @ 2023-04-22 10:07:20
同上,建议bfs,dfs容易出错
因为本人就是用的bfs
by szlh_XJS @ 2023-04-22 11:30:47
@zjw806903 感谢大佬
by szlh_XJS @ 2023-04-22 11:31:01
@zjw806903 感谢大佬