Little_Fox_Fairy @ 2023-07-23 14:09:25
这是代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fx[5]={0,0,0,1,-1},fy[5]={0,1,-1,0,0};
char a[101][101];
bool vis[101][101];
void dfs(int x,int y)
{
if (x==n&&y==m)
{
cout<<"Yes";
exit(0);
}
for (int i=1;i<=4;i++)
{
int dx=fx[i]+x;
int dy=fy[i]+y;
if (dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]&&a[dx][dy]!='#')
{
vis[dx][dy]=1;
dfs(dx,dy);
vis[dx][dy]=0;
}
}
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for (int i=1;i<=n;i++)
{
string s;
cin>>s;
for (int j=1;j<=m;j++)
a[i][j]=s[j-1];
}
vis[1][1]=1;
dfs(1,1);
cout<<"No";
return 0;
}用 bfs AC了，但 dfs 为什么会超时呢？
by xiaoyang111 @ 2023-07-23 14:16:53
我帮你换了一个表就60分了
by xiaoyang111 @ 2023-07-23 14:19:12
可是我的哪个dfs都过了啊？
by xiaoyang111 @ 2023-07-23 14:30:37
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fx[5]={0,-1,0,1,0},fy[5]={0,0,1,0,-1};
char a[101][101];
bool vis[101][101];
void dfs(int x,int y)
{
if (x==n&&y==m)
{
cout<<"Yes";
exit(0);
}
for (int i=1;i<=4;i++)
{
int dx=fx[i]+x;
int dy=fy[i]+y;
if (dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]&&a[dx][dy]!='#')
{
vis[dx][dy]=true;
dfs(dx,dy);
}
}
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;++j)
{
cin >> a[i][j];
}
}
vis[1][1]=true;
dfs(1,1);
cout<<"No";
return 0;
}改了一下过了
by xiaoyang111 @ 2023-07-23 14:32:18
这个其实可以不用回溯，因为既然这个点走过了，那肯定是有比这个路线更优的路线。还有不要用1和0赋值给bool，强制转换也有时间啊。
by xiaoyang111 @ 2023-07-23 14:34:47
主要是强制转换的问题和是否回溯，其他没啥问题。
by xiaoyang111 @ 2023-07-23 14:36:01
推荐一个双倍经验，可以练一下。
这个
by xiaoyang111 @ 2023-07-23 14:36:41
@HXZspr208
by Little_Fox_Fairy @ 2023-07-23 14:48:54
@xiaoyang111 欧，知道了。谢谢大佬
by Little_Fox_Fairy @ 2023-07-23 14:53:51
@xiaoyang111 我之前一直以为1和true还有0和false都是等价的，所以一直都是这么写的。这下知道了
by 280123xxx @ 2023-07-25 00:18:03
@xiaoyang111 那如果硬要回溯呢？咋写啊，个人习惯dfs写回溯