求助BFS

⚡zhangjingcan⚡ @ 2020-08-30 17:12:50

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    char c = getchar();
    int x = 0;
    bool f = 0;
    while (!isdigit(c)) f ^= !(c ^ 45), c = getchar();
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    if (f) x = -x;
    return x;
}
const int N = 1e3 + 10;
int step[N][N];
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
struct Node {
    int x, y;
} Q[N * 2];
char a[N][N];
int n, sx, sy, ex, ey;
int bfs() {
    int head = 0, tail = 0;
    Q[tail].x = sx;
    Q[tail++].y = sy;
    memset(step, -1, sizeof(step));
    step[sx][sy] = 0;
    while (head < tail) {
        Node Tx = Q[head++];
        if (Tx.x == ex && Tx.y == ey) return step[ex][ey];
        for (int i = 0; i < 4; i++) {
            int px = Tx.x + dx[i];
            int py = Tx.y + dy[i];
            if (px < 1 || px > n || py < 1 || py > n) continue;
            if (a[px][py] == '1' || a[px][py] > -1) continue;
            step[px][py] = step[Tx.x][Tx.y] + 1;
            Q[tail].x = px, Q[tail++].y = py;
        }
    }
    return -1;
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    sx = read(), sy = read();
    ex = read(), ey = read();
    printf("%d\n", bfs());
    return 0;
}

by ⚡zhangjingcan⚡ @ 2020-08-30 17:13:24

@zhangjingcan 本人经常眼瞎

by Purslane @ 2020-08-30 20:22:17

a[px][py] > -1什么鬼？

by Purslane @ 2020-08-30 20:22:29

@zhangjingcan

by Purslane @ 2020-08-30 20:26:57

为什么要按照老师模板写呢？我喜欢手写双队列……

by Purslane @ 2020-08-30 20:37:57

看我清奇的马蜂

#include<bits/stdc++.h>
using namespace std;
inline bool id(const char ch) {
    return ch>='0'&&ch<='9';
}
inline int read(void) {
    int s=0;
    char ch=getchar();
    while(!id(ch)) ch=getchar();
    while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return s;
}
const int MAXN=1000+10;
int n,h,t,sx,sy,ex,ey,x[MAXN*MAXN],y[MAXN*MAXN],st[MAXN][MAXN],step[MAXN*MAXN]; 
const int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
void bfs() {
    h=1;
    x[++t]=sx,y[t]=sy;
    while(h<=t) {
        int tmpx=x[h],tmpy=y[h++];
        for(int i=1;i<=4;i++) {
            int xx=tmpx+dx[i],yy=tmpy+dy[i];
            if(!st[xx][yy]) continue;
            st[xx][yy]=0;
            x[++t]=xx,y[t]=yy,step[t]=step[h-1]+1;
            if(xx==ex&&yy==ey) {
                printf("%d",step[t]);
                exit(0);
            } 
        }
    }
}
int main() {
    n=read();
    for(int i=1;i<=n;i++) {
        string tmp;
        cin>>tmp;
        for(int j=0;j<n;j++) if(tmp[j]=='0') st[i][j+1]=1;
    }
    sx=read(),sy=read(),ex=read(),ey=read();
    bfs();
    printf("Chuxu AK IOI!!!");
    return 0;
}