水题TLE求助

花里心爱 @ 2018-09-15 17:03:43

by Nova_守门员 @ 2018-09-15 17:05:37

Orz

by 风翮雨翎 @ 2018-09-15 17:17:03

emmmmmmmmmmmmm

by emming @ 2018-09-15 18:10:24

嗯巨佬都认为黄题是水题

我可以AFO了

by 花里心爱 @ 2018-09-15 18:10:56

@emming 不就是bfs吗……

别告诉我您不会

by Rbu_nas @ 2018-09-15 18:11:01

看不懂，溜了溜了

by emming @ 2018-09-15 18:11:59

@Irressey 嗯蒟蒻我不会【认真】

by Rbu_nas @ 2018-09-15 18:12:22

这位和您差不多@Irressey

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
using namespace std;

int n,x1,x2,y1,y2;
char a[1010][1010],b[1010][1010];
int head,tail,sum[1010][1010],list[1110000][2];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool vis[1010][1010];

bool ok(int x,int y) {
    return x>=1&&y>=1&&x<=n&&y<=n;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%s",b[i]);
    for(int i=1;i<=n;i++)   
        for(int j=1;j<=n;j++)
            a[i][j]=b[i-1][j-1];
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    list[1][0]=x1,list[1][1]=y1;
    head=tail=1,sum[x1][y1]=0,vis[x1][y1]=true;
    while(head<=tail) {
        int x=list[head][0],y=list[head][1];
        if(x==x2&&y==y2) break;
        for(int i=0;i<4;i++) {
            int nx=x+dx[i],ny=y+dy[i];
            if(!ok(nx,ny)||vis[nx][ny]||a[nx][ny]=='1') continue;
            tail++; list[tail][0]=nx,list[tail][1]=ny;
            vis[nx][ny]=true; sum[nx][ny]=sum[x][y]+1;
        }
        head++;
    }
    printf("%d\n",sum[x2][y2]);
    return 0;
}

by 花里心爱 @ 2018-09-15 18:14:13

@AC我最萌 所以这个是A了还是T了

by Rbu_nas @ 2018-09-15 18:14:54

@Irressey 当然是A的哇...

by Rbu_nas @ 2018-09-15 18:15:24

@Irressey queue还不如手写一个维护