题解 P2864 【[USACO06JAN]The Grove S】

旭日临窗 · 2020-09-10 20:12:15 · 题解

这里发一下建墙法的题解：

• 首先，拿到一道题，我们要先确定思路，再去证明我们的思路是对的，这样做题就会变得简单而高效了。

• 思路：我们先在最后一棵树下面建墙，建完墙之后是这个样子的（ | 代表墙，很形象）：

  . . . . . . .
  . . . X . . .
  . . X X X . .
  . . . X X X .
  . . . X . . .
  . . . | . . *

  而最短路是这样子的：

  . . . + . . .
  . . + X + . .
  . + X X X + .
  . . + X X X +
  . . + X . . +
  . . . + + + *

  我们发现，我们要求的最短路不就是从原点到墙的最短 路与原点到（5 , 5），第5行第5列，的最短路之和吗，知道了这一点，这道题就几乎迎刃而解了。

• 理由：我们可以理解成就相当于把从原点绕一圈的最短路拆分成了两部分，大家可以自己先想一下。

• 还有最后一个小问题：就是原点到墙的距离可以从三个位置转移过来，我们假设墙的位置是（u , v），那dis[ u ] [ v ]就等于min( min(dis[ u ][ v - 1 ] , dis[ u - 1 ][ v - 1 ]) , dis[ u + 1 ][ v - 1 ]) + 1;

• code

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;
    node(){}//构造函数 。 
    node(int _x,int _y) : x(_x),y(_y){};
};
int n,m,u1,v1,u2,v2,s,ans;
int vis[60][60],dis[60][60];
int fx[8][2] = {0,-1,0,1,-1,0,1,0,-1,-1,-1,1,1,1,1,-1};//有8个方向可以走 。 
char a[60][60];
queue <node> q;//队列 。 
void bfs()
{
    q.push(node(u1,v1));
    vis[u1][v1] = 1;
    dis[u1][v1] = 0;
    while(!q.empty())
    {
        node t = q.front();q.pop();
        for(int k = 0;k < 8;k++)
        {
            int u = t.x + fx[k][0],v = t.y + fx[k][1];
            if(u >= 1 && u <= n && v >= 1 && v <= m && a[u][v] == '.' && !vis[u][v])//只有空地可以走 。 
            {
                vis[u][v] = 1;
                dis[u][v] = dis[t.x][t.y] + 1;//更新距离 。 
                q.push(node(u,v));
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%s",a[i] + 1);
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(a[i][j] == '*') u1 = i,v1 = j;//记录起点 。 
            if(a[i][j] == 'X') u2 = i + 1,v2 = j;//记录最后一棵树的位置，准确地说是建第一堵墙的位置 。 
        }
    }
    for(int i = 1;i < 60;i++)
    for(int j = 1;j < 60;j++)
    dis[i][j] = 1e9;//因为后面要取min，所以要赋一个比较大的值 。 
    for(int i = u2;i <= n;i++) a[i][v2] = '|';//建墙，注意要一直建到底 。 
    bfs();
    ans = min(min(dis[u2][v2 - 1],dis[u2 - 1][v2 - 1]),dis[u2 + 1][v2 - 1]) + 1;//更新起点到墙的距离。 
    printf("%d",ans + dis[u2 - 1][v2 + 1] + 1);//最后输出答案即可 。 
    return 0;
}

/ 管理员大大求过，thanks /