又一個(gè)二分圖！其實(shí)對于這個(gè)題，關(guān)鍵是看你怎樣建立二分圖！
我比較偷懶，就用了一個(gè)黑白染色。題目意思很簡單，就是要用多少個(gè)圓圈完*，當(dāng)然每個(gè)圓只能圈兩個(gè)*；
具體看代碼吧，懶得寫了，一個(gè)早上，還沒吃飯呢？
1 #include <iostream>
2 using namespace std;
3 bool map[500][500];
4 bool vi[500];
5 int link[500];
6 int n,h;
7 int x[4]={0,0,1,-1};
8 int y[4]={1,-1,0,0};
9 bool dfs(int v)
10 {
11 for (int i=1;i<=n;i++)
12 {
13 if (map[v][i]&&!vi[i])
14 {
15 vi[i]=true;
16 if (link[i]==0||dfs(link[i]))
17 {
18 link[i]=v;
19 return true;
20 }
21 }
22 }
23 return false;
24 }
25 int com()
26 {
27 int sum=0;
28 for (int i=1;i<=h;i++)
29 {
30 memset(vi,0,sizeof(vi));
31 if (dfs(i))sum++;
32 }
33 return sum;
34 }
35 int main()
36 {
37 char a[50][16];
38 int b[50][16],c[50][16];
39 int m,k,i,j;
40 int t;
41 cin>>t;
42 while (t--)
43 {
44 cin>>m>>k;
45 n=0,h=0;
46 memset(map,0,sizeof(map));
47 memset(link,0,sizeof(link));
48 memset(b,0,sizeof(b));
49 for (i=1;i<=m;i++)
50 for (j=1;j<=k;j++)
51 {
52 cin>>a[i][j];
53 }
54 h=0,n=0;
55 for (i=1;i<=m;i++)
56 for (j=1;j<=k;j++)
57 if (a[i][j]=='*')
58 {
59 if ((i+j)%2==0)b[i][j]=++h;
60 else b[i][j]=++n;
61 }
62 int dx,dy;
63 for (i=1;i<=m;i++)
64 for (j=1;j<=k;j++)
65 if (a[i][j]=='*'&&(i+j)%2==0)
66 {
67 for (int l=0;l<4;l++)
68 {
69 dx=x[l]+i;
70 dy=y[l]+j;
71 if (a[dx][dy]=='*')
72 map[b[i][j]][b[dx][dy]]=1;
73 }
74 }
75 cout<<h+n-com()<<endl;
76 }
77 return 0;
78 }
79
posted on 2011-04-05 10:46
路修遠(yuǎn) 閱讀(1366)
評論(0) 編輯 收藏 引用 所屬分類:
路修遠(yuǎn)