hdu 1045 Fire Net(二分匹配 or 暴搜) Fire Net
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7998 Accepted Submission(s): 4573Problem DescriptionSuppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.
A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.
The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.
The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.
Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.InputThe input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.OutputFor each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.Sample Input4.X......XX......2XX.X3.X.X.X.X.3....XX.XX4................0Sample Output5 1 5 2 4Source
渣渣一枚只会暴力搜索，查阅了很多资料以后，也就是找到了一个二分匹配的最简写法。
1.匹配算法（匈牙利算）
题意：给出一个n*n的矩阵，其中‘.’表示空地，‘X’表示城墙，空地上可以放炮台，城墙可以阻挡炮台，任意两个炮台不能照脸。求最多能放多少个炮台。
思路：按照行和列一一对应可以构建一个二分图，最大匹配数就是结果。
比较难想的是怎么建图，对于下图，如果(1,1)和(1,3)这两个点是可以同时放炮台的。这种情况相当于将第一行分成了两行，所以(1,3)应该与 (1,1)区分出来独立建图。开始我的想法是记录该点之前遇到过多少城墙，根据遇到的城墙数+当前行列数+n建图，这样建图相当于对原来图中的点进行了平 移，但是这样平移有一个问题。举个例子，就是2+3+n和3+2+n会在同一行。这个例子不一定准确，只是说明在平移后本来一部分在原图中可以同时成立的 匹配在新图中因为没有X反倒不能同时存在了。
可以举一种简单的例子来否定这种情况，新图相当于对原图所有的X进行处理，新图中没有X，但是图的长和宽都扩大了一倍。比如说对于5*5的图（题目规定最 大值为4，这里只是举例），如果按照上面的建图方法，长和宽同时增大一倍。那么新图中最多能同时存在十个点。按照‘.’和‘X’逐个隔开的方式画图，可以 看出这种方法明显是错的。
后来想了一下，对于没有遇到城墙的点应该保留在原图，遇到一次城墙的点应该在下一个图里。对于城墙后面的点的位置不是调整到原图之后，而是完全存在一个新的图里面。所以我修改了一下建图的方法，改为当前行列数+遇到城墙数*n，修改之后提交AC。
因为对于一个n*n的图，原图的长和边的长度最多增加(n-1)*n，所以新图的点数最多应该是(n-1)*n+n，即n*n。
.X..
....
XX..
....
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <iostream> 6 #include <algorithm> 7 #include <climits> 8 #include <queue> 9 #define ll long long 10 11 using namespace std; 12 13 const int N = 1000; 14 int head[N],total,visit[N]; 15 int link[N],flag_x[N],flag_y[N]; 16 char maze[10][10]; 17 18 struct nodes 19 { 20 int e,next; 21 }Edge[N]; 22 23 24 void add(int x,int y) 25 { 26 Edge[total].e = y; 27 Edge[total].next = head[x]; 28 head[x] = total++; 29 } 30 31 int dfs(int f) 32 { 33 int u = head[f]; 34 for(int i = u; i != -1; i = Edge[i].next) 35 { 36 int s = Edge[i].e; 37 if(visit[s]) continue; 38 visit[s] = 1; 39 if(link[s] == -1 || dfs(link[s])) 40 { 41 link[s] = f; 42 return 1; 43 } 44 } 45 return 0; 46 } 47 48 void init() 49 { 50 total = 0; 51 memset(head,-1,sizeof(head)); 52 memset(flag_x,0,sizeof(flag_x)); 53 memset(flag_y,0,sizeof(flag_y)); 54 memset(link,-1,sizeof(link)); 55 } 56 int main(void) 57 { 58 int n,i,j,cnt; 59 while(scanf("%d",&n),n) 60 { 61 init(); 62 for(i = 1; i <= n; i++) 63 scanf("%s",maze[i]+1); 64 65 for(i = 1; i <= n; i++) 66 { 67 for(j = 1; j <= n ; j++) 68 { 69 if(maze[i][j] == '.') 70 add(n*flag_x[i]+i,n*flag_y[j]+j); 71 else 72 flag_x[i]++,flag_y[j]++;//讲城墙隔开的点建到新图里 73 } 74 } 75 for(cnt = 0,i = 1; i <= n * n; i++) 76 { 77 memset(visit,0,sizeof(visit)); 78 if(dfs(i)) 79 cnt++; 80 } 81 printf("%d ",cnt); 82 } 83 return 0; 84 }
2.暴力深搜
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 #define PI acos(-1.0) 8 using namespace std; 9 char maps[5][5]; 10 int visit[5][5],n,ans,k; 11 struct nodes 12 { 13 int x,y; 14 } use[25]; 15 void dfs(int th,int cur) 16 { 17 if(th >= k) 18 return; 19 dfs(th+1,cur); 20 int x = use[th].x; 21 int y = use[th].y; 22 for(int i = y-1; i >= 0; i--) 23 { 24 if(maps[x][i] == 'X') 25 break; 26 if(visit[x][i] == 1) 27 { 28 return; 29 } 30 } 31 for(int i = x-1; i >= 0; i--) 32 { 33 if(maps[i][y] == 'X') 34 break; 35 if(visit[i][y] == 1) 36 { 37 return; 38 } 39 } 40 41 visit[x][y] = 1; 42 ans = max(ans,cur+1); 43 dfs(th+1,cur+1); 44 visit[x][y] = 0; 45 } 46 int main(void) 47 { 48 while(scanf("%d",&n) ,n) 49 { 50 ans = 0; 51 k = 0; 52 memset(visit,0,sizeof(visit)); 53 for(int i = 0; i <n; i++) 54 scanf("%s",maps[i]); 55 for(int i = 0; i < n; i++) 56 for(int j = 0; j < n; j++) 57 { 58 if(maps[i][j] == '.') 59 use[k].x = i,use[k++].y = j; 60 } 61 dfs(0,0); 62 printf("%d ",ans); 63 } 64 return 0; 65 }