您的位置:9159金沙官网 > 外星大作战 > 2801 LOL-盖伦的蹲草计划

2801 LOL-盖伦的蹲草计划

发布时间:2019-12-19 04:11编辑:外星大作战浏览(145)

    2801 LOL-盖伦的蹲草陈设

     时限: 1 s

    2801 LOL-盖伦的蹲草计划。 空间范围: 256000 KB

    2801 LOL-盖伦的蹲草计划。 题目品级 : 黄金高尔德

     

    2801 LOL-盖伦的蹲草计划。 

    主题材料陈述 Description

    旗帜明显,英雄联盟那款伟大的玩耍,有个叫盖伦的身体力行。他的硬汉之处在于她专程喜爱蹲草丛阴人(XL:蹲草阴人也算勇敢?!CZQ:无法,个个都以如此玩的)。某日,德玛西亚与诺克萨斯之间又生出了一场交锋,嘉文四世希望盖伦能教导豆蔻年华支K人的德玛西亚武装部队出战。

    打仗产生在召唤师峡谷。整个召唤师峡谷被分割成M行N列的七个矩阵,矩阵中有空地和几片草丛。这几片草丛中有些相当大、有个别超小。几个1×1的草丛能包容3个战士,盖伦坚信蹲草偷袭战略能摆平诺克萨斯军队,所以她希望她的军事能整个蹲进草丛里。当然,为了不影响盖伦的交锋,盖伦供给独自侵吞连起来的一片草丛(不管草丛有多大)。

    图片 1

    2801 LOL-盖伦的蹲草计划。输入描述 Input Description

    2801 LOL-盖伦的蹲草计划。先是行M、N、K,表示矩阵的行数、列数和兵员数量。
    接下去M行,输入矩阵,'.'代表平地,'*'代表草丛。

    出口描述 Output Description

    只要德玛西亚军事和盖伦都能躲进草丛里,则输出“德姆acia Win!”,不然输出“德姆acia Lose!”

    样例输入 萨姆ple Input

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

    样例输出 萨姆ple Output

    Demacia Win!

    多少范围及提示 Data Size & Hint

    1<=m、n<=1500
    1<=k<=1500
    P.S:这里对于三个1×1的草丛是还是不是连在一同的定义是:对于每一种1×1的草从,它与周边(上下左右)的草丛是连在一齐的。

    分类标签 

     思路:dfs+剪枝,不然会爆栈;

     1 #include<cstdio>
     2 #include<cstring>
     3 #include<queue>
     4 using namespace std;
     5 #define max(a,b) a>b?a:b;
     6 int n,m,k,tem,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
     7 char a[1600][1600];
     8 long long int cnt,an;
     9 void dfs(int si,int sj)
    10 {
    11     a[si][sj]='*';
    12     int xx,yy;
    13     for(int i=0;i<4;i++)
    14     {
    15         xx=si+dir[i][0];
    16         yy=sj+dir[i][1];
    17         if(xx>=0&&xx<m&&yy>=0&&yy<n&&a[xx][yy]=='.')
    18         {
    19             cnt++;
    20             if(3*cnt>=k)
    21                 return;
    22             dfs(xx,yy);
    23 
    24         }
    25         else
    26             continue;
    27     }
    28     return ;
    29 }
    30 int main()
    31 {
    32     scanf("%d%d%d",&m,&n,&k);
    33     int i,j;
    34     for(i=0;i<m;i++)
    35     {
    36         scanf("%s",a[i]);
    37     }
    38     for(i=0;i<m;i++)
    39     {
    40         for(j=0;j<n;j++)
    41         {
    42             if(a[i][j]=='.')
    43             {
    44                 cnt=1;
    45                 dfs(i,j);
    46                 an=max(cnt,an);
    47             }
    48             if(3*an>=k)
    49                 break;
    50         }
    51         if(3*an>=k)
    52             break;
    53     }
    54     if(3*an>=k)
    55     printf("Demacia Win!n");
    56     else
    57     printf("Demacia Lose!n");
    58 
    59 return 0;
    60 }
    

     

    本文由9159金沙官网发布于外星大作战,转载请注明出处:2801 LOL-盖伦的蹲草计划

    关键词: