为什么删一行代码就可以AC，否则只有10分

lanmengfei @ 2023-06-09 16:57:05

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool ans=0,book[105][105];
string s[105];
char c[105][105];
const int dis[][2]={
    {0,0},
    {1,0},
    {-1,0},
    {0,1},
    {0,-1}
};
void dfs(int x,int y){
    if(x==n and y==m){
        ans=1;
        return;
    }
    if(x>n or y>m){
        ans=0;
        return;
    }
    for(int i=0;i<5;i++){
        int mx,my;
        mx=x+dis[i][0],my=y+dis[i][1];
        if(mx<1 or mx>n or my<1 or my>m){
            continue;
        }
        if(c[mx][my]=='.' and book[mx][my]==0){
            book[mx][my]=1;
            dfs(mx,my);
            //book[mx][my]=0;删的这一行
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i].size();j++){
            c[i][j+1]=s[i][j];
        }
    }
    dfs(1,1);
    cout<<(ans?"Yes":"No");
    return 0;
}

by hellolin @ 2023-06-09 17:05:55

@lanmengfei 访问状态不应该置 0 的，否则两块路访问状态一直置 0 反复横跳就 TLE 了。

by GloryYang @ 2023-06-09 17:20:56

会导致一个点遍历多次，卡在某个地方死循环，从而TLE，把那行删掉，每个点只遍历一次，就能过了

by lanmengfei @ 2023-06-13 22:05:01

@hellolin 是不是说去掉那一行就和广搜很相似了？

by code_1237 @ 2023-07-03 13:30:48

呜呜呜，我也是这个问题，但我还是不太很懂，有没有佬给我详细的说一下。

by lanmengfei @ 2023-07-05 13:30:53

@code_1237 我回去想了一下，其实大概是这样的

一开始在（1,1）

我们遍历4个方向，在这4个方向中，如果有符合条件的，把这个地方设为已遍历。

接下来再从这4个点开始遍历4个方向，就像是源点扩散一样，直到如果扩散到了（n,m)就停止。（由于不求最短路径，所以遇到无法遍历的点直接跳过，不用再次返回；更不需要广搜的队列实现，时间复杂度大大降低）

代码是这里：

 for(int i=0;i<5;i++){
        int mx,my;
        mx=x+dis[i][0],my=y+dis[i][1];
        if(mx<1 or mx>n or my<1 or my>m){
            continue;
        }
        if(c[mx][my]=='.' and book[mx][my]==0){
            book[mx][my]=1;
            dfs(mx,my);
        }
    }

你可以回去画个图想一下，想通了就很好理解了（我也是这样的）

by code_1237 @ 2023-07-06 15:28:43

@lanmengfei 谢谢大佬十分感谢！！！！！！！！！