洛谷 P1443 马的遍历

题目链接

思路：

要求到一个点，马最少走多少步。bfs 从起点往四周辐射，最先达到的点，就是最短距离（最少的步数）。所以这题就是典型的 bfs，通过队列来做。

对于一个结点 Pos（取队首），根据中国象棋马走斜日的规则，我们可以判断有八个方向，分别遍历八个方向能够到达的点。如果遍历到的这个点 New_pos 满足两个条件：

没有遍历过。是一个新鲜的点。vis 数组中值为初始值 0 。使数组不越界！

那么它就是一个新的结点，将它在 vis 数组中标记后入队。它的 level （从起点到这个点是第几层，即需要走几步）就是前面那个节点 Pos 的 level +1。

点 Pos 的八个方向都遍历完成之后，就将 Pos 出队，然后遍历新的队列头结点。因为 Pos 在最开始入队的时候就标记过 vis 数组，所以它肯定不会再入队。

当所有能够到达的点都在 vis 数组中标记完成，队列就是空的了。（BFS套路）

bfs 完成。

实现细节：

马行走的八个方向。画个图就能够理解。用 dx[] 数组和 dy[] 表示位置的变换。马在的初始位置，到达的步数应该是 0 。但是如果在将初始节点入队的时候，将 level 设置为 0，那么后面有可能还会遍历到这个点，造成错误。我的解决办法是将初始节点的 level 设置为 1 ，那么后面输出答案时，所有的 level 都要 -1。数组是否越界的判断很重要！而且容易忘……在输出时要判断，如果是初始数据，则输出 0 ；如果是不能到达的点 vis[i][j] == 0，则输出 -1；其他情况则输出 vis[i][j] - 1。最后也是最重要的，输出格式。题目要求是每个答案占五格。那么，如果答案是初始数据的 0 ，后面就要跟 4 个空格；如果答案是 -1 ，后面就要跟三个空格；同理，其他情况中对一位数答案，二位数答案，三位数答案，后面都要跟相应位置的空格。

代码：

#include<bits/stdc++.h> using namespace std; int gra[405][405]; int vis[405][405]; struct point{ int x; int y; int level; }; int dx[]={-2,-1,1,2,2,1,-1,-2};// 马走斜日，移动方位 int dy[]={1,2,2,1,-1,-2,-2,-1}; queue<point> q; // 入队的都是标记过的点；已经标记过的点不再入队（入队前检测）； // 直到将所有能遍历到的点都入队完后，队空，则遍历完成 // 此时，vis 数组仍为 0 的是不可到达的点； int m,n; void bfs(){ while(!q.empty()){ point pos=q.front(); int x=pos.x; int y = pos.y; int level = pos.level; for(int i=0;i<8;i++){ int x_new = x + dx[i]; int y_new = y + dy[i]; // 判断数组是否越界？ if(x_new<=n && x_new>0 && y_new>0 && y_new<=m){ if(vis[x_new][y_new]==0){// 没遍历过，应入队 point new_pos = {x_new,y_new,level+1}; vis[x_new][y_new] = level+1;// 标记 q.push(new_pos); } } } // 8 个方向都遍历过之后， 将这个点出队； q.pop(); } } int main(){ int start_x,start_y; cin>>n>>m; cin>>start_x>>start_y; point start={start_x,start_y,1};// 首位应该是0 ，但是为了方便标记。后面输出再处理 q.push(start); vis[start.x][start.y] = start.level;//标记，最后输出的就是这个数组 bfs(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(i==start_x && j==start_y){ cout<<0<<" "; } else if(vis[i][j]==0){ cout<<-1<<" "; } else{ int ans = vis[i][j]-1;// 因为第一步设为 1；所以后面每一步都多了 1 if(ans<10) cout<<ans<<" "; else if(ans>=10 && ans <= 99) cout<<ans<<" "; else if(ans>=100) cout<<ans<<" "; } } cout<<endl; } return 0; }

最后：

突然才发现，洛谷虽然只能下载部分数据，但是对于每一个错误点其实都会给出提示。鼠标移到 WA 那的时候会有一段话出现，提示错误在哪一行哪一列，输出的错误答案是什么，正确答案 expected 是多少。

由于这些话是英文，以前都是当没看到或者看不懂，一头雾水，直接忽略。直到今天才发现其中玄妙。可见学好英语真的很重要啊！