zyh0413 @ 2024-03-23 09:32:02
测试点全是TLE,不会调,求大佬帮忙:
#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[105][105];
bool dfs(int x,int y,int t){
if(x==n && y==m)
{
return true;
}
if(t==m*n)
{
return false;
}
bool a[4];
if(c[x+1][y]=='.')
{
a[1]=dfs(x+1,y,t+1);
}
if(c[x-1][y]=='.' && x!=1)
{
a[2]=dfs(x-1,y,t+1);
}
if(c[x][y+1]=='.')
{
a[3]=dfs(x,y+1,t+1);
}
if(c[x][y-1]=='.' && y!=1)
{
a[4]=dfs(x,y-1,t+1);
}
return a[1]||a[2]||a[3]||a[4];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
}
}
if(dfs(1,1,0))
{
cout<<"Yes";
}
else
{
cout<<"No";
}
return 0;
}
by SparkingDaydream @ 2024-05-15 21:08:16
我也tle了几发,事实上这道题用迷宫找路的方法去做,回溯的过程肯定会TLE的,不如用连通图的思路去想,从(1,1)开始求连通图,看最后一个点是不是(n,m)如果是,则(1,1)与(n,m)连通,就可以判定yes了