10分 全是超时

jr_cct @ 2023-07-02 14:35:38

#include <iostream>

using namespace std;
int n,m;
char a[10005][10005];
int xx[5]={0,0,0,1,-1};
int yy[5]={0,1,-1,0,0};
void dfs(int lx,int ly){
    if(lx==n&&ly==m){
        cout << "Yes";
        exit(0);
    }
    int nx,ny;
    for(int i = 1;i <= 4;i++){
        nx=lx+xx[i];
        ny=ly+yy[i];
        if(nx<=n&&ny<=m&&nx>0&&ny>0&&a[nx][ny]!='#'){
            a[nx][ny]='#';
            dfs(nx,ny);
            a[nx][ny]='.';
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin >> a[i][j];
    dfs(1,1);
    cout << "No";
    return 0;
}

by Milthm @ 2023-07-02 14:39:30

@jr_cct 你的vis数组哪去了

by jr_cct @ 2023-07-02 14:43:06

给我吃了

by jr_cct @ 2023-07-02 14:44:10

把走过的路标记成#就能不让它再走过了Ya

by Terrible @ 2023-07-02 14:44:41

@jr_cct

把后面的 a[nx][ny]='.';扔了就行了。

加上回溯的操作就成了遍历所有路径了（路径是指数级的），去掉是遍历每一个可走格点。

另外 char a[10005][10005];不需要这么大，只需要 char a[105][105];。还有，exit(0);在使用C++类之后不建议使用。

by jr_cct @ 2023-07-02 14:47:47

@Terrible

跟exit(0)好像没什么关系吧

by jr_cct @ 2023-07-02 14:49:16

把a[nx][ny]='.';扔了就AC了

by jr_cct @ 2023-07-02 14:49:59

蟹蟹@Terrible

by Terrible @ 2023-07-02 14:50:19

@jr_cct exit(0);会让主函数不进行对类对象析构强行结束程序。专业软件里面只能中午这么用，因为早晚会出事。OJ上写的就是玩具程序而已。。。

by jr_cct @ 2023-07-02 14:52:25

那我还是这样吧

#include <iostream>
using namespace std;
int n,m;
char a[105][105];
int xx[5]={0,0,0,1,-1};
int yy[5]={0,1,-1,0,0};
bool flag=0;
void dfs(int lx,int ly){
    if(lx==n&&ly==m){
        cout << "Yes";
        flag=1;
    }
    int nx,ny;
    for(int i = 1;i <= 4;i++){
        nx=lx+xx[i];
        ny=ly+yy[i];
        if(nx<=n&&ny<=m&&nx>0&&ny>0&&a[nx][ny]!='#'){
            a[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 >> a[i][j];
    dfs(1,1);
    if(!flag)cout << "No";
    return 0;
}

这样就AC了