必威电竞2801 LOL-盖伦的家居草计划。codevs 2801 LOL-盖伦的家居草计划。

2801 LOL-盖伦的家居草计划

 

时间限制: 1 s

空间范围: 256000 KB

题目等级 : 黄金 Gold

 

 

 

题目叙述 Description

大庭广众,LOL这款伟大之玩,有个给盖伦的威猛。他的宏大的处在当被外特意喜蹲草丛阴人(XL:蹲草阴人也总算勇敢?!CZQ:没道,个个都是这样玩的)。某日,德玛西亚和诺克萨斯之间又起了平等摆战斗,嘉文四世希望盖伦能带领一出K人的德玛西亚军事出战。

打仗有在召唤师峡谷。整个召唤师峡谷被划分成M行N列的一个矩阵,矩阵中出空地和几切片草丛。这几乎片草丛中略大死、有些绷有点。一个1×1的草莽能盛3独兵卒,盖伦坚信蹲草偷袭战术能克服诺克萨斯军队,所以他要他的队伍会一体蹲进草丛里。当然,为了不影响盖伦的征战,盖伦用单独把占连起来的一致切开草丛(不管草丛有差不多可怜)。

必威电竞 1

输入描述 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底草从,它与周围(上下左右)的草莽是连在一起的。

 时间限制: 1
s

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

 

 

 空间限制: 256000
KB

 题目等级 : 黄金
Gold

题目叙述 Description

确定性,LOL这款伟大的嬉戏,有只受盖伦的英勇。他的赫赫的远在当被他特意好蹲草丛阴人(XL:蹲草阴人也毕竟勇敢?!CZQ:没道,个个都是这般玩的)。某日,德玛西亚暨诺克萨斯之间以起了同庙会战斗,嘉文四世希望盖伦能带领一开K人的德玛西亚武装出战。

征发生在召唤师峡谷。整个召唤师峡谷被分成M行N列的一个矩阵,矩阵中来空地和几切开草丛。这几切开草丛中多少老可怜、有些大有些。一个1×1之草莽能包容3独兵卒,盖伦坚信蹲草偷袭战术能克服诺克萨斯军队,所以他梦想他的武装部队会全部蹲进草丛里。当然,为了不影响盖伦的交锋,盖伦用单独把占连起来的平切开草丛(不管草丛有差不多颇)。

必威电竞 2

输入描述 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之草从,它与周围(上下左右)的草莽是连在一起的。

传送门  点这个开展 

自身大盖伦居然出现在这样回之写里,而且数量范围说了k>=1
末一个触及k=0 ,我大盖伦连个保镖也不曾吗。

代码  BFS

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int h,ans,i,j,m,n,k,xf[5]={1,-1,0,0},yf[5]={0,0,1,-1};
char map[1501][1501];
int ss(int x,int y)
{
    int xx,yy,head=0,tail=1,f[3000][3];
    f[tail][1]=x;f[tail][2]=y;
    do{
        head++;
        for(i=0;i<4;++i)
        {
            xx=f[head][1]+xf[i];yy=f[head][2]+yf[i];
            if(xx>=0&&xx<m&&yy>=0&&yy<n&&map[xx][yy]=='.')
            {
                tail++;
                f[tail][1]=xx;
                f[tail][2]=yy;
                map[xx][yy]='#';
            }
        }
    }while(head<=tail);
    return head;
}
int main()
{
    cin >> m >> n >> k;
    if(k==0)
    {
        cout<<"Demacia Win!";
        return 0;
    }
    for (i = 0 ;i < m ;++i)
    {
        for (j = 0 ;j < n ;++j)
        cin >> map[i][j];
    }
    for (i = 0 ;i < m ;++i)
    {
        for(j = 0 ;j < n ;++j)
        {
            if (map[i][j]=='.')
            {
                ans=max(ss(i,j),ans);
            }
        }
    }
    if(ans*3>=k)
        cout<<"Demacia Win!";
    else cout<<"Demacia Lose!";
}

 

admin

网站地图xml地图