救救孩子我吧《P1746 离开中山路》

Apollo0130 @ 2024-07-04 09:09:35

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int g[N][N];
bool st[N][N],f;
int dx[5]={-1,0,1,0};
int dy[5]={0,1,0,-1};
int n,sx,sy,ex,ey,sum;
struct node{
    int x,y,step;
}q[100*N];
int tt=1,hh=1,tx,ty;

void bfs(int x,int y){
    q[tt].x=sx;
    q[tt].y=sy;
    q[tt].step=0;
    tt++;
    while(hh<=tt){
        for(int i=0;i<4;i++){
            tx=q[hh].x+dx[i];
            ty=q[hh].y+dy[i];
            if(tx<1 || tx>n || ty<1 || ty>n)continue;
            if(!st[tx][ty]){
                q[tt].x=tx;
                q[tt].y=ty;
                q[tt].step=q[hh].step+1;
                st[tx][ty]=1;
                tt++;
            }
            if(tx==ex && ty==ey){
                f=1;
                cout<<q[tt-1].step;
                break;
            }
        }
        if(f)break;
        hh++;
    }
}

int main(){
    cin>>n;
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c;
            g[i][j]=c-48;
        }
    }
    cin>>sx>>sy>>ex>>ey;
    st[sx][sy]=1;
    bfs(sx,sy);
} 

by _Panyc @ 2024-07-04 09:20:58

@zlf201101 我帮你该到了80分

#include<bits/stdc++.h>
using namespace std;
const int N=1007;
int g[N][N];
bool st[N][N];
int dx[5]={-1,1,0,0};
int dy[5]={0,0,1,-1};
int n,sx,sy,ex,ey,sum;
struct node{
    int x,y,step;
}q[N*N];
int tt=-1,hh,tx,ty;
void bfs(int x,int y){
    tt++;
    q[tt].x=sx;
    q[tt].y=sy;
    q[tt].step=0;
    while(hh<=tt){
        for(int i=0;i<4;i++){
            if(tx==ex && ty==ey){
                cout<<q[tt].step;
                exit(0);
            }
            tx=q[hh].x+dx[i];
            ty=q[hh].y+dy[i];
            if(tx<1 || tx>n || ty<1 || ty>n)continue;
            if(!st[tx][ty]){
                tt++;
                q[tt].x=tx;
                q[tt].y=ty;
                q[tt].step=q[hh].step+1;
                st[tx][ty]=1;
            }

        }
        hh++;
    }
}

int main(){
    cin>>n;
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c;
            g[i][j]=c-'0';
        }
    }
    cin>>sx>>sy>>ex>>ey;
    bfs(sx,sy);
    return 0;
}

by _Panyc @ 2024-07-04 09:22:22

改

by Apollo0130 @ 2024-07-04 09:22:45

@_Panyc 最主要的错是什么

by _Panyc @ 2024-07-04 09:26:04

1.队列不够规范啊\ 2.数组小了

by Apollo0130 @ 2024-07-04 09:31:08

我最初的代码把对列改大之后也有80分了

感谢大佬

黑色是队列 白色是我

by Apollo0130 @ 2024-07-04 09:32:00

白色还有 @ _Panyc

by Handezheng @ 2024-07-04 10:27:48

@zlf201101
你会用STL的队列吗？

by Apollo0130 @ 2024-07-04 20:43:41

@Handezheng 我用的是数组队列

by Apollo0130 @ 2024-07-04 20:44:09

@Handezheng 我这样改完之后AC了

by Apollo0130 @ 2024-07-04 20:44:43

@Handezheng 谢谢大佬的建议