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

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

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

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

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

Demacia Win!

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

 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         else26             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     else57     printf("Demacia Lose!\n");58 59 return 0;60 }