JZOJ4016. 【雅禮聯考DAY01】圈地為王

Description

在 n 行 m 列的網格中，你要圈一些地。

你從左上角出發，最後傳回左上角，路徑内部的區域視為被你圈住。 你不可以進入網格内部， 隻能在邊上行走。 你的路徑不能在左上角以外自交， 但是邊足夠寬， 你可以重複經過而不自交。

網格中有一些格子對你很重要，你要盡量圈住它；而另一些格子對你有壞處，你不能圈住它。

求圈住 i 個重要的格子的最小路徑長度。

Input

n 行，每行 m 個字元。

‘I’表示重要的格子， ‘X’表示有壞處的格子， ‘.’表示其他格子。

Output

輸出重要的格子數行， 第 i 行表示圈住 i 個重要的格子的最小路徑長度。

Sample Input

X.I

.I.

I..

Sample Output

8

10

14

題解

首先我們需要知道如何判斷一個點是否在一個多邊形裡面，

這個很簡單：從這個點引出一條射線，看看它與多邊形的邊有多少個交點，

如果是奇數個，就在多邊形裡面，偶數個就不在。

關于自交的問題，就将它當作沒有自交就好了。

看到資料範圍，特殊點隻有很少，考慮如何設狀态，

用 fx,y,s f x , y , s 表示目前走的點(x,y)，特殊格子上面經過的線的奇偶性的2進制狀态，

有了這個狀态就可以bfs了。

code

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 2560000
#define M 103
#define db double
#define P putchar
#define G getchar
#define inf 998244353
#define pi 3.1415926535897932384626433832795
using namespace std;
char ch;
void read(int &n)
{
    n=;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=;
    if(ch=='-')w=-,ch=G();
    while('0'<=ch && ch<='9')n=(n<<)+(n<<)+ch-'0',ch=G();
    n*=w;
}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>) write(x/);P(x%10+'0');}

int f[][][],n,m,x,y,xx,yy,t,v,ss;
int z[],fx[][]={{-,},{,-},{,},{,}};
int head,tail,q[3][N*8],ans[],p[][],cnt;
bool bz[][][];
char s[][];

int get(int x,int y,int s)
{
    for(int i=;i<=cnt;i++)
        if(p[][i]==y && p[][i]>x)s^=z[i-];
    return s;
}

void dfs(int ss,int x,int y)
{
    ans[y]=min(ans[y],f[][][ss]);
    if(x>cnt)return;
    if(s[p[][x]][p[][x]]=='I')dfs(ss|z[x-],x+,y+);
    dfs(ss,x+,y);
}

int main()
{   
    z[]=;
    for(int i=;i<;i++)
        z[i]=z[i-]<<;

    for(n=;scanf("%c",&ch)!=EOF;n++)
    {
        for(m=;ch=='X' || ch=='I' || ch=='.';ch=G())
        {
            s[n][++m]=ch;
            if(ch!='.')cnt++,p[][cnt]=n,p[][cnt]=m;
        } 
    }

    memset(f,,sizeof(f));
    memset(bz,,sizeof(bz));
    f[][][]=;bz[][][]=;n--;
    for(head=,tail=;head<tail;)
    {
        head++;
        x=q[0][head];
        y=q[1][head];
        t=q[2][head];
        v=f[x][y][t];

        for(int k=;k<;k++)
        {
            xx=x+fx[k][];
            yy=y+fx[k][];
            ss=t;
            if(xx< || yy< || xx>n || yy>m)continue;
            if(k==)ss=get(x,y,ss);
            if(k==)ss=get(x,yy,ss);

            if(f[xx][yy][ss]>v+)
            {
                f[xx][yy][ss]=v+;
                if(bz[xx][yy][ss])
                {
                    bz[xx][yy][ss]=;
                    tail++;
                    q[0][tail]=xx;
                    q[1][tail]=yy;
                    q[2][tail]=ss;
                }
            }
        }
        bz[x][y][t]=;
    }

    memset(ans,,sizeof(ans));
    dfs(,,);
    for(int i=;i<=cnt;i++)
        if(ans[i]<)write(ans[i]),P('\n');

    return ;
}