题解：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;
}