poj 3020Antenna Placement

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxn 1000
 5 using namespace std;
 6 int t,n,m;
 7 char g[maxn][maxn];
 8 int map1[maxn][maxn];
 9 int gg[maxn][maxn];
10 bool vis[maxn];
11 int match[maxn];
12 int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
13 int res,num;
14 int dfs(int p)
15 {
16     int i,t;
17     for(i=1; i<=num; i++)
18     {
19         if(gg[i][p]&&!vis[i])
20         {
21             vis[i]=true;
22             t=match[i];
23             match[i]=p;
24             if(t==-1||dfs(t))
25                 return 1;
26             match[i]=t;
27         }
28     }
29     return 0;
30 }
31 void pro()
32 {
33     int i;res=0;
34     for(i=1; i<=num; i++)
35     {
36         memset(vis,false,sizeof(vis));
37         res+=dfs(i);
38     }
39 }
40 int main()
41 {
42     scanf("%d",&t);
43     while(t--)
44     {
45         memset(match,-1,sizeof(match));
46         memset(gg,0,sizeof(gg));
47         memset(map1,0,sizeof(map1));
48         num=0;
49         scanf("%d%d",&n,&m);
50         for(int i=0; i<n; i++)
51         {
52             scanf("%s",g[i]);
53             for(int j=0; j<m; j++)
54             {
55                 if(g[i][j]=='*')
56                 {
57                    map1[i][j]=++num;
58                 }
59             }
60         }
61         for(int i=0; i<n; i++)
62         {
63             for(int j=0; j<m; j++)
64             {
65                 if(map1[i][j])
66                 {
67                     for(int k=0; k<4; k++)
68                     {
69                         int x=i+dir[k][0];
70                         int y=j+dir[k][1];
71                         if(map1[x][y])
72                         {
73                             gg[map1[i][j]][map1[x][y]]=1;
74                         }
75                     }
76                 }
77             }
78         }
79         pro();
80         printf("%d
",num-res/2);
81     }
82     return 0;
83 }
View Code