Solution_AT2375

_FL_ · 2022-05-01 11:49:24 · 题解

\texttt{AT2375}

思路：

第一道自己做出的 AGC 题，虽然这道题比较水。

仔细观察会发现，在第一轮之后可以打开 k 个点和走 k 步，这就相当于没有障碍物直接走。

所以主要保证第一轮尽量走到靠近边界的位置就行。

那么直接 BFS，找到和边界距离的最小值 min ，则答案为 1+\lceil\dfrac{min}{k}\rceil

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 8e2 + 5;
struct Node {
    int Xi, Yi, DIS;
};
int n, m, k1, ans = 1, minn, sx, sy;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char str1[N][N], ch;
bool vis[N][N];
queue<Node> q1;
void BFS();
int main() {
    scanf("%d%d%d", &n, &m, &k1);//循环有的时候要用k所以k1好习惯
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ch = getchar();
            while (ch != '.' && ch != '#' && ch != 'S') {
                ch = getchar();
            }
            if (ch == 'S') {
                ch = '.';
                sx = i;
                sy = j;
                minn = min(min(i - 1, n - i), min(j - 1, m - j));
                //起点,第一轮可以不动
            }
            str1[i][j] = ch;//getchar读入比较优秀
        }
    }
    BFS();
    ans += (minn + k1 - 1) / k1;//向上取整
    printf("%d", ans);
    return 0;
}
void BFS() {
    //都来刷AGC了不至于不会BFS
    while (!q1.empty()) {
        q1.pop();//清空好习惯
    }
    vis[sx][sy] = 1;
    q1.push((Node){sx, sy, 0});//存下点的位置和走了多少步
    while (!q1.empty()) {
        int x = q1.front().Xi;
        int y = q1.front().Yi;
        int dis = q1.front().DIS;
        q1.pop();
        minn = min(minn, min(min(x - 1, n - x), min(y - 1, m - y)));
        //注意与边界的距离别写错
        if (dis >= k1) {
            continue;//走够k步就不能再走
        }
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty] || str1[tx][ty] == '#') {
                continue;
            }
            vis[tx][ty] = 1;
            q1.push((Node){tx, ty, dis + 1});
        }
    }
    return;
}