救救孩子吧 玄关

yjjh @ 2024-07-03 17:15:37

#include <bits/stdc++.h>
using namespace std;
const int N=1002;
int dt[N][N],n,x2,y2;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int q[100000000][3];
int tt=0,rr=1;
inline int bbfs(int x,int y,int bs){
    for(int i=0;i<4;i++){
        if(x+xx[i]>=1&&x+xx[i]<=n&&y+yy[i]>=1&&y+yy[i]<=n&&dt[x+xx[i]][y+yy[i]]==0){
            rr++;
            if(x+xx[i]==x2&&y+yy[i]==y2)return bs+1;
            q[rr][0]=x+xx[i],q[rr][1]=y+yy[i],q[rr][2]=bs+1,dt[x+xx[i]][y+yy[i]]=1;
        }
    }
    return 0;
}
inline int bfs(){
    while(rr>=tt){
        int t=bbfs(q[tt][0],q[tt][1],q[tt][2]);
        if(t)return t;
        tt++;
    }
}
int main(){
    std::cin >>n;
    for(int i=0;i<n;i++){
        string str;
        std::cin >>str;
        for(int j=0;j<n;j++){
            dt[i][j]=str[j]-'0';
        }
    }
    int x,y;
    std::cin >>x>>y>>x2>>y2;
    q[0][0]=x,q[0][1]=y;

    std::cout <<bfs();
    return 0;
}

by silhouettel @ 2024-07-03 17:21:03

@yjjh bfs题建议用queue，模拟队列可能会炸，除非算清了状态数或者写节点回收

by yjjh @ 2024-07-03 17:30:50

@silhouettel 谢谢，已改：

#include <iostream>
#include <queue>
using namespace std;
const int N=1002;
int dt[N][N],n,x2,y2;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
std::queue<int>q1;
std::queue<int>q2;
std::queue<int>q3;
inline int bbfs(int x,int y,int bs){
    for(int i=0;i<4;i++){
        if(x+xx[i]>=1&&x+xx[i]<=n&&y+yy[i]>=1&&y+yy[i]<=n&&dt[x+xx[i]][y+yy[i]]==0){
            if(x+xx[i]==x2&&y+yy[i]==y2)return bs+1;
            q1.push(x+xx[i]);q2.push(y+yy[i]);q3.push(bs+1),dt[x+xx[i]][y+yy[i]]=1;
        }
    }
    return 0;
}
inline int bfs(){
    while(q1.size()){
        int t=bbfs(q1.front(),q2.front(),q3.front());
        if(t)return t;
        q1.pop();q2.pop();q3.pop();
    }
}
int main(){
    std::cin >>n;
    for(int i=0;i<n;i++){
        string str;
        std::cin >>str;
        for(int j=0;j<n;j++){
            dt[i][j]=str[j]-'0';
        }
    }
    int x,y;
    std::cin >>x>>y>>x2>>y2;
    q1.push(x);q2.push(y);q3.push(0);
    std::cout <<bfs();
    return 0;
} 

可是还是一样啊。。。

by silhouettel @ 2024-07-03 18:28:36

@yjjh
帮你改了一个地方 现在大抵是能过的
你输入的时候下标是从0开始的
但是bfs的时候是从1开始的

#include <iostream>
#include <queue>
using namespace std;
const int N=1011;
int dt[N][N],n,x2,y2;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
std::queue<int>q1;
std::queue<int>q2;
std::queue<int>q3;
inline int bbfs(int x,int y,int bs){
    for(int i=0;i<4;i++){
        if(x+xx[i]>=1&&x+xx[i]<=n&&y+yy[i]>=1&&y+yy[i]<=n&&dt[x+xx[i]][y+yy[i]]==0){
            if(x+xx[i]==x2&&y+yy[i]==y2)return bs+1;
            q1.push(x+xx[i]);q2.push(y+yy[i]);q3.push(bs+1),dt[x+xx[i]][y+yy[i]]=1;
        }
    }
    return 0;
}
inline int bfs(){
    while(q1.size()){
        int t=bbfs(q1.front(),q2.front(),q3.front());
        if(t) return t;
        q1.pop();q2.pop();q3.pop();
    }
}
int main(){
    std::cin >>n;
    for(int i=0;i<n;i++){
        string str;
        std::cin >>str;
        for(int j=0;j<n;j++){
            dt[i + 1][j + 1]=str[j]-'0';
        }
    }
    int x,y;
    std::cin >>x>>y>>x2>>y2;
    q1.push(x);q2.push(y);q3.push(0);
    std::cout <<bfs();
    return 0;
}

by yjjh @ 2024-07-04 08:32:38

@silhouettel 谢谢大佬！AC，已关！

by _Panyc @ 2024-07-04 09:06:21

不是你为什么要在std里调用std???