poj 3020

题意：给出一个r*c的图，每个点都是'o'或'*'，最少要用多少个1×2的矩形才能把图中所有的'*'都覆盖掉。

分析：受之前那题muddy field的影响，一直以为这题跟它是类似的，一路想着怎样把交点用边来表示，于是乎什么都想不出来。看了别人的题解才知道，这题每个点用一个顶点表示，若两个'*'相邻，则这两个点之间有条边（所以这条边表示的是一个1×2的矩形）。求出这个图的最大匹配，意思就是把相邻的'*'都尽量用最少的矩形来覆盖，匹配数就是矩形的数量。剩下那些不能匹配的点，每个都要用一个矩形来覆盖。所以答案就是n-HUngary()/2（因为是无向图，匹配过程中同一条边会重复两次）。

View Code

 1 #include<cstdio>
 2 struct coordinate
 3 {
 4     int x,y;
 5 };
 6 int mat[100][100],nx,ny,dir[4][2]={0,1,1,0,0,-1,-1,0},r,c;
 7 bool visited[100][100];
 8 coordinate pset[500];
 9 char map[100][100];
10 bool inside(int x,int y)
11 {
12     return x>=0 && y>=0 && x<r && y<c;
13 }
14 int path(int u)
15 {
16     int i,x,y;
17     x=pset[u].x;
18     y=pset[u].y;
19     for(i=0;i<4;i++)
20     {
21         if(inside(x+dir[i][0],y+dir[i][1]) && map[x+dir[i][0]][y+dir[i][1]]=='*' && !visited[x+dir[i][0]][y+dir[i][1]])
22         {
23             visited[x+dir[i][0]][y+dir[i][1]]=true;
24             if(mat[x+dir[i][0]][y+dir[i][1]]==-1 || path(mat[x+dir[i][0]][y+dir[i][1]]))
25             {
26                 mat[x+dir[i][0]][y+dir[i][1]]=u;
27                 return 1;
28             }
29         }
30     }
31     return 0;
32 }
33 int Hungary()
34 {
35     int ans=0,i,j;
36     for(i=0;i<r;i++)
37     {
38         for(j=0;j<c;j++)
39             mat[i][j]=-1;
40     }
41     for(i=0;i<nx;i++)
42     {
43         for(j=0;j<r;j++)
44         {
45             for(int k=0;k<c;k++)
46                 visited[j][k]=false;
47         }
48         ans+=path(i);
49     }
50     return ans;
51 }
52 int main()
53 {
54     int n;
55     scanf("%d",&n);
56     while(n--)
57     {
58         scanf("%d%d",&r,&c);
59         nx=0;
60         for(int i=0;i<r;i++)
61         {
62             getchar();
63             for(int j=0;j<c;j++)
64             {
65                 scanf("%c",&map[i][j]);
66                 if(map[i][j]=='*')
67                 {
68                     pset[nx].x=i;
69                     pset[nx].y=j;
70                     nx++;
71                 }
72             }
73         }
74         ny=nx;
75         printf("%d\n",nx-Hungary()/2);
76     }
77     return 0;
78 }