【CZYZ2009暑假集训提高组6】盟军敢死队

来源和评测点

CZYZ2009暑假集训提高组6

题目

【题目大意】
仓库是一个 mn的矩形区域, 每一格用一个字符来描述:
“.” 代表空地; “#”代表墙或障碍物;
“^”, “v”(小写), “<”, “>”四个字符分别表示正向 NSWE 四个方向看的敌人。
敌人总是保持固定不动并朝着一个方向看,
从这个方向一直延伸直到边界或障碍物的区域是他的视线范围,
如果一个敌人没有在任何人的视线范围之内,敢死队员就可以消灭他。
你不能消灭一个正在另一个活着的敌人视线范围内的敌人,否则你就会被发现,
后果不堪设想。一个敌人不会成为遮挡视线的障碍物。
【输入格式】
输入数据的第一行是用空格分开的两个整数 n,m ,分别表示仓库的长和宽。
接下来有 n行,每行 m个字符,是仓库的描述。
100%的数据中,1<=m, n<=60
90%的数据中,敌人数不超过 10
100%的数据中,敌人数不超过 15
【输出格式】
如果能够成功消灭所有敌人,输出消灭所有敌人的不同顺序的数量,
否则输出“Impossible” (不含引号)。
【输入样例1】
2 2
>^
#^
【输出样例1】
2
【输入样例2】
1 3
>.<
*【输出样例2】

Impossible

分析

挺好的状压题
注释很详细
“一看数据范围就知道是状压”
话说有的人一看就觉得是暴力,其实也有道理
事实上时间是压着过去的

代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//**********************************************
struct pr
{
int x,y;
int tr;
}p[20];
int pn;
bool rd[20][20];//i能否看到j
//**********************************************
int mp[100][100];
//**********************************************
int f[1<<15];//状态方案数
bool chw[20][1<<15];//j状态下能否杀i
//状态用二进制表示,1就是死了
//**********************************************
char s[100];
int bin[21];
int main()
{
pn=0;memset(rd,0,sizeof(rd));memset(chw,0,sizeof(chw));
bin[1]=1;for(int i=2;i<=20;i++) bin[i]=bin[i-1]<<1;
//稍微改了一下,不是2^i而是对应第i个敌人
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++)
{
if(s[j]=='.') mp[i][j]=1;
else if(s[j]=='#') mp[i][j]=0;
else
{
pn++;p[pn].x=i;p[pn].y=j;
mp[i][j]=10+pn;
if(s[j]=='^') p[pn].tr=2;
if(s[j]=='v') p[pn].tr=3;
if(s[j]=='<') p[pn].tr=4;
if(s[j]=='>') p[pn].tr=5;
}
}
}
for(int i=1;i<=pn;i++)
{
int x=p[i].x,y=p[i].y;
while(1)
{
if(p[i].tr==2) x--;if(p[i].tr==3) x++;
if(p[i].tr==4) y--;if(p[i].tr==5) y++;
if(mp[x][y]==0 or x<=0 or y<=0 or x>n or y>m) break;
if(mp[x][y]>10) rd[i][mp[x][y]-10]=1;
}
}
int full=(1<<pn)-1;//圆满状态
for(int i=1;i<=pn;i++)//被看者
{
for(int j=0;j<=full;j++)//状态
{
if( (j&bin[i])!=0 ) continue;//已经死了
bool bk=1;
for(int k=1;k<=pn;k++)//看者
{
if( (j&bin[k])==0 and i!=k ) bk=!rd[k][i];
if(!bk) break;
}
chw[i][j]=bk;
}
if(chw[i][0]) f[bin[i]]++;//单杀
}
for(int i=0;i<=full;i++)
for(int j=1;j<=pn;j++)
if((i&bin[j])!=0 and chw[j][i^bin[j]]==1)//任杀
f[i]+=f[i^bin[j]];
if(f[full]>0) printf("%d",f[full]);
else printf("Impossible");
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/盟军敢死队.html
转载请注明出处,谢谢!

给我投食吧,您的支持将鼓励我继续创作!