题解 P2864 【[USACO06JAN]树林The Grove】

一颗赛艇 · 2017-10-31 22:45:45 · 题解

虚拟射线法：

虚拟出一条射线，然后搜索图中看其是否穿过，穿过奇数次为在多边形内，偶数次为多边形外，自己可以画图看看效果，另外判断是否穿过的函数容易写错，因为状态很容易覆盖

_ps:这种做法推荐，是一般解法，适合各种变形，而且代码简单。_

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <string>  
#include <map>  
#include <stack>  
#include <vector>  
#include <set>  
#include <queue>  
//#pragma comment (linker,"/STACK:102400000,102400000")  
#define maxn 105  
#define mod 1000000007  
#define INF 0x3f3f3f3f  
using namespace std;  
typedef long long ll;  
int n,m,ans,flag;  
int sx,sy,gx,gy,nx,ny,tx,ty;  
int dx[]= {-1,1,0,0,-1,-1,1,1};  
int dy[]= {0,0,-1,1,-1,1,-1,1};  
int dp[maxn][maxn][2];  
char mp[maxn][maxn];  
char s[maxn];  
struct Node  
{  
    int x,y,k; // k-是否包围  
} cur,now;  
bool issur()  // 向下穿过包围 向上解包围  
{  
    if(tx==gx&ty<gy)  
    {  
        if(nx<gx) return true;  
    }  
    else if(nx==gx&&ny<gy)  
    {  
        if(tx<gx) return true ;  
    }  
    return false;  
}  
void bfs()  
{  
    int i,j,t,k,nk;  
    queue<Node>q;  
    memset(dp,-1,sizeof(dp));  
    cur.x=sx;  
    cur.y=sy;  
    cur.k=0;  
    dp[sx][sy][0]=0;  
    q.push(cur);  
    while(!q.empty())  
    {  
        now=q.front();  
        q.pop();  
        nx=now.x;  
        ny=now.y;  
        nk=now.k;  
        for(i=0; i<8; i++)  
        {  
            tx=nx+dx[i];  
            ty=ny+dy[i];  
            k=nk;  
            if(tx<1||tx>n||ty<1||ty>m||mp[tx][ty]=='X') continue ;  
            if(issur()) k^=1;  
            if(dp[tx][ty][k]!=-1&&dp[tx][ty][k]<=dp[nx][ny][nk]+1) continue ;  
            cur.x=tx;  
            cur.y=ty;  
            cur.k=k;  
            dp[tx][ty][k]=dp[nx][ny][nk]+1;  
            q.push(cur);  
        }  
    }  
    ans=dp[sx][sy][1];  
}  
int main()  
{  
    int i,j,t;  
    while(~scanf("%d%d",&n,&m))  
    {  
        flag=0;  
        for(i=1; i<=n; i++)  
        {  
            scanf("%s",s);  
            for(j=1; j<=m; j++)  
            {  
                mp[i][j]=s[j-1];  
                if(mp[i][j]=='*') sx=i,sy=j;  
                if(!flag&&mp[i][j]=='X') flag=1,gx=i,gy=j;  
            }  
        }  
        bfs();  
        printf("%d\n",ans);  
    }  
    return 0;  
}