Description
你的蔬菜园形成了一个矩形网格。你决定检查一些小块土地。从左上角开始，你将走过菜园，回到起点。现在你想要检查一下菜园内的田地，于是你决定从左上角出发，在菜园里走一圈回到原处。最后，所有在你走过的这个环内的田地都被认为检查过了。为了保护植 物，你的路径只能在田地边界的小路上走，不能走到田地里面。并且你走过的路径不能自交，小路保证足够宽，你可以多次沿着一条小路走，并且这些路径都不相 交。先在给你菜园的地图，其中有的田地标记为”I”，表示这些田地是你想要检查的；有的田地被标记为”X”，表示这些田地是你不想检查的；有的田地被标记为”.”，表示这些田地你不关心。假设菜园中有K个”I”，那么你要返回K个数字，其中第i个数为：恰好检查任意i个标记为”I”的田地，并且没有检查任何一个标记为”X”的田地的最短路。
【输入格式】
n 行,每行 m 个字符。
'I'表示重要的格子,'X'表示有坏处的格子,'.'表示其他格子。
【输出格式】
输出重要的格子数行,第 i 行表示圈住 i 个重要的格子的最小
路径长度。
【输入样例】
X.I
.I.
I..
【输出样例】
8
10
14
判断一个格子是否被圈住，可以看它上面是否有奇数条边
如果是奇数，那么就需要从下面连回起点
用$dist[x][y][S]$表示到$(x,y)$,关键点上面的边数的奇偶性状态S
广搜更新$dist$数组
复杂度$O(n^{2}*10*2^{10})$
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct ZYYS
{
int x,y,s;
};
const int dx[]={,,,-},dy[]={,-,,};
int n,m,cnt,x[],y[],pd[],dist[][][<<],ans[],inf,tot,Max;
bool vis[][][<<];
char s[][];
queue<ZYYS>Q;
int get(int S,int xx,int yy)
{int i;
for (i=;i<=cnt;i++)
{
if (yy==y[i]&&xx<=x[i]) S^=(<<i-);
}
return S;
}
int main()
{int i,j;
while (~scanf("%s",s[n]))
{
n++;
}
m=strlen(s[]);
for (i=;i<n;i++)
for (j=;j<m;j++)
{
if (s[i][j]=='X')
{
++cnt;
pd[cnt]=;
x[cnt]=i;y[cnt]=j;
}
else if (s[i][j]=='I')
{
++cnt;
pd[cnt]=;
x[cnt]=i;y[cnt]=j;
}
}
memset(dist,/,sizeof(dist));
Q.push((ZYYS){,,});
dist[][][]=;
while (Q.empty()==)
{
ZYYS u=Q.front();
Q.pop();
vis[u.x][u.y][u.s]=;
for (i=;i<;i++)
{
int x=u.x+dx[i],y=u.y+dy[i],S;
if (x<||y<||x>n||y>m) continue;
if (i==||i==)
S=get(u.s,u.x,min(y,u.y));
else S=u.s;
if (dist[x][y][S]>dist[u.x][u.y][u.s]+)
{
dist[x][y][S]=dist[u.x][u.y][u.s]+;
if (vis[x][y][S]==)
{
vis[x][y][S]=;
Q.push((ZYYS){x,y,S});
}
}
}
}
memset(ans,/,sizeof(ans));
inf=ans[];
for (i=;i<(<<cnt);i++)
{
tot=;
for (j=;j<=cnt;j++)
if ((i&(<<j-)))
{
if (pd[j]==)
{
tot=-;
break;
}
else
tot++;
}
if (tot!=-)
{
Max=max(tot,Max);
if (dist[][][i]<ans[tot]) ans[tot]=dist[][][i];
}
}
for (i=;i<=Max;i++)
printf("%d\n",ans[i]);
}