题目链接：

题目描述

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入格式

一行四个数据，棋盘的大小和马的坐标

输出格式

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0    3    2    3    -1   1    2    1    4

---

题解

此题是典型的BFS问题。不过和有两点不同：一是马的走法不是上下左右，所以pos数组需要修改，二是走的步数需要从队列中元素的步数加1。还有一个小问题就是要控制cout的输出格式，刚开始没有注意，10个全WA了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6  7 using namespace std; 8  9 struct Node10 {11     int x, y;12     int step;13 };14 Node q[100005];15 16 const int MAXN = 1005;17 int n, m, a, b, c, d, step, front, rear, ans[MAXN][MAXN]; 18 int pos[8][2] = {
   2, 1, 2, -1, 1, 2, 1, -2, -1, 2, -1, -2, -2, 1, -2, -1};19 bool vis[MAXN][MAXN];20 21 void bfs()22 {23     Node now, next;24     now.x = a;25     now.y = b;26     vis[a][b] = 1; 27     now.step = 0;28     front = rear = 0;29     q[rear] = now;30     rear++;31     while(front < rear)32     {33         now = q[front++];34         for(int i = 0; i < 8; i++)35         {36             int nx = now.x + pos[i][0]; 37             int ny = now.y + pos[i][1]; 38             if(nx <= n && nx > 0 && ny <= m && ny > 0 39                 && vis[nx][ny] == false) 40             {41                 vis[nx][ny] = true;42                 q[rear].x = nx;43                 q[rear].y = ny;44                 q[rear].step = now.step + 1;45                 ans[nx][ny] = q[rear].step;46                 rear++;47             }48         } 49     }50 }51 52 int main()53 {54     cin >> n >> m >> a >> b;55     for(int i = 1; i <= n; i++)56     {57         for(int j = 1; j <= m; j++)58         {59             ans[i][j] = -1;60         }61     }62     ans[a][b] = 0;63     step = 1;64     bfs();65     for(int i = 1; i <= n; i++)66     {67         for(int j = 1; j <= m; j++)68         {69             cout.width(5);70             cout.setf(ios::left);71             cout << ans[i][j];72         }73         cout << endl;74     }75     return 0;76 }