這題大意是一堆積木，抽掉某一塊后會(huì)使得上面的積木崩潰（當(dāng)上面的積木僅僅與抽去的部分相鄰），問(wèn)抽去哪塊積木會(huì)使得崩塌的總積木數(shù)最多
這題做法是先將積木處理成圖的節(jié)點(diǎn)，然后如果假設(shè)底下的積木i與上面的積木j直接相鄰面為k，則將i與j連接條權(quán)值為k的邊，然后針對(duì)每一塊積木枚舉求崩潰的總塊數(shù)，這里用類似拓?fù)渑判蛩惴ǖ奶幚恚瑢⒚總€(gè)節(jié)點(diǎn)底面與其他面的接觸面數(shù)作為該節(jié)點(diǎn)的“入度”
1
# include <iostream>
2using namespace std;
3# include <cstdio>
4# include <map>
5# include <cstring>
6# include <vector>
7# include <queue>
8char g[101][101];
9int id[101][101];
10int n,m,c;
11# define max(a,b) ((a)>(b)?(a):(b))
12struct
13
{
14
int r,c,len;
15
}block[10001];
16int main()
17{
18 while(true)
19
{
20 scanf("%d%d",&n,&m);
21 if(!n&&!m) break;
22 for(int i=0;i<n;i++)
23 scanf("%s",g[i]);
24 c=0;
25 for(int i=0;i<n;i++)
26 for(int j=0;j<m;)
27 {
28 if(g[i][j]=='0')
29 {
30 j++;
31 continue;
32
}
33 block[c].r=i;
34 block[c].c=j;
35 block[c].len=g[i][j]-'0';
36 for(int k=j;k<block[c].len+j;k++)
37 id[i][k]=c;
38 j+=block[c++].len;
39 }
40 int degree[10001];
41 int res=0;
42 queue<int> q;
43 int stddegree[10001];
44 for(int i=0;i<c;i++)
45 {
46 stddegree[i]=block[i].len;
47 if(block[i].r+1!=n)
48 for(int j=block[i].c;j<block[i].c+block[i].len;j++)
49 if(g[block[i].r+1][j]=='0')
50 stddegree[i]--;
51 }
52 for(int i=0;i<c;i++)
53 {
54
55 int ans=0;
56 memcpy(degree,stddegree,sizeof(degree));
57 q.push(i);
58 while(!q.empty())
59 {
60 int top=q.front();
61 q.pop();
62 ans+=block[top].len;
63 if(block[top].r!=0)
64 for(int j=block[top].c;j<block[top].c+block[top].len;j++)
65 if(g[block[top].r-1][j])
66 {
67 degree[id[block[top].r-1][j]]--;
68 if(!degree[id[block[top].r-1][j]])
69 q.push(id[block[top].r-1][j]);
70 }
71 }
72 res=max(res,ans);
73 }
74 printf("%d\n",res);
75
76
77 }
78 return 0;
79}
80
81
82