题目
题目描述
在$n$行$m$列的网格中，你要圈一些地
你从左上角出发，最后返回左上角，路径内部的区域视为被你圈住
你不可以进入网格内部，只能在边上行走
你的路径不能在左上角以外自交，但是边足够宽，你可以重复经过而不自交
网格中有一些格子对你很重要，你要尽量圈住它；而另一些格子对你有坏处，你不能圈住它
求圈住$i$个重要的格子的最小路径长度
输入格式
$n$行，每行$m$个字符I表示重要的格子，X表示有坏处的格子，.表示其他格子
输出格式
输出重要的格子数行，第i行表示圈住i个重要的格子的最小路径长度
样例
样例输入
1 | X.I |
样例输出
1 | 8 |
数据范围与提示
题解
看到这个非.的格子这么少，让我想到了压缩最短路算法的状态
如何判断一个点是否在多边形内？很简单，只需要使用射线法
即从这个点随便引出一条射线，如果这条射线与多边形有奇数个交点，那么这个点就在多边形内
所以，我们用状态$s$表示路径下方某个重要格（或坏格）上方被该路径覆盖的次数的奇偶，$f_{x,y,s}$表示圈住这些点并且现在在$(x,y)$上的路径最短长度
然后直接跑最短路，对于左（或右）移操作，就查看一遍移动经过的这一段下方的重要格和坏格，更新$s$
统计答案的时候就遍历所有状态，取最小值即可
附上代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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]);
}