2801 LOL-盖伦的蹲草计划
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<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
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 else
51 {
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 else
76 {
77 printf("Demacia Lose!");
78 }
79 return 0;
80 }