题目

题目描述

在$n$行$m$列的网格中，你要圈一些地
你从左上角出发，最后返回左上角，路径内部的区域视为被你圈住
你不可以进入网格内部，只能在边上行走
你的路径不能在左上角以外自交，但是边足够宽，你可以重复经过而不自交
网格中有一些格子对你很重要，你要尽量圈住它；而另一些格子对你有坏处，你不能圈住它
求圈住$i$个重要的格子的最小路径长度

输入格式

$n$行，每行$m$个字符
I表示重要的格子，X表示有坏处的格子，.表示其他格子

输出格式

输出重要的格子数行，第i行表示圈住i个重要的格子的最小路径长度

样例

样例输入

X.I
.I.
I..

样例输出

8
10
14

数据范围与提示

题解

看到这个非.的格子这么少，让我想到了压缩最短路算法的状态
如何判断一个点是否在多边形内？很简单，只需要使用射线法
即从这个点随便引出一条射线，如果这条射线与多边形有奇数个交点，那么这个点就在多边形内
所以，我们用状态$s$表示路径下方某个重要格（或坏格）上方被该路径覆盖的次数的奇偶，$f_{x,y,s}$表示圈住这些点并且现在在$(x,y)$上的路径最短长度
然后直接跑最短路，对于左（或右）移操作，就查看一遍移动经过的这一段下方的重要格和坏格，更新$s$
统计答案的时候就遍历所有状态，取最小值即可
附上代码：

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct ppap
{
    int x,y,s;
};
queue<ppap> q;
pair<int,int> sp[20];
int n,m,cnt,sum,dx[5]={0,0,1,-1},dy[5]={1,-1,0,0},k[20],f[60][60][2100],v[60][60][2100],ans[20];
char map[60][60];
int get(int s,int x,int y)
{
    for(int i=1;i<=cnt;i++) if(y==sp[i].second&&x<=sp[i].first) s^=(1<<(i-1));
    return s;
}
int main()
{
    while(~scanf("%s",map[n++]));
    m=strlen(map[0]);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        if(map[i][j]=='X') k[++cnt]=0,sp[cnt]=make_pair(i,j);
        else if(map[i][j]=='I') k[++cnt]=1,sp[cnt]=make_pair(i,j),sum++;
    }
    memset(f,0x7f,sizeof(f)),memset(ans,0x7f,sizeof(ans)),q.push((ppap){0,0,0}),f[0][0][0]=0;
    while(!q.empty()){
        ppap u=q.front();
        q.pop(),v[u.x][u.y][u.s]=0;
        for(int i=0;i<4;i++){
            int x=u.x+dx[i],y=u.y+dy[i],s;
            if(x<0||y<0||x>n||y>m) continue;
            if(i==0||i==1) s=get(u.s,u.x,min(y,u.y));
            else s=u.s;
            if(f[x][y][s]>f[u.x][u.y][u.s]+1){
                f[x][y][s]=f[u.x][u.y][u.s]+1;
                if(!v[x][y][s]) v[x][y][s]=1,q.push((ppap){x,y,s});
            }
        }
    }
    for(int i=1,s;i<(1<<cnt);i++){
        s=0;
        for(int j=1;j<=cnt;j++) if(i&(1<<(j-1))){
            if(!k[j]){s=-1;break;}
            else s++;
        }
        if(s!=-1) ans[s]=min(ans[s],f[0][0][i]);
    }
    for(int i=1;i<=sum;i++) printf("%d\n",ans[i]); 
}