两个点TLE求助(普通BFS写法)
查看原帖
两个点TLE求助(普通BFS写法)
222555
Simon_Lu楼主2022/5/25 23:28

rt

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,head,tail;
int d[11][2]={1,2,2,1,1,-2,-2,1,-1,-2,-2,-1,-1,2,2,-1};
int ans[405][405];
bool book[405][405];
struct T{
    int x,y,step;
    T(){}
    T(const int &_x,const int &_y,const int &_step):x(_x),y(_y),step(_step){}
}q[160005];
void init(){
    memset(book,0,sizeof(book));
}
void bfs(int a,int b){
    init();
    book[x][y]=1;
    head=tail=1;
    q[tail++]=T(x,y,0);
    while(head<tail){
        T old=q[head++];
        for(int i=0;i<12;i++){
            int newx=old.x+d[i][0];
            int newy=old.y+d[i][1];
            if(newx==a&&newy==b){
                ans[a][b]=old.step+1;
                return;
            }
            if(newx<1||newx>n||newy<1||newy>m||book[newx][newy])
                continue;
            ans[newx][newy]=old.step+1;
            book[newx][newy]=1;
            q[tail++]=T(newx,newy,old.step+1);
        }
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&x,&y);
    memset(ans,-1,sizeof(ans));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            bfs(i,j);
    }
    ans[x][y]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%-5d",ans[i][j]);
        cout<<endl;
    }
    return 0;
}
2022/5/25 23:28
加载中...