9个TLE,求调

e4fsrc2e4fsrc2 @ 2022-08-16 12:48:49

#include<iostream>
using namespace std;
int n,m;
char mp[105][105];
int dx[4]={0,0,-1,1},
    dy[4]={-1,1,0,0};
bool vis[105][105],flag;
void dfs(int x,int y){
    if(flag)return;
    if(x==n&&y==m){
        flag=true;
        return;
    }
    for(int i=0; i<4; i++){
        int nx=x+dx[i],
            ny=y+dy[i];
        if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&mp[nx][ny]='.'){
            mp[nx][ny]='#';
            dfs(nx,ny);
            mp[nx][ny]='.';
        }
    } 
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>mp[i][j];
    dfs(1,1);
    if(flag)cout<<"Yes";
    else cout<<"No";
    return 0;
}

by Tobiichi_Origami @ 2022-08-16 12:53:09

@e4fsrc2e4fsrc2 把回溯删了就过了

by Adchory @ 2022-08-16 12:57:49

@e4fsrc2e4fsrc2 怎么通过编译的 17行mp[nx][ny]='.'

by e4fsrc2e4fsrc2 @ 2022-08-16 13:02:09

@Tobiichi_Origami 回溯删了就变成MLE了

by e4fsrc2e4fsrc2 @ 2022-08-16 13:03:17

@Reimu_Hakurei 我交的的时候是写了mp[nx][ny]=='.'

by Adchory @ 2022-08-16 13:06:15

@e4fsrc2e4fsrc2 没删错吧，删第20行。

#include<iostream>
using namespace std;
int n,m;
char mp[105][105];
int dx[4]={0,0,-1,1},
    dy[4]={-1,1,0,0};
bool vis[105][105],flag;
void dfs(int x,int y){
    if(flag)return;
    if(x==n&&y==m){
        flag=true;
        return;
    }
    for(int i=0; i<4; i++){
        int nx=x+dx[i],
            ny=y+dy[i];
        if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&mp[nx][ny]=='.'){
            mp[nx][ny]='#';
            dfs(nx,ny);

        }
    } 
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>mp[i][j];
    dfs(1,1);
    if(flag)cout<<"Yes";
    else cout<<"No";
    return 0;
}

by e4fsrc2e4fsrc2 @ 2022-08-16 13:10:16

@Tobiichi_Origami @Reimu_Hakurei 刚刚删错了，谢谢dalao