dfs的TLE 60分

123uuu @ 2023-12-26 12:49:28

#include<bits/stdc++.h>
using namespace std;
int  fx, fy, p=0;
char mp[110][110];
bool vist[110][110];
int ax[6]={-1, 0, 1, 0};
int ay[6]={0, 1, 0, -1};
void mg(int nx, int ny){
    int i;
    if(nx == fx && ny == fy){
        cout << "Yes";
        exit(0);
    }
    for(i = 0;i < 4;++i){

        int tx, ty;
        tx = nx + ax[i];
        ty = ny + ay[i];
        if(mp[tx][ty] == '#')continue;
        if(vist[tx][ty] == 1)continue;
        if(tx <= 0 || tx > fx || ty > fy || ty <= 0)continue;
        vist[tx][ty] = 1;
        mg(tx,ty);
        vist[tx][ty] = 0;
    }

}
int main(){
    cin >> fx >> fy;
    for(int i = 1;i <= fx; ++i){
        for(int j = 1; j <= fy; ++j){
            cin >> mp[i][j];
        }
    } 
    vist[1][1] = 1;
    mg(1, 1);
    cout << "No";
return 0;
}

by renjunxin0721 @ 2023-12-26 12:58:12

试了一下
这个题不用回溯就能过 把24行删掉就行

vist[tx][ty] = 0;

代码改后

#include<bits/stdc++.h>
using namespace std;
int  fx, fy, p=0;
char mp[110][110];
bool vist[110][110];
int ax[6]={-1, 0, 1, 0};
int ay[6]={0, 1, 0, -1};
void mg(int nx, int ny){
    int i;
    if(nx == fx && ny == fy){
        cout << "Yes";
        exit(0);
    }
    for(i = 0;i < 4;++i){

        int tx, ty;
        tx = nx + ax[i];
        ty = ny + ay[i];
        if(mp[tx][ty] == '#')continue;
        if(vist[tx][ty] == 1)continue;
        if(tx <= 0 || tx > fx || ty > fy || ty <= 0)continue;
        vist[tx][ty] = 1;
        mg(tx,ty);
    }

}
int main(){
    cin >> fx >> fy;
    for(int i = 1;i <= fx; ++i){
        for(int j = 1; j <= fy; ++j){
            cin >> mp[i][j];
        }
    } 
    vist[1][1] = 1;
    mg(1, 1);
    cout << "No";
return 0;
}

by renjunxin0721 @ 2023-12-26 13:13:23

@123uuu

by 123uuu @ 2023-12-26 14:15:29

@renjunxin0721 谢谢，已过