The pasture contains a small, contiguous grove of trees that has no 'holes' in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She's just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn't think you could pass 'through' the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here's a typical example where '.' is pasture (which Bessie may traverse), 'X' is the grove of trees, '*' represents Bessie's start and end position, and '+' marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): ...+... ..+X+.. .+XXX+. ..+XXX+ ..+X..+ ...+++* The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she's starting 'outside' the grove instead of in a sort of 'harbor' that could complicate finding the best path.

 

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).

* Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.

Silver

Solution

显然是bfs，但是要求绕障碍一周，所以不能裸上bfs。

考虑从障碍向边界引出一个阻拦边，规定，这个阻拦边右边的点无法穿过该边，但是左边的点可以穿过，这样就可以用这条边来限制，使得可以得到绕圈一周的答案。

具体的方法就是，对于每个点记录dis[0/1][x][y]表示从右/左来的距离，这样在bfs的时候分类讨论一下，就可以了。

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

int N,M,sx,sy,lx,ly,dis[][][];

struct Pa{int x,y,d;};

int dx[]={,,,,,,-,-,-},dy[]={,,-,,,-,,,-};

bool visit[][],mp[][],line[][];

inline bool OK(int x,int y) {return x>= && x<=N && y>= && y<=M;}

void BFS()

{

    queue<Pa>q; q.push((Pa){sx,sy,}); dis[][sx][sy]=;

    while (!q.empty())

        {

            Pa now=q.front(); q.pop();

            for (int d=,x,y; d<=; d++)

                {

                    x=now.x+dx[d],y=now.y+dy[d];

                    if (!OK(x,y) || mp[x][y]) continue;

                    if (line[now.x][now.y] && y<=now.y) continue;

                    if (line[x][y] && y>now.y)

                        if (!dis[][x][y])

                            dis[][x][y]=dis[][now.x][now.y]+,q.push((Pa){x,y,});

                        else;

                    else

                        if (!dis[now.d][x][y])

                            dis[now.d][x][y]=dis[now.d][now.x][now.y]+,q.push((Pa){x,y,now.d});

                        else;

                }

        }

}

int main()

{

    scanf("%d%d",&N,&M); char c[][];

    for (int i=; i<=N; i++)

        {

            scanf("%s",c[i]+);

            for (int j=; j<=M; j++)

                mp[i][j]=c[i][j]=='X',lx=c[i][j]=='X'? i:lx,ly=c[i][j]=='X'? j:ly,

                sx=c[i][j]=='*'? i:sx,sy=c[i][j]=='*'? j:sy;

        }

    for (int i=; i<=N; i++) if (i+lx<=N) line[i+lx][ly]=;

    BFS();

    printf("%d\n",dis[][sx][sy]-);

    return ;

}

说好了shabi题不发博客...

然而长这么大没写过这样的bfs...

自己明明想到了，却实现出了问题，在讨论的时候naive了....所以留一下长记性