Codevs 2801 LOL盖伦的蹲草计划

题目描述 Description

众所周知，LOL这款伟大的游戏，有个叫盖伦的英雄。他的伟大之处在于他特别喜欢蹲草丛阴人（XL：蹲草阴人也算英雄？！CZQ：没办法，个个都是这么玩的）。某日，德玛西亚与诺克萨斯之间又发生了一场战斗，嘉文四世希望盖伦能带领一支K人的德玛西亚军队出战。

战斗发生在召唤师峡谷。整个召唤师峡谷被分割成M行N列的一个矩阵，矩阵中有空地和几片草丛。这几片草丛中有些很大、有些很小。一个1×1的草丛能容纳3个士兵，盖伦坚信蹲草偷袭战术能战胜诺克萨斯军队，所以他希望他的军队能全部蹲进草丛里。当然，为了不影响盖伦的作战，盖伦需要单独霸占连起来的一片草丛（不管草丛有多大）。

输入描述 Input Description

第一行M、N、K，表示矩阵的行数、列数和士兵数量。
接下来M行，输入矩阵，'.'代表平地，'*'代表草丛。

输出描述 Output Description

如果德玛西亚军队和盖伦都能躲进草丛里，则输出“Demacia Win!”，否则输出“Demacia Lose!”

样例输入 Sample Input

3 3 6
.**
...
.*.

样例输出 Sample Output

Demacia Win!

数据范围及提示 Data Size & Hint

1<=m、n<=1500
1<=k<=1500
P.S：这里对于两个1×1的草丛是否连在一起的定义是：对于每个1×1的草从，它与周围（上下左右）的草丛是连在一起的。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 using namespace std;
 6 int m,n,k,a[1500+10][1500+10],dis[1801];
 7 int x0[4]={0,0,1,-1},y0[4]={1,-1,0,0},p=0;
 8 bool f=false;
 9 void init()
10 {
11     scanf("%d%d%d",&m,&n,&k);
12     getchar();
13     for(int i=1;i<=m;i++)
14     {
15         for(int j=1;j<=n;j++)
16         {
17             char c;
18             scanf("%c",&c);
19             if(c=='.') a[i][j]=0;
20             else a[i][j]=1;
21         }
22     getchar();
23     }
24 }
25 queue<int> qx,qy;
26 void ss()
27 {
28     for(int i=1;i<=m;i++)
29         for(int j=1;j<=n;j++)
30             if(a[i][j])
31             {
32                 p++;
33                 queue<int> qx,qy;
34                 qx.push(i),qy.push(j);
35                 dis[p]++;
36                 a[i][j]=0;
37                 while(!qx.empty()) 
38                 {
39                     int xx=qx.front(),yy=qy.front();
40                     qx.pop();qy.pop();
41                     for(int k=0;k<4;k++)
42                     {
43                         int zx=xx+x0[k],zy=yy+y0[k];
44                         if(a[zx][zy])
45                         {
46                             qx.push(zx);qy.push(zy);
47                             dis[p]++;
48                             a[zx][zy]=0;
49                         }
50                     }
51                 }
52             }
53 }
54 void sss()
55   {
56       sort(dis+1,dis+p+1);
57       int q=0;
58       for(int i=2;i<=p;i++)
59         q+=dis[i];
60       if(3*q>=k)
61         {
62             f=true;
63             return;
64         }
65   }
66 int main()
67 {
68     init();
69     ss();
70     //for(int i=1;i<=p;i++) printf("%d ",dis[i]);
71     sss();
72     if(f==true) printf("Demacia Win!
");
73     else printf("Demacia Lose!
");
74     return 0;
75 }

思路：宽搜，求出每个联通块的大小，最小的那个给盖伦，其余的藏小兵

80分的AC代码~~5555555.....

轮Code【vs】的操蛋性：

心塞~不说啥了