dfs0分全wa求解

P1746 离开中山路

User586768 @ 2023-07-14 20:32:03

#include <bits/stdc++.h>
using namespace std; 
int n=0,a[1001][1001],vis[1001][1001];
int xx1,yy1,xx2,yy2,sum[10000000];
void dfs(int x,int y,int ex,int ey,int s){
    vis[x][y]=1;
    if(x!=0&&vis[x-1][y]==0){
        dfs(x-1,y,ex,ey,s+1);
    }
    if(y!=0&&vis[x][y-1]==0){
        dfs(x,y-1,ex,ey,s+1);
    }
    if(x!=n-1&&vis[x+1][y]==0){
        dfs(x+1,y,ex,ey,s+1);
    }
    if(y!=n-1&&vis[x][y+1]==0){
        dfs(x,y+1,ex,ey,s+1);
    }
    if(x==ex&&y==ey){
        sum[vis[1001][1001]]==s;
        vis[1001][1001]++;
        return;
    }
}
int main(){
    scanf("%d",&n);
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            char c;
            scanf("%c",&c);
            a[i][j]=c-'0';
            if(a[i][j]==1){
                vis[i][j]=1;
            }
        }
    }
    scanf("%d %d %d %d",&xx1,&xx2,&yy1,&yy2);
    int ans;
    for(int i=0;i<10000000;i++){
        ans=max(ans,sum[i]);
    }
    printf("%d",ans);
    return 0;
} 

by mediocre_ @ 2023-07-15 13:26:12

@zk123bc dfs肯定T啊,不对,你连代码都是错的


by mediocre_ @ 2023-07-15 13:26:44

@zk123bc 建议bfs


by User586768 @ 2023-07-16 18:13:07

@Mr_Huang12 bfs不会写


by mediocre_ @ 2023-07-16 18:41:43

@zk123bc 可以参考一下我的代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 9;
const int fx[] = {-1, 0, 0, 1};
const int fy[] = {0, -1, 1, 0};
int n, sx, sy, bx, by;
int a[N][N];
int vis[N][N];
bool use[N][N];
struct Node {
    int x, y;
};
queue <Node>q;
bool inmap(int nx, int ny) {
    return nx >= 1 && nx <= n && ny >= 1 && ny <= n;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%1d", &a[i][j]);
    scanf("%d%d%d%d", &sx, &sy, &bx, &by);
    q.push(Node{sx, sy});
    use[sx][sy] = true;
    while (!q.empty()) {
        Node u = q.front();
        q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = u.x + fx[d];
            int ny = u.y + fy[d];
            if (inmap(nx, ny) && a[nx][ny] == 0 && !use[nx][ny]) {
                vis[nx][ny] = vis[u.x][u.y] + 1;
                use[nx][ny] = true;
                q.push(Node{nx, ny});
            }
        }
    }
    printf("%d", vis[bx][by]);
    return 0;
}

by mediocre_ @ 2023-07-16 18:43:34

@zk123bc 像这种最短路的问题最好用bfs,不然很容易T


by User586768 @ 2023-07-18 20:47:48

@Mr_Huang12 但我是全wa,没t额


by User586768 @ 2023-07-18 20:48:29

@Mr_Huang12 我再想想bfs吧


|