首页 > > 程序设计 > C/C++ >

2801 LOL-盖伦的蹲草计划

2018-06-17 22:45:21来源：未知阅读 ()

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 }