The Grove

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 904		Accepted: 444

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.

6 7

.......

...X...

..XXX..

...XXX.

...X...

......*

13

题意：

    一个n*m(n,m<=50)的矩阵有一片连着的树林，Bessie要从起始位置出发绕林子一圈再回来，每次只能向横着、竖着或斜着走一步。

问最少需多少步才能完成。

分析：

    1.如果搜出的路径能够包围其中的一个点，那么就能包围森林，这样问题就被简化了

    2.我们任选一个点作为被包围点，在搜索时利用射线法判断某这个点是否在多边形中

    3.判断点在多边形内外最常用的方法就是射线法，即以一条射线穿过多边形次数的奇偶性来判断。
　　　奇在偶不在。

//dp[x][y][0]表示从起点达到(x,y)的距离
//dp[x][y][1]表示从(x,y)到起点的距离+去的距离

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=;

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

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

int dp[N][N][];char mp[N][N];

int n,m,sx,sy,gx,gy,px,py,pk,nx,ny,nk;

struct node{

    int x,y,k;

    node(int x=,int y=,int k=):x(x),y(y),k(k){}

};

bool ok(){

    if(nx==gx&&ny<gy){

        if(px<nx) return ;

    }

    if(px==gx&&py<gy){

        if(px>nx) return ;

    }

    return ;

}

void bfs(){

    memset(dp,-,sizeof dp);

    queue<node>q;

    q.push(node(sx,sy,));

    dp[sx][sy][]=;

    while(!q.empty()){

        node t=q.front();q.pop();

        px=t.x;py=t.y;pk=t.k;

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

            nx=px+dx[i];ny=py+dy[i];nk=pk;

            if(nx<||ny<||nx>n||ny>m||mp[nx][ny]=='X') continue;

            if(ok()) nk^=;

            if(!(~dp[nx][ny][nk])){

                dp[nx][ny][nk]=dp[px][py][pk]+;

                q.push(node(nx,ny,nk));

            }

        }

    }

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

}

int main(){

    scanf("%d%d",&n,&m);bool flag=;

    for(int i=;i<=n;i++) scanf("%s",mp[i]+);

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(mp[i][j]=='*') sx=i,sy=j;

            if(!flag&&mp[i][j]=='X') flag=,gx=i,gy=j;

        }

    }

    bfs();

    return ;

}