我是蒟蒻(没学几天,还请大佬勿喷),因为这道题不能发题解,所以来这里发表一下我的看法 首先,这道题与P1605其实是同一道,P1605是找有几条路,这道题是判定,先给出TLE的代码,因为n,m 最大100,所以肯定会TLE(2^100)
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
char g[N][N];
bool flag=false;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y)
{
if(x==n&&y==m){flag=true;return;}
g[x][y]='#';
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>n||b<1||b>m)continue;
if(g[a][b]=='#'){continue;}
dfs(a,b);
g[a][b]='.';
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>g[i][j];
dfs(1,1);
if(flag)cout<<"Yes";
else cout<<"No";
return 0;
}
再者,给出另一种思维,大家都做过连通图吧,就是类似P1596这样的题,用DFS判断一个矩阵中有几块连在一起的图形(因为我刚学算法没多久,董晓老师叫它n连通,为了方便记忆,我叫它连通图,貌似这个说法并不准确,因为图论好像有这种东西),我们只用判断与(1,1)连通的图中,是否存在(n,m)就可以了,存在,则两点连通,自然可以到达,反之不能到达,所以用求连通图的板子改一下就好了(或是迷宫板子不进行回溯,一搜到底!!!)
// Problem: B3625 迷宫寻路
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3625
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,ans;
char g[N][N];
bool flag=false,ok=false;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y)
{
if(x==n&&y==m){flag=true;return;}
g[x][y]='#';
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>n||b<1||b>m)continue;
if(g[a][b]=='#'){ans++;continue;}
dfs(a,b);
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>g[i][j];
dfs(1,1);
if(flag)cout<<"Yes";
else cout<<"No";
return 0;
}
是的,AC代码只用删除回溯就可以了