首页 > 代码库 > HDU 4770 状压暴力枚举
HDU 4770 状压暴力枚举
Lights Against Dudely
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1415 Accepted Submission(s): 412
Problem Description
Harry: "But Hagrid. How am I going to pay for all of this? I haven‘t any money."
Hagrid: "Well there‘s your money, Harry! Gringotts, the wizard bank! Ain‘t no safer place. Not one. Except perhaps Hogwarts."
— Rubeus Hagrid to Harry Potter.
Gringotts Wizarding Bank is the only bank of the wizarding world, and is owned and operated by goblins. It was created by a goblin called Gringott. Its main offices are located in the North Side of Diagon Alley in London, England. In addition to storing money and valuables for wizards and witches, one can go there to exchange Muggle money for wizarding money. The currency exchanged by Muggles is later returned to circulation in the Muggle world by goblins. According to Rubeus Hagrid, other than Hogwarts School of Witchcraft and Wizardry, Gringotts is the safest place in the wizarding world.
The text above is quoted from Harry Potter Wiki. But now Gringotts Wizarding Bank is not safe anymore. The stupid Dudley, Harry Potter‘s cousin, just robbed the bank. Of course, uncle Vernon, the drill seller, is behind the curtain because he has the most advanced drills in the world. Dudley drove an invisible and soundless drilling machine into the bank, and stole all Harry Potter‘s wizarding money and Muggle money. Dumbledore couldn‘t stand with it. He ordered to put some magic lights in the bank rooms to detect Dudley‘s drilling machine. The bank can be considered as a N × M grid consisting of N × M rooms. Each room has a coordinate. The coordinates of the upper-left room is (1,1) , the down-right room is (N,M) and the room below the upper-left room is (2,1)..... A 3×4 bank grid is shown below:
Some rooms are indestructible and some rooms are vulnerable. Dudely‘s machine can only pass the vulnerable rooms. So lights must be put to light up all vulnerable rooms. There are at most fifteen vulnerable rooms in the bank. You can at most put one light in one room. The light of the lights can penetrate the walls. If you put a light in room (x,y), it lights up three rooms: room (x,y), room (x-1,y) and room (x,y+1). Dumbledore has only one special light whose lighting direction can be turned by 0 degree,90 degrees, 180 degrees or 270 degrees. For example, if the special light is put in room (x,y) and its lighting direction is turned by 90 degrees, it will light up room (x,y), room (x,y+1 ) and room (x+1,y). Now please help Dumbledore to figure out at least how many lights he has to use to light up all vulnerable rooms.
Please pay attention that you can‘t light up any indestructible rooms, because the goblins there hate light.
Hagrid: "Well there‘s your money, Harry! Gringotts, the wizard bank! Ain‘t no safer place. Not one. Except perhaps Hogwarts."
— Rubeus Hagrid to Harry Potter.
Gringotts Wizarding Bank is the only bank of the wizarding world, and is owned and operated by goblins. It was created by a goblin called Gringott. Its main offices are located in the North Side of Diagon Alley in London, England. In addition to storing money and valuables for wizards and witches, one can go there to exchange Muggle money for wizarding money. The currency exchanged by Muggles is later returned to circulation in the Muggle world by goblins. According to Rubeus Hagrid, other than Hogwarts School of Witchcraft and Wizardry, Gringotts is the safest place in the wizarding world.
The text above is quoted from Harry Potter Wiki. But now Gringotts Wizarding Bank is not safe anymore. The stupid Dudley, Harry Potter‘s cousin, just robbed the bank. Of course, uncle Vernon, the drill seller, is behind the curtain because he has the most advanced drills in the world. Dudley drove an invisible and soundless drilling machine into the bank, and stole all Harry Potter‘s wizarding money and Muggle money. Dumbledore couldn‘t stand with it. He ordered to put some magic lights in the bank rooms to detect Dudley‘s drilling machine. The bank can be considered as a N × M grid consisting of N × M rooms. Each room has a coordinate. The coordinates of the upper-left room is (1,1) , the down-right room is (N,M) and the room below the upper-left room is (2,1)..... A 3×4 bank grid is shown below:
Some rooms are indestructible and some rooms are vulnerable. Dudely‘s machine can only pass the vulnerable rooms. So lights must be put to light up all vulnerable rooms. There are at most fifteen vulnerable rooms in the bank. You can at most put one light in one room. The light of the lights can penetrate the walls. If you put a light in room (x,y), it lights up three rooms: room (x,y), room (x-1,y) and room (x,y+1). Dumbledore has only one special light whose lighting direction can be turned by 0 degree,90 degrees, 180 degrees or 270 degrees. For example, if the special light is put in room (x,y) and its lighting direction is turned by 90 degrees, it will light up room (x,y), room (x,y+1 ) and room (x+1,y). Now please help Dumbledore to figure out at least how many lights he has to use to light up all vulnerable rooms.
Please pay attention that you can‘t light up any indestructible rooms, because the goblins there hate light.
Input
There are several test cases.
In each test case:
The first line are two integers N and M, meaning that the bank is a N × M grid(0<N,M <= 200).
Then a N×M matrix follows. Each element is a letter standing for a room. ‘#‘ means a indestructible room, and ‘.‘ means a vulnerable room.
The input ends with N = 0 and M = 0
In each test case:
The first line are two integers N and M, meaning that the bank is a N × M grid(0<N,M <= 200).
Then a N×M matrix follows. Each element is a letter standing for a room. ‘#‘ means a indestructible room, and ‘.‘ means a vulnerable room.
The input ends with N = 0 and M = 0
Output
For each test case, print the minimum number of lights which Dumbledore needs to put.
If there are no vulnerable rooms, print 0.
If Dumbledore has no way to light up all vulnerable rooms, print -1.
If there are no vulnerable rooms, print 0.
If Dumbledore has no way to light up all vulnerable rooms, print -1.
Sample Input
2 2
##
##
2 3
#..
..#
3 3
###
#.#
###
0 0
Sample Output
0
2
-1
题目意思：
在n*m的迷宫里，‘#’代表墙，‘.’代表空地，在空地上可以安装一些灯，每栈灯可以照亮(x,y) (x-1,y) (x,y+1)三个地方，题目要求安装最少的灯使得灯照亮所有空地(灯光可以覆盖)而且不能照到墙，安装的灯中只有一盏灯可以0、90、180、270度旋转。
思路：
题目要求最多15个空地，每个空地要么安装灯要么不安装灯，用状压枚举安装灯的状态即可。然后在安装的灯中枚举哪一盏灯可以旋转，状压枚举中套个旋转枚举，更新灯的数目就行了。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 struct node{10 int x, y;11 }a[40005];12 13 int n, m;14 char map[205][205];15 int xx[]={-1,0,1,0};16 int yy[]={0,1,0,-1};17 18 int flag(int x,int y){19 if(x<0||x>=n||y<0||y>=m) return 0;20 return 1;21 }22 23 main()24 {25 int i, j, k, nn, l, r, ans, aa;26 int f[20];27 while(scanf("%d %d",&n,&m)==2){28 if(!n&&!m) break;29 ans=99999;30 for(i=0;i<n;i++){31 scanf("%s",map[i]);32 }33 nn=0;34 for(i=0;i<n;i++){35 for(j=0;j<m;j++){36 if(map[i][j]==‘.‘){37 a[nn].x=i;a[nn++].y=j;38 }39 }40 }41 if(nn==0){42 printf("0\n");continue;43 }44 int sum=1<<nn;45 for(i=1;i<sum;i++){ //状压状态枚举46 memset(f,0,sizeof(f));aa=0;47 for(j=0;j<nn;j++){48 if((i>>j)&1) f[j]=1,aa++;49 }50 for(j=0;j<nn;j++){ //枚举哪一盏灯可以旋转51 if(!f[j]) continue;52 int num=0;53 for(l=0;l<nn;l++){ 54 map[a[l].x][a[l].y]=‘.‘;55 }56 for(k=0;k<nn;k++){ //安装不旋转的灯57 if(!f[k]||k==j) continue;58 if(flag(a[k].x,a[k].y+1)&&map[a[k].x][a[k].y+1]==‘#‘||flag(a[k].x-1,a[k].y)&&map[a[k].x-1][a[k].y]==‘#‘) continue;59 if(map[a[k].x][a[k].y]==‘.‘) map[a[k].x][a[k].y]=‘*‘,num++;60 if(map[a[k].x-1][a[k].y]==‘.‘) map[a[k].x-1][a[k].y]=‘*‘,num++;61 if(map[a[k].x][a[k].y+1]==‘.‘) map[a[k].x][a[k].y+1]=‘*‘,num++;62 }63 for(k=0;k<4;k++){ //旋转的灯的四种旋转方式64 if(flag(a[j].x+xx[k],a[j].y+yy[k])&&map[a[j].x+xx[k]][a[j].y+yy[k]]==‘#‘||65 flag(a[j].x+xx[(k+1)%4],a[j].y+yy[(k+1)%4])&&map[a[j].x+xx[(k+1)%4]][a[j].y+yy[(k+1)%4]]==‘#‘) continue;66 int num1=num;67 int f1, f2, f3;68 f1=f2=f3=0;69 if(map[a[j].x][a[j].y]==‘.‘) map[a[j].x][a[j].y]=‘*‘,num1++,f1=1;70 if(map[a[j].x+xx[k]][a[j].y+yy[k]]==‘.‘) map[a[j].x+xx[k]][a[j].y+yy[k]]=‘*‘,num1++,f2=1;71 if(map[a[j].x+xx[(k+1)%4]][a[j].y+yy[(k+1)%4]]==‘.‘) map[a[j].x+xx[(k+1)%4]][a[j].y+yy[(k+1)%4]]=‘*‘,num1++,f3=1;72 if(num1==nn) ans=min(ans,aa);73 if(f1) map[a[j].x][a[j].y]=‘.‘;74 if(f2) map[a[j].x+xx[k]][a[j].y+yy[k]]=‘.‘;75 if(f3) map[a[j].x+xx[(k+1)%4]][a[j].y+yy[(k+1)%4]]=‘.‘;76 }77 }78 }79 if(ans==99999) printf("-1\n");80 else printf("%d\n",ans);81 }82 }
HDU 4770 状压暴力枚举
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。