诡异MLE

xXyhhyhhXX @ 2024-06-29 11:41:42

#include <iostream>
#include <queue>
using namespace std;
struct Point{
    int x,y,step;
};
int s[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
Point tPoint(int x,int y,int step){
    Point a;
    a.x=x;
    a.y=y;
    a.step=step;
    return a;
}
queue<Point> list;
bool map[1005][1005];
int x1,y1,x2,y2,n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            char c;
            cin>>c;
            if(c=='0'){
                map[i][j]=1;
            }
        }
    }
    cin>>x1>>y1>>x2>>y2;
    list.push(tPoint(x1-1,y1-1,0));
    while(!list.empty()){
        Point t=list.front();
        list.pop();
        map[t.x][t.y]=0;
        //cout<<t.x<<" "<<t.y<<" "<<t.step<<endl;
        if((t.x==x2-1)&&(t.y==y2-1)){
            cout<<t.step<<endl;
            return 0;
        }
        for(int i=0;i<4;i++){
            int px=t.x+s[i][0],py=t.y+s[i][1];
            if((px<n||px>=0||py<n||py>=0)&&map[px][py]){
                list.push(tPoint(px,py,t.step+1));
            }
        }
        //cout<<list.size()<<endl;
    }
    return 0;
} 

by xXyhhyhhXX @ 2024-06-29 11:42:18

玄二关

by wangzhongqian @ 2024-06-29 12:28:06

@xXyhhyhhXX

#include <iostream>
#include <queue>
using namespace std;
struct Point {
    int x, y, step;
};
int s[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
Point tPoint(int x, int y, int step) {
    Point a;
    a.x = x;
    a.y = y;
    a.step = step;
    return a;
}
queue<Point> list;
bool map[1005][1005];
int x1, y1, x2, y2, n;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char c;
            cin >> c;
            if (c == '0') {
                map[i][j] = 1;
            }
        }
    }
    cin >> x1 >> y1 >> x2 >> y2;
    list.push(tPoint(x1 - 1, y1 - 1, 0));
    while (!list.empty()) {
        Point t = list.front();
        list.pop();
//      map[t.x][t.y]=0;
        //cout<<t.x<<" "<<t.y<<" "<<t.step<<endl;
        if ((t.x == x2 - 1) && (t.y == y2 - 1)) {
            cout << t.step << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int px = t.x + s[i][0], py = t.y + s[i][1];
            if ((px < n && px >= 0 && py < n && py >= 0) && map[px][py]) {//用&&
                list.push(tPoint(px, py, t.step + 1));
                map[px][py] = 0;//在这就改成0
            }
        }
        //cout<<list.size()<<endl;
    }
    return 0;
}

by yx666 @ 2024-06-29 12:42:19

@xXyhhyhhXX

加个 vis[1024][1024] 判断走没走过，走过的节点就不走了。

by xXyhhyhhXX @ 2024-06-29 19:48:13

@wangzhongqian thx,已关

by xXyhhyhhXX @ 2024-06-29 19:48:31

@yx666 thx,已关