P1443马的遍历

一.题目描述：

 二.解题思路：

马在象棋中是走日的，所以根据这个特点可以写出八个方向，用bfs解决即可，需要注意的是，不需要每一个点都枚举，不然T两个点。可以跑一次就做完所有事情，然后为distance为0的就是不能到达的输出-1即可。

三.代码实现：

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 int dt[500][500];
 4 int bk[500][500];
 5 int mv[8][2] = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-2,-1},{-1,-2}};
 6 int n,m,x,y;
 7 struct node{
 8     int x;
 9     int y;
10     int s;
11 };
12 node u;
13 void bfs()
14 {
15     queue  ans;
16     ans.push(u);
17     int head = 1;
18     int tail = 2;
19     while(head < tail){
20         node v = ans.front();
21         ans.pop();
22         dt[v.x][v.y] = v.s;
23         for(int i = 0;i < 8;i++){
24             int dx = mv[i][0] + v.x;
25             int dy = mv[i][1] + v.y;
26             if(dx < 1 || dx > n || dy < 1 || dy > m) continue;
27             if(bk[dx][dy]) continue;
28             node w;
29             bk[dx][dy] = 1;
30             w.x = dx;
31             w.y = dy;
32             w.s = v.s + 1;
33             ans.push(w);
34             tail++;
35         }
36         head++;
37     }
38 }
39 int main()
40 {
41     cin >> n >> m >> x >> y;
42     u.x = x;
43     u.y = y;
44     u.s = 0;
45     dt[x][y] = 0;
46     bk[x][y] = 1;
47     bfs();
48     for(int i = 1;i <= n;i++){
49         for(int j = 1;j <= m;j++){
50             if(dt[i][j] == 0 && (i != x || j != y))
51                 printf("%-5d",-1);
52             else 
53                 printf("%-5d",dt[i][j]);
54         }
55         printf("\n");
56     }
57     return 0;
58 }