40分

chht_0219 @ 2024-07-10 11:31:36

#include<bits/stdc++.h>
using namespace std;
char a[11][11];
int ans,us[11][11];
int n,n1;
int dx[9]={0,-1,-1,0,1,1,1,0,-1};
int dy[9]={0,0,1,1,1,0,-1,-1,-1};
void dfs(int x,int y) {
    if(x==n&&y==n1){
        ans++;
    }
    for(int i=1;i<=8;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if((nx>=1&&ny<=n1)&&(ny>=1&&nx<=n)&&a[nx][ny]==0&&us[nx][ny]==0){
            us[nx][ny]=1;
            dfs(nx,ny);
            us[nx][ny]=0;
        }
    }
}
int main()
{

    cin>>n;
    cin>>n1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n1;j++){
        cin>>a[i][j];          
        }   
    }
    us[1][1]=1;
    dfs(1,1);
    if(ans>=1){
        cout<<"Yes";
    }else if(ans==0){
        cout<<"No";
}
    return 0;
}

by Sugar_Fate @ 2024-07-10 15:00:26

只是四联通问题（

by Sugar_Fate @ 2024-07-10 15:20:20

@chht_0219

#include<bits/stdc++.h>  
using namespace std;  
char a[101][101];  
bool us[101][101];
int ans = 0;  
int n, n1;  

void dfs(int x, int y) {  
    if (x < 0 || y >= n1 || y < 0 || x >= n || a[x][y] == '#' || us[x][y]) {  
        return;  
    }  
    if (x == n - 1 && y == n1 - 1) {
        cout << "Yes";  
        ans = 1;  
        exit(0);  
    }  
    us[x][y] = true;  
    dfs(x, y - 1);  
    dfs(x, y + 1);  
    dfs(x - 1, y);  
    dfs(x + 1, y);  
}  

int main() {  
    cin >> n >> n1;
    for (int i = 0; i < n; i++) { 
        for (int j = 0; j < n1; j++) {  
            cin >> a[i][j];  
        }  
    }  
    dfs(0, 0); 
    if (ans == 0) { 
        cout << "No";  
    }  
    return 0;  
}

帮你改了一下：把数组的起始索引从 0 改到了 1，把 dfs 里的循环给展开了，（这道题是四联通不是八联通）这道题也不用回溯，然后如果检测到到了重点就退出，省点时间（

by chht_0219 @ 2024-07-10 15:33:08

@Sugar_Fate 谢谢 以关注

by chht_0219 @ 2024-07-10 16:00:10

允许我问一下什么是四联通？ 我不知道啊

我不是菜狗

by chht_0219 @ 2024-07-10 17:05:12

知道了