题解：P2864 [USACO06JAN] The Grove S

· · 题解

题目传送门

题目大意

这道题目言简意赅，就是要我们求以 * 为起点绕 X 走一圈的最短路。

思路分析

下面介绍 建墙法。
以一个简单的样例为例： 

.......
...X...
..XXX..
...XXX.
...X...
......*

最后一棵树为原点，向下建墙。

最后一棵树 X 的 X 坐标 +1 记为 ltx，Y 记为 lty。

注：X 坐标需 +1，以不与树重合。

如下所示：

.......
...X...
..XXX..
...XXX.
...X...
...|..*
建好墙后，以贝茜为原点，进行 BFS。 所走的步数如下所示： ```cpp 8 7 6 5 5 5 5 8 7 6 X 4 4 4 8 7 X X X 3 3 8 8 8 X X X 2 9 9 9 X 2 1 1 10 10 10 | 2 1 0 ``` BFS 后，就是统计答案了！ 那么答案记为 $sum$，统计步数的数组为 $ans$。 $sum=\min(ans_{ltx−1,lty−1},ans_{ltx,lty−1},ans_{ltx+1,lty−1})+\min(ans_{ltx−1,lty+1},ans_{ltx,lty+1},ans_{ltx+1,lty+1})+2

tips

  1. 墙不能与贝茜重合
  2. BFS 时注意墙与树 一样不能走。
  3. BFS 注意边界。
  4. 统计过的点无需再次访问。

  5. 墙不能与树重合。

    附上 AC 代码

    #include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
#define INF 0x7f7f7f7f7f
ll min(ll a, ll b) {//手打min
return a < b ? a : b;
}
ll r, c; //见题面，r:长 c：宽
char a[100][100]; //地图
ll sx, sy, ltx, lty; //*的坐标，及最后一棵树的坐标
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; //8个方向
ll ans[110][110]; //见前文
ll q[100100][3], h, t; //手打BFS队列
int main() {
cin >> r >> c; //读入
for (int i = 1; i <= r; i++) {
    for (int j = 1; j <= c; j++) {
        cin >> a[i][j];
        if (a[i][j] == '*')sx = i, sy = j; //*坐标
        else if (a[i][j] == 'X')ltx = i + 1, lty = j; //最后一棵树的坐标
    }
}
for (int i = 0; i < 110; i++)for (int j = 0; j < 110; j++)ans[i][j] = INF; //ans赋值为最大值
if (ltx == sx && lty == sy) { //特判，墙不能与*重合
    bool f = 0;
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= c; j++){
            if (a[i][j] == 'X' && !f) {
                ltx = i;
                lty = j;
                f = 1;
                break;
            }
        }
    }
    for (int i = 1; i <= ltx; i++)a[i][lty] = '|';
}
for (int i = ltx; i <= r; i++)a[i][lty] = '|';

ll x, y, s, xx, yy; //BFS开始
ans[sx][sy] = 0;
t = 1;
q[0][0] = sx;
q[0][1] = sy;
while (h < t) {
    x = q[h][0], y = q[h][1], s = q[h][2]; //取队首
    for (int i = 0; i < 8; i++) { //8个方向搜
        xx = x + dx[i], yy = y + dy[i]; //替死鬼
        if (ans[xx][yy] != INF)continue; //不重复搜
        if ((xx >= 1 && xx <= r && yy >= 1 && yy <= c) && a[xx][yy] == '.') { //边界及能否走
            ans[xx][yy] = s + 1; //记入答案
            q[t][0] = xx; //入队
            q[t][1] = yy; //入队
            q[t++][2] = s + 1; //入队
        }
    }
    h++; //出队
} //BFS结束

cout << min(ans[ltx - 1][lty - 1], min(ans[ltx][lty - 1], ans[ltx + 1][lty - 1])) + min(ans[ltx - 1][lty + 1], min(ans[ltx][lty + 1], ans[ltx + 1][lty + 1])) + 2; //输出答案
return 0;
}