2801 LOL-盖伦的蹲草计划

 

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

 

 

 

题目描述

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的草从，它与周围（上下左右）的草丛是连在一起的。

分类标签 Tags

''

 

尼玛题目错了。。。

这就比较尴尬了。。。

注意在DFS的时候一旦遇到可以退出的条件就直接退出

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int MAXN=5000; 7 int map[MAXN][MAXN]; 8 int vis[MAXN][MAXN]; 9 int ans;10 int xx[5]={-1,+1,0,0};11 int yy[5]={
    0,0,-1,+1};12 int n,m,k;13 void dfs(int x,int y,int tot)14 {15     if(tot>ans)16     ans=tot;17     if(tot*3>=k)18     {19         printf("Demacia Win!");20         exit(0);21     }22     vis[x][y]=1;23     for(int i=0;i<4;i++)24     {25         int wx=x+xx[i];26         int wy=y+yy[i];27         if(wx>0&&wy>0&&wx<=n&&wy<=m&&vis[wx][wy]==0&&map[wx][wy]==0)28         {29             dfs(wx,wy,tot+1);30         }31     }32     33 }34 int main()35 {36     37     scanf("%d%d%d",&n,&m,&k);38     int flag=0;39     for(int i=1;i<=n;i++)40     {41         for(int j=1;j<=m;j++)42         {43             char c;44             cin>>c;45             if(c=='*')46             {47                 map[i][j]=1;48                 flag=1;49             }50             else51             {52                 map[i][j]=0;//不能走 53             }54         }55     }56     for(int i=1;i<=n;i++)57     {58         for(int j=1;j<=m;j++)59         {60             if(vis[i][j]==0&&map[i][j]==0)61             {62                 dfs(i,j,1);63             }64         }65     }66     /*if(flag==1&&k<=3)67     {68         printf("Demacia Win!");69         return 0;70     }*/71     if(ans*3>=k)72     {73         printf("Demacia Win!");74     }75     else76     {77         printf("Demacia Lose!");78     }79     return 0;80 }