P1443 马的遍历

思路：

BFS模版题

nxt表示方向数组，一共八个方向

省去vis/book标记数组，直接用e[i][j]==-1来判断

#include<bits/stdc++.h>
#define M 405
using namespace std;
int e[M][M],n,m,sx,sy;
int nxt[8][2]={{-2,1},{-1,2},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2}}; 
struct node{int x,y;
};void bfs()
{queue<node> q;node head;int tx,ty;e[sx][sy]=0;q.push({sx,sy});while(!q.empty()){head=q.front(); q.pop();for(int i=0;i<8;++i){tx=head.x+nxt[i][0];ty=head.y+nxt[i][1];if(tx<1||ty<1||tx>n||ty>m) continue;if(e[tx][ty]==-1){e[tx][ty]=e[head.x][head.y]+1;q.push({tx,ty});}}}
}int main()
{cin>>n>>m>>sx>>sy;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)e[i][j]=-1;bfs();for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){printf("%d ",e[i][j]);}printf("\n");}return 0;
}