http://poj.org/problem?id=2226
题意：农夫John的养牛场，是一个R 行C 列的矩形，一场大雨后，养牛场低洼的地方都有了积水。
John 的牛都很娇贵的，他们吃草的时候，不想把他们的蹄子给弄脏了。
为了不让牛儿们把它们的蹄子弄脏，John 决定把有水的地方铺上木板（木板可以重叠）。他的木板是宽度为1，长度没有限制的。
Sample:
4 4
*.*.
.***
***.
..*.
4 4
*.*.
.***
***.
..*.
题解 :
看到这个题感觉一个题很像，原来就是黑书上的 “皇家卫士” ，因为要用最少的木板，所以我们要 ，使木板最长，
把行里面连在一起的坑连起来视为一个点，即一块横木板，编上序号，Sample则转化为：
1 0 2 0
0 3 3 3
4 4 4 0
0 0 5 0
把这些序号加入X集合，再按列做一次则为：
1 0 4 0
0 3 4 5
2 3 4 0
0 0 4 0
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-6
15 #define inf 10001000
16
17 #define ll __int64
18
19 #define read() freopen("data.txt","r",stdin) ;
20 const double pi = acos(-1.0);
21 const int maxn = 2600;
22
23 using namespace std;
24 int n,m;
25 int result[maxn],vis[maxn] ;
26 int rcnt,ccnt;
27 int r[60][60],c[60][60] ;
28 int mat[maxn][maxn] ;
29 int find(int a)
30 {
31 int i ;
32 for(i = 0 ; i < ccnt;i++)
33 {
34 if(mat[a][i]&&!vis[i])
35 {
36 vis[i] = 1;
37 if(result[i] == -1||find(result[i]))
38 {
39 result[i] = a ;
40 return 1 ;
41
42 }
43 }
44 }
45 return 0 ;
46 }
47 int get()
48 {
49 int i ;
50 int ans = 0 ;
51 CL(result,-1) ;
52 for(i = 0 ;i < rcnt;i++)
53 {
54 CL(vis,0);
55 if(find(i)) ans++;
56 }
57 return ans ;
58 }
59 char str[maxn][maxn] ;
60 int main()
61 {
62 //read();
63 int i ,j;
64 scanf("%d%d",&n,&m);
65
66
67 CL(mat,0) ;
68
69
70 for(i = 0 ; i < n;i++)
71 {
72 scanf("%s",str[i]);
73 }
74 rcnt = 0 ;
75 for(i = 0 ; i < n;i++)
76 {
77 for(j = 0; j < m;j++)
78 {
79 if(str[i][j] == '*')
80 r[i][j] = rcnt;
81
82 if(str[i][j] == '*'&&str[i][j + 1]!='*')
83 rcnt++;
84 }
85 }
86 ccnt = 0;
87 for(j = 0 ; j < m;j++)
88 {
89 for(i = 0;i < n;i++)
90 {
91 if(str[i][j] == '*')
92 c[i][j] = ccnt;
93
94 if(str[i][j] == '*'&& str[i + 1][j]!='*')
95 {
96 ccnt++;
97
98 }
99
100 }
101
102 }
103
104
105 for(i =0;i < n;i++ )
106 {
107 for(j = 0 ; j< m;j++)
108 {
109 if(str[i][j] == '*')
110 {
111 int x = r[i][j] ;
112 int y = c[i][j] ;
113 mat[x][y] = 1 ;
114 }
115 }
116 }
117
118 int ans = get() ;
119 printf("%d\n",ans) ;
120
121 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-6
15 #define inf 10001000
16
17 #define ll __int64
18
19 #define read() freopen("data.txt","r",stdin) ;
20 const double pi = acos(-1.0);
21 const int maxn = 2600;
22
23 using namespace std;
24 int n,m;
25 int result[maxn],vis[maxn] ;
26 int rcnt,ccnt;
27 int r[60][60],c[60][60] ;
28 int mat[maxn][maxn] ;
29 int find(int a)
30 {
31 int i ;
32 for(i = 0 ; i < ccnt;i++)
33 {
34 if(mat[a][i]&&!vis[i])
35 {
36 vis[i] = 1;
37 if(result[i] == -1||find(result[i]))
38 {
39 result[i] = a ;
40 return 1 ;
41
42 }
43 }
44 }
45 return 0 ;
46 }
47 int get()
48 {
49 int i ;
50 int ans = 0 ;
51 CL(result,-1) ;
52 for(i = 0 ;i < rcnt;i++)
53 {
54 CL(vis,0);
55 if(find(i)) ans++;
56 }
57 return ans ;
58 }
59 char str[maxn][maxn] ;
60 int main()
61 {
62 //read();
63 int i ,j;
64 scanf("%d%d",&n,&m);
65
66
67 CL(mat,0) ;
68
69
70 for(i = 0 ; i < n;i++)
71 {
72 scanf("%s",str[i]);
73 }
74 rcnt = 0 ;
75 for(i = 0 ; i < n;i++)
76 {
77 for(j = 0; j < m;j++)
78 {
79 if(str[i][j] == '*')
80 r[i][j] = rcnt;
81
82 if(str[i][j] == '*'&&str[i][j + 1]!='*')
83 rcnt++;
84 }
85 }
86 ccnt = 0;
87 for(j = 0 ; j < m;j++)
88 {
89 for(i = 0;i < n;i++)
90 {
91 if(str[i][j] == '*')
92 c[i][j] = ccnt;
93
94 if(str[i][j] == '*'&& str[i + 1][j]!='*')
95 {
96 ccnt++;
97
98 }
99
100 }
101
102 }
103
104
105 for(i =0;i < n;i++ )
106 {
107 for(j = 0 ; j< m;j++)
108 {
109 if(str[i][j] == '*')
110 {
111 int x = r[i][j] ;
112 int y = c[i][j] ;
113 mat[x][y] = 1 ;
114 }
115 }
116 }
117
118 int ans = get() ;
119 printf("%d\n",ans) ;
120
121 }