两个点TLE求助(普通BFS写法)

P1443 马的遍历

修改后没问题了,但是不明白为什么搜到(m,n)就能把所有点都搜到? ```cpp #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<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)); bfs(n,m); 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; } ```
by Simon_Lu @ 2022-05-25 23:30:55


@[Simon_Lu](/user/222555) 这道题应该是从左上角往右下角搜,所以(m,n)就是能搜到的最远的一个点,也就是说到了(m,n)就把整个图都搜过了。
by Qiancy1427 @ 2022-05-26 16:35:46


@[Qiancy1427](/user/478917) 栓Q
by Simon_Lu @ 2022-05-26 22:39:55


|