手打 bfs，又带 TLE 又带 MLE，10pts，求调！

ImposterAnYu @ 2021-11-05 23:31:22

#include<bits/stdc++.h>
using namespace std;
const int dx[9] = {0,-1,1,0,0};
const int dy[9] = {0,0,0,-1,1};
int n,x,y,xx,yy,i,j,sx,sy,w[1005][1005];
char ch;
struct i_dont_like_bfs{
    int xxx,yyy,s;
} now,nex;
queue<i_dont_like_bfs> a;
int bfs(){
    now.xxx = x;
    now.yyy = y;
    w[x][y] = 114514,w[xx][yy] = 1919810;
    a.push(now);
    while(!a.empty()){
        now = a.front();
        a.pop();
        for(i = 1; i <= 4; i++){
            sx = now.xxx + dx[i];
            sy = now.yyy + dy[i];
            if(max(sx,sy) <= n && min(sx,sy) >= 1 && (!w[sx][sy] || w[sx][sy] == 1919810)){
                nex.xxx = sx;
                nex.yyy = sy;
                nex.s = now.s + 1;
                w[now.xxx][now.yyy] = 114514;
                if(w[sx][sy] == 1919810){
                    return nex.s;
                }
                a.push(nex);
            }
        }
    }
}
int main(){
    cin >> n;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            ch = getchar();
            while(ch < '0' || ch > '1'){
                ch = getchar();
            }
            w[i][j] = (ch == '1');
        }
    }
    cin >> x >> y >> xx >> yy;
    cout<< bfs() << endl;
    return 0;
}

by qwq___qaq @ 2021-11-05 23:39:13

@ImopsterAnYu 确实没看懂您怎么写的

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,n,ans=1e7,vis[1005][1005];
char s[1005][1005];
struct node{
    int a,b,c;
};
void bfs(){
    queue<node> q;
    q.push(node({a,b,0}));
    while(!q.empty()){
        int x=q.front().a,y=q.front().b,t=q.front().c;
        q.pop();
        if(x<1||x>n||y<1||y>n||s[x][y]=='1'||t>=ans)
            continue;
        if(vis[x][y]!=-1&&t>=vis[x][y])
            continue;
        vis[x][y]=t;
        if(x==c&&y==d){
            ans=t;
            continue;
        }
        q.push(node({x-1,y,t+1}));
        q.push(node({x+1,y,t+1}));
        q.push(node({x,y-1,t+1}));
        q.push(node({x,y+1,t+1}));
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>s[i][j],vis[i][j]=-1;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    bfs();
    printf("%d\n",ans);
    return 0;
}

by ImposterAnYu @ 2021-11-05 23:46:15

@pengzijun az，谢谢了，我再调一下……

by Chang_Pei @ 2021-11-06 12:53:00

@ImopsterAnYu 我也实在是看不懂，附上丑陋代码

#include <bits/stdc++.h>
using namespace std;
struct Nobe {
  int x, y, step;
} a[1000005];
char q[1005][1005];
bool flag[1005][1005];
int n, sx, sy, zx, zy;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int bfs(int sx, int sy) {
  int head = 1, tail = 1;
  a[tail].x = sx;
  a[tail].y = sy;
  a[tail].step = 0;
  tail++;
  flag[sx][sy] = 1;
  int nx, ny;
  while (1) {
    Nobe h = a[head];
    if (h.x == zx && h.y == zy) {
      return h.step;
    }
    for (int i = 0; i <= 3; i++) {
      nx = h.x + dx[i];
      ny = h.y + dy[i];
      if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && q[nx][ny] == '0' && flag[nx][ny] == 0) {
        a[tail].x = nx;
        a[tail].y = ny;
        a[tail].step = h.step + 1;
        tail++;
        flag[nx][ny] = 1;
      }
    }
    head++;
  }
}
int main() {
  int ans = -1;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> q[i][j];
    }
  }
  cin >> sx >> sy >> zx >> zy;
  ans = bfs(sx, sy);
  cout << ans;
  return 0;
}