TLEaaa

glass_goldfish @ 2024-06-16 17:05:39

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[101][101];
bool v[101][101];
bool dfs(int x,int y)
{
    if(x<1||y<1||x>n||y>n||a[x][y]=='#'||v[x][y])return 0;
    else if(x==n&&y==m)return 1;
    v[x][y]=1;
    bool k=dfs(x+1,y)||dfs(x-1,y)||dfs(x,y+1)||dfs(x,y-1);
    v[x][y]=0;
    return k;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        cin>>a[i][j];
    if(dfs(1,1))cout<<"Yes";
    else cout<<"No";
    return 0;
}

by kexun_kevin @ 2024-06-16 17:13:30

@liulijinyu

这题不用回溯，因为它不是最短路，所以无论是怎么走到这的都无所谓，回溯了反而会计算多次，浪费时间。

by glass_goldfish @ 2024-06-16 17:17:17

@kexun_kevin so,,该怎么写

by kexun_kevin @ 2024-06-16 17:19:25

@liulijinyu

你不会不知道回溯是啥吧（那你咋写出来的），就是

v[x][y] = 0;

去掉就行了

by glass_goldfish @ 2024-06-16 17:21:02

@kexun_kevin 50，WA

by glass_goldfish @ 2024-06-16 17:21:44

@kexun_kevin 样例都没过

by kexun_kevin @ 2024-06-16 17:22:35

@liulijinyu

哦对，你判越界的时候 y<m 写成 y<n 了，把这个改了应该就行了

by glass_goldfish @ 2024-06-16 17:24:48

@kexun_kevin AC了，感谢！ abcd

by xutengyuan2012 @ 2024-07-01 22:51:16

@kexun_kevin 我也是这个问题，现在AC了，谢谢大佬！