題目描述

傳送門：https://www.luogu.com.cn/problem/P1443
有一個n*m的棋盤(1<n,m<=400)，在某個點上有一個馬,要求你計算出馬到達棋盤上任意一個點最少要走幾步

輸入格式

一行四個數據，棋盤的大小和馬的坐標

輸出格式

一個n*m的矩陣，代表馬到達某個點最少要走幾步（左對齊，寬5格，不能到達則輸出-1）

輸入樣例

3 3 1 1

輸出樣例

0 3 2 3 -1 1 2 1 4

棋盤最少步數到達某個點，比較常見的廣度優先搜索（BFS）。首先馬走日，體現在棋盤上，就是在不越界的情況下遍歷八個方向，這個以dx，dy數組定義方向。首先將馬的節點入隊，該點記錄步數為0，同時vis數組記錄已經訪問。之后遍歷八個方向，如果滿足條件，將新節點入隊，同時該節點步數為上一個節點步數加1，vis數組記錄已遍歷，直至隊列為空，將馬可以走到的點全部遍歷完。
題目為比較常規的BFS，首先初始化棋盤均為-1，即初始狀態全部不可達，最后輸出注意左對齊的輸出，這里使用printf的“-5d"格式化輸出。

#include<bits/stdc++.h> using namespace std; int dx[] = { 2,2,-2,-2,1,1,-1,-1 }; int dy[] = { -1,1,-1,1,-2,2,2,-2 }; struct point {int x, y; }node; point top; queue<point>que; int n, m, hx, hy; int mapp[405][405]; bool vis[405][405];void bfs(int x, int y) {mapp[x][y] = 0;vis[x][y] = true;//已入隊node.x = x;node.y = y;que.push(node);while (!que.empty()){top = que.front();//頭節點獲取que.pop();//出隊for (int i = 0; i < 8; i++){int newx = top.x + dx[i];int newy = top.y + dy[i];if (newx<1 || newx>n || newy<1 || newy>m) continue;if (!vis[newx][newy]){node.x = newx;node.y = newy;//cout << node.x << " " << node.y << endl;que.push(node);vis[newx][newy] = true;mapp[newx][newy] = mapp[top.x][top.y] + 1;}}} }int main() {cin >> n >> m >> hx >> hy;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)mapp[i][j] = -1;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)vis[i][j] = false;bfs(hx, hy);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++)printf("%-5d", mapp[i][j]);cout << endl;}return 0; }

總結

以上是生活随笔為你收集整理的【洛谷】马的遍历--广度优先搜索（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。