题目描述

https://www.acwing.com/problem/content/2550/

C++ 代码

// bfs
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 305;
typedef pair<int, int> PII;

int n, k;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dr[3] = {2, 1, 0}; // 胖子的半径
bool st[N][N];
struct Node{
    int x, y, netime;
};


int bfs()
{
    queue<Node> q;
    q.push({3, 3, 0});
    st[3][3] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        if(t.x == n - 2 && t.y == n - 2) return t.netime;

        if(t.netime / k < 2) q.push({t.x, t.y, t.netime + 1}); // 胖子占1x1才可以走，其他情况都有可能走不了
        for(int i = 0; i < 4; i ++)
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            int fat;
            if(t.netime / k >= 2){
                fat = dr[2];
            }
            else if(t.netime / k < 2 && t.netime / k >= 1){
                fat = dr[1];
            }
            else fat = dr[0];

            if(x - fat < 1 || x + fat > n || y - fat < 1 || y + fat > n) continue;  
            if(st[x][y]) continue;

            // 判断胖子所在范围有无障碍物
            bool flag = false;
            for(int j = x - fat; j <= x + fat; j ++)
                for(int k = y - fat; k <= y + fat; k ++)
                    if(g[j][k] == '*') flag = true;

            if(flag) continue;
            q.push({x, y, t.netime + 1});
            st[x][y] = true;
        }
    }
    return -1;
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        cin >> g[i] + 1;

    int res = bfs();

    cout << res << endl;
    return 0;
}