2020 CCPC Wannafly Winter Camp Day6 Div.12——L.你吓到我的马了.jpg【BFS】

题目传送门

题目描述

给定一个 $n\times m$ 的棋盘，棋盘上有很多障碍和一个中国象棋中的马（本题中马的移动方式跟中国象棋中的马完全一致）。
马每次移动首先会选择是上下左右中的某个不被卡马脚（卡马脚的定义在下面）的方向并面朝这个方向，然后再选择跳到左前方或者右前方，其中左前方是前面两格，左边一格的地方，右前方是前面两格，右边一格的地方。
然后马的移动有以下这么几个条件限制：
马不能跳到障碍上或者跳出棋盘
当马在某个方向上的前面一个格子有障碍的话，那么我们称马在这个方向上被卡了马脚
现在对于棋盘上的每个点，你需要输出马最少跳几次能跳到这个地方，如果不可能跳到这个地方则输出
$?1$.

输入描述:

第一行两个正整数 $n,m$ 表示棋盘大小
接下来 $n$ 行，每行一个长度为 {m}m 的字符串，表示地图
第 $i$ 行第 $j$ 列的格子由第 $i$ 行的字符串的第 $j$ 个（从 $1$ 开始计算）字符决定，若是 $.$ 则表示是空格子， $X$ 表示障碍，$M$表示马，数据保证马有且只有一个。$2\le n,m\le 100$

输出描述:

输出 $n$ 行，每行 $m$ 个数，第 $i$ 行第 $j$ 个数表示跳到第 $i$ 行第 $j$ 列至少需要几步，如果不可能跳到则输出 $?1$。

输入

3 3
.M.
…
.X.

输出

-1 0 -1
-1 -1 -1
1 -1 1

题解

AC-Code

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e2 + 5;int dx[] = {
     -1,-2,-2,-1,1,2,2,1 };
int dy[] = {
     2,1,-1,-2,-2,-1,1,2 };struct Node {
    int x, y;Node(int x, int y) :x(x), y(y) {
    }
};int n, m;
char mp[maxn][maxn];
int vis[maxn][maxn];bool check(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m)	return false;if (mp[x][y] == 'X' || vis[x][y] > 0)	return false;return true;
}void bfs(int now_x, int now_y) {
    queue<Node>q;q.push(Node{
     now_x,now_y });vis[now_x][now_y] = 1;while (!q.empty()) {
    int x = q.front().x;int y = q.front().y;q.pop();for (int i = 0; i < 8; ++i) {
    int nx = x + dx[i];int ny = y + dy[i];switch (i){
    case 7:case 0:if (mp[x][y + 1] == 'X')	continue;break;case 1:case 2:if (mp[x - 1][y] == 'X')	continue;break;case 3:case 4:if (mp[x][y - 1] == 'X')	continue;break;case 5:case 6:if (mp[x + 1][y] == 'X')    continue;break;}if (check(nx, ny)) {
    q.push(Node{
     nx,ny });vis[nx][ny] = vis[x][y] + 1;}}}
}int main() {
    while (cin >> n >> m) {
    memset(vis, 0, sizeof vis);int x, y;for (int i = 1; i <= n; ++i) {
    string s;	cin >> s;for (int j = 1; j <= m; ++j) {
    mp[i][j] = s[j-1];if(mp[i][j] == 'M')x=i,y=j;}}bfs(x, y);for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) cout << vis[i][j] - 1 << " ";puts("");}}
}