30分(样例都没过)

Dpf20120621 @ 2024-01-17 19:43:45

#include<bits/stdc++.h>
using namespace std;
int n,m,bx[]={0,0,1,-1},by[]={1,-1,0,0};
bool f=true,v[101][101];
char c;
void dfs(int x,int y){
    if(x==n-1&&y==m-1){
        printf("Yes");
        f=false;
        return;
    }
    for(int i=0;i<4;i++){
        int nx=x+bx[i];
        int ny=y+by[i];
        if(!f)break;
        if(!v[nx][ny]||nx<0||nx>=n||ny<0||ny>=m)continue;
        v[nx][ny]=true;
        dfs(nx,ny);
        v[nx][ny]=false;
    }
    return;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>c;
            if(c=='#')v[i][j]=true;
        }
    }
    dfs(0,0);
    if(f)printf("No");
    return 0;
}

by Dpf20120621 @ 2024-01-17 19:48:23

还有

真的不用回朔吗

by Lemon_zqp @ 2024-01-17 19:57:53

@Dpf20120621 你怎么知道我会看到这个……

by Lemon_zqp @ 2024-01-17 19:58:48

@Dpf20120621 我也不知到为什么不会回溯，但是回溯时间肯定会比较长，没回溯能AC可能是数据不严谨。

by Lemon_zqp @ 2024-01-17 20:18:25

@Dpf20120621 70分：

#include<bits/stdc++.h>
using namespace std;
int n,m,bx[]={-1,1,0,0},by[]={0,0,-1,1};
bool v[105][105];
char c;
void dfs(int x,int y){
    if(x==n-1&&y==m-1){
        cout <<"Yes";
        exit(0);
    }
    for(int i=0;i<4;i++){
        int nx=x+bx[i];
        int ny=y+by[i];
        if(v[nx][ny]||nx<0||nx>n||ny<0||ny>m)continue;
        v[nx][ny]=true;
        dfs(nx,ny);
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>c;
            if(c=='#')v[i][j]=true;
            else v[i][j]=false;
        }
    }
    dfs(0,0);cout <<"No";
    return 0;
}

by Lemon_zqp @ 2024-01-17 20:19:11

@Dpf20120621 我这个100的，你对着看看：

#include<bits/stdc++.h>
using namespace std;

bool mp[105][105];
int n, m;
int dx[5] = {-1, 1, 0, 0};
int dy[5] = {0, 0, -1, 1};

void dfs(int x, int y){
    if(x == n && y == m){
        cout << "Yes";
        exit(0); 
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny]){
            mp[nx][ny] = false;
//          cout << nx << " " << ny << endl;
            dfs(nx, ny);
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char a;
            cin >> a;
            if(a == '.'){
                mp[i][j] = true;
            }
            else{
                mp[i][j] = false;
            }
        }
    }
    dfs(1, 1);
    cout << "No";
    return 0;
}

by Dpf20120621 @ 2024-01-17 20:21:10

请问一下

exit(0)

是什么意思

by Lemon_zqp @ 2024-01-17 20:40:22

@Dpf20120621 return 0；的另一种写法。

by Ztartrek @ 2024-01-17 21:12:20

@Dpf20120621 直接结束程序，并返回0。

by chengkelin2024 @ 2024-01-26 15:36:58

用广度优先搜所呀