蹲草阴人也算勇敢,有个叫盖伦的勇猛

280一 LOL-盖伦的蹲草布置

 

时限: 1 s

空间范围: 25五千 KB

标题等第 : 黄金 戈尔德

 

 

 

标题叙述 Description

眼看,LOL那款伟大的玩耍,有个叫盖伦的奋勇。他的壮烈之处在于他专程喜欢蹲草丛阴人(XL:蹲草阴人也算勇敢?!CZQ:不能够,个个都以这么玩的)。某日,德玛西亚与诺克萨斯之间又发出了一场战斗,嘉文4世希望盖伦能辅导1支K人的德玛西亚武装部队出战。

战斗发生在呼唤师峡谷。整个召唤师峡谷被细分成M行N列的一个矩阵,矩阵中有空地和几片草丛。这几片草丛中大概相当大、某个不大。一个一×一的草丛能包容1个兵卒,盖伦坚信蹲草偷袭计谋能击溃诺克萨斯军队,所以她梦想她的军事能整个蹲进草丛里。当然,为了不影响盖伦的战斗,盖伦供给独自侵吞连起来的一片草丛(不管草丛有多大)。

图片 1

输入描述 Input Description

第一行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的草从,它与周边(上下左右)的草莽是连在一齐的。

280一 LOL-盖伦的蹲草安排

 

时限: 一 s

空间范围: 256000 KB

标题等第 : 黄金 戈尔德

 

 

 

难题叙述 Description

眼看,LOL那款伟大的2日游,有个叫盖伦的勇于。他的宏大之处在于她特意喜欢蹲草丛阴人(XL:蹲草阴人也算勇敢?!CZQ:不可能,个个都是那样玩的)。某日,德玛西亚与诺克萨斯之间又发生了一场交锋,嘉文肆世希望盖伦能指引1支K人的德玛西亚军队出战。

打仗产生在召唤师峡谷。整个召唤师峡谷被分割成M行N列的3个矩阵,矩阵中有空地和几片草丛。这几片草丛中有个别相当的大、有个别一点都不大。二个1×一的草丛能包容2个兵士,盖伦坚信蹲草偷袭计策能战胜诺克萨斯军队,所以她期望她的军事能壹切蹲进草丛里。当然,为了不影响盖伦的战斗,盖伦需求独自侵吞连起来的一片草丛(不管草丛有多大)。

图片 2

输入描述 Input Description

先是行M、N、K,表示矩阵的行数、列数和战士数量。
接下去M行,输入矩阵,’.’代表平地,’*’代表草丛。

出口描述 Output Description

即使德玛西亚武装和盖伦都能躲进草丛里,则输出“德姆acia
Win!”,不然输出“德姆acia Lose!”

样例输入 Sample Input

3 3 6
.**

.*.

样例输出 萨姆ple Output

Demacia Win!

多少范围及提醒 Data Size & Hint

1<=m、n<=1500
1<=k<=1500
P.S:这里对于五个壹×壹的草丛是或不是连在一齐的概念是:对于每一种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 }

 

 

分类标签 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 }