首页 > 代码库 > HDU 4770 Lights Against Dudely 暴力枚举+dfs
HDU 4770 Lights Against Dudely 暴力枚举+dfs
又一发吐血ac，，，再次明白了用函数（代码重用）和思路清晰的重要性。
| 11779687 | 2014-10-02 20:57:53 | Accepted | 4770 | 0MS | 496K | 2976 B | G++ | czy |
Lights Against Dudely
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1360 Accepted Submission(s): 392
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:
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
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.
Sample Input
2 2 ## ## 2 3 #.. ..# 3 3 ### #.# ### 0 0
Sample Output
0 2 -1
Source
2013 Asia Hangzhou Regional Contest
Recommend
We have carefully selected several similar problems for you: 5057 5055 5054 5053 5052
思路：暴力枚举每一个款式特殊灯的位置（转自：http://blog.csdn.net/u014737310/article/details/39249581）
好像状压更简单：
http://www.cnblogs.com/kuangbin/p/3416163.html
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<string> 10 //#include<pair> 11 12 #define N 205 13 #define M 15 14 #define mod 10000007 15 //#define p 10000007 16 #define mod2 100000000 17 #define ll long long 18 #define LL long long 19 #define maxi(a,b) (a)>(b)? (a) : (b) 20 #define mini(a,b) (a)<(b)? (a) : (b) 21 22 using namespace std; 23 24 int n,m; 25 int ans; 26 int k; 27 int vis[N][N]; 28 char s[N][N]; 29 int c[N]; 30 int step[4][3][2]={ {-1,0,0,0,0,1}, 31 {0,-1,-1,0,0,0}, 32 {0,-1,0,0,1,0}, 33 {0,0,0,1,1,0} 34 }; 35 typedef struct 36 { 37 int x; 38 int y; 39 }PP; 40 41 PP p[N]; 42 43 void change(int x,int y,int st[3][2],int s) 44 { 45 int i; 46 int nx,ny; 47 for(i=0;i<3;i++){ 48 nx=x+st[i][0]; 49 ny=y+st[i][1]; 50 if(nx<0 || nx>=n) continue; 51 if(ny<0 || ny>=m) continue; 52 53 vis[nx][ny]=s; 54 } 55 } 56 57 int judge(int x,int y,int st[3][2]) 58 { 59 int i; 60 int nx,ny; 61 for(i=0;i<3;i++){ 62 nx=x+st[i][0]; 63 ny=y+st[i][1]; 64 if(nx<0 || nx>=n || ny<0 || ny>=m) continue; 65 if(s[nx][ny]==‘#‘){ 66 return 0; 67 } 68 } 69 return 1; 70 } 71 72 void ini() 73 { 74 int i,j; 75 memset(c,0,sizeof(c)); 76 ans=20; 77 k=0; 78 for(i=0;i<n;i++){ 79 scanf("%s",s[i]); 80 } 81 for(i=n-1;i>=0;i--){ 82 for(j=0;j<m;j++){ 83 if(s[i][j]==‘.‘){ 84 k++; 85 p[k].x=i;p[k].y=j; 86 } 87 } 88 } 89 90 for(i=1;i<=k;i++){ 91 if(judge(p[i].x,p[i].y,step[0])==1){ 92 c[i]=1; 93 } 94 else{ 95 c[i]=-1; 96 } 97 } 98 } 99 100 101 void dfs(int i,int f,int re)102 {103 if(re>=ans){104 return;105 }106 if(i==k+1){107 ans=re;108 return;109 }110 if(vis[ p[i].x ][ p[i].y ]==1)111 {112 dfs(i+1,f,re);113 }114 if(f!=i && c[i]==1){115 change(p[i].x,p[i].y,step[0],1);116 dfs(i+1,f,re+1);117 change(p[i].x,p[i].y,step[0],0);118 }119 }120 121 void solve()122 {123 int i,j;124 if(k==0){125 ans=0;return;126 }127 memset(vis,0,sizeof(vis));128 dfs(1,0,0);129 for(j=1;j<=3;j++)130 {131 memset(vis,0,sizeof(vis));132 for(i=1;i<=k;i++){133 if(judge( p[i].x,p[i].y,step[j] )==1){134 change(p[i].x,p[i].y,step[j],1);135 dfs(1,i,1);136 change(p[i].x,p[i].y,step[j],0);137 }138 }139 }140 }141 142 143 void out()144 {145 if(ans==20) ans=-1;146 printf("%d\n",ans);147 }148 149 int main()150 {151 // freopen("data.in","r",stdin);152 //freopen("data.out","w",stdout);153 //scanf("%d",&T);154 // for(int ccnt=1;ccnt<=T;ccnt++)155 // while(T--)156 while(scanf("%d%d",&n,&m)!=EOF)157 {158 if(n==0 && m==0 ) break;159 //printf("Case %d: ",ccnt);160 ini();161 solve();162 out();163 }164 165 return 0;166 }
HDU 4770 Lights Against Dudely 暴力枚举+dfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。