中国象棋-马-有障碍

题目

现有一个n∗m​​​​大小的棋盘，在棋盘的第x行第y​​列的位置放置了一个棋子，其他位置中的一部分放置了障碍棋子。棋子的走位参照中国象棋的“马”（障碍棋子将成为“马脚”）。求该棋子到棋盘上每个位置的最小步数。

注1：中国象棋中“马”的走位为“日”字形，如下图所示。

注2：与“马”直接相邻的棋子会成为“马脚”，“马”不能往以“马”=>“马脚”为长边的方向前进，如下图所示。

思考

利用bfs遍历，最主要的就是处理障碍问题。注意到长边方向前进，前面有障碍的话，就会导致马撇脚。例如上图4*4的棋盘，点坐标为（x，y），马在（2，2），障碍在（3，2），马需要向（1，4）去，则增长量为dx = 2，dy = -1，此时x方向增长量多，即为长边，马在x轴的方向上，有障碍，那么马就不能过去。增量最长也就为2，最小为1，用一个map<PII（坐标）,bool> block来存储障碍，所以障碍阻挡了前进的条件判断条件为

block[PII(temp.first + dx[i] / 2,temp.second + dy[i] / 2)]) == true；代表有障碍阻挡了前进方向

!block[PII(temp.first + dx[i] / 2,temp.second + dy[i] / 2)]) == false；代表在前进方向上没有障碍

代码

#include <iostream>
#include <queue>
#include <cstring>
#include <map>

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int n,m,startX,startY;
int k;
//存储障碍坐标
map<PII,bool> block;

int cnt = 0;
int dx[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int ans[N][N];
bool st[N][N];

bool check(int x,int y)
{
    //点不能出界 且 点的位置上不能有障碍 且 点未被访问过
    return x >= 0 && x < n && y >= 0 && y < m && !block[PII(x,y)] && !st[x][y];
}

void bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    st[x][y] = true;
    ans[x][y] = 0;
    while(!q.empty())
    {
        int size = q.size();
        while(size--)
        {
            PII temp = q.front();
            ans[temp.first][temp.second] = cnt;
            q.pop();
            for(int i = 0;i < 8;i++)
            {
                int nextX = temp.first + dx[i];
                int nextY = temp.second + dy[i];
                //判断点的合法性 且 在长增量上不能有障碍
                if(check(nextX,nextY) && !block[PII(temp.first + dx[i] / 2,temp.second + dy[i] / 2)])
                {
                    st[nextX][nextY] = true;
                    q.push({nextX,nextY});
                }
            }
        }
        cnt++;
    }
}

int main()
{
    cin>>n>>m>>startX>>startY;
    cin>>k;
    for(int i = 0;i < k;i++)
    {
        int x,y;
        cin>>x>>y;
        //存储障碍坐标
        block[PII(x - 1,y - 1)] = true;
    }
    memset(ans,-1,sizeof(ans));

    bfs(startX - 1,startY - 1);

    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++)
            if(j == m - 1) cout<<ans[i][j]<<endl;
            else cout<<ans[i][j]<<" ";

    return 0;
}