纪中21日c组T2 2117. 【2016-12-30普及组模拟】台风-白红宇

纪中21日c组T2 2117. 【2016-12-30普及组模拟】台风

阅读量：5272 次

发布时间：2019-06-14

本文共 2360 字，大约阅读时间需要 7 分钟。

2117. 台风

(File IO): input:storm.in output:storm.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述

天气预报频道每天从卫星上接受卫星云图。图片被看作是一个矩阵，每个位置上要么是”#”,要么”.”,”#”表示该位置没有云，”.”表示有云，地图上每个位置有多达8个相邻位置，分别是，左上、上、右上、左、右、左下、下、右下8个方向，一块云是由连续的”.”组成。

给你一幅卫星云图和形成台风所需云的大小，要你计算出有几个台风以及最大台风的大小。我们用云的大小表示台风的大小。

输入

第一行输入两个整数M和N，表示行和列数。接下来M行,每行N个字符”#”或”.”描述地图的情况。第M+2行是一个正整数K,表示要形成台风，云的大小至少为K.

输出

两个用空各隔开的整数N和S,分别表示台风的个数，和最大台风的大小。

样例输入

6 11 #####.##### ####.####.# ###..##.#.# ##...###### ######..... ########### 4

样例输出

2 7

数据范围限制

原题此处未给出，我提交后估计$0 \leq n,m \leq 5000$左右

Solution

这是今天最简单的一道题，许多同学都拿了分

但是我也提交了

我却是0分……

哈哈……不重要了

第一行输入两个整数M和N，表示行和列数。接下来M行,每行N个字符”#”或”.”描述地图的情况。

在读入的地方，我发现我写反了，于是改正了

但是在枚举dfs起点时，我没有检查到！

这就导致dfs的起点会在矩阵外，并且有一些点还不会被扫到……

样例没有过，但是自己出的样例到是过了！

埋怨自己吧……

Algorithm

bool dt（map）数组存点，bool vis数组存是否已访问

从上到下，从左到右，枚举每一个未访问且值为1（.）的点进行dfs

dfs里在这个点的八个方向再搜点，再进行dfs

使用返回值来递归答案

使用一个int数组存可能形成台风的云的面积

最后for扫一遍判断是否比k大，并打擂台求最大值即可……

Code

1 #pragma GCC optimize(2) 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
           8 #include
           
             9 #include
            
             10 #include
             
              11 #define IL inline12 using namespace std;13 IL int read()14 {15 int res=0;16 char ch=getchar();17 while(ch<'0'||ch>'9')18 ch=getchar();19 while(ch>='0'&&ch<='9')20 res=(res<<1)+(res<<3)+(ch^48),ch=getchar();21 return res;22 }23 int m,n,ans,s,k,num;24 bool dt[10001][10001];25 bool vis[10001][10001];26 int storm[100001];27 int mov[8][2]={28 1,1,29 1,0,30 1,-1,31 32 0,1,33 0,-1,34 35 -1,-1,36 -1,0,37 -1,1,38 };39 IL int dfs(int x,int y)40 {41 if(x<1||x>m||y<1||y>n) return 0;42 if(vis[x][y]) return 0;43 if(!dt[x][y]) return 0;44 vis[x][y]=1;45 int _new=0;46 for(int to=0;to<8;to++)47 {48 _new+=dfs(x+mov[to][0],y+mov[to][1]);49 }50 return _new+1;51 }52 53 54 int main()55 {56 // freopen("storm.in","r",stdin);57 // freopen("storm.out","w",stdout);58 m=read();n=read();59 char ch;60 for(int i=1;i<=m;i++)61 for(int j=1;j<=n;j++)62 {63 ch=getchar();64 if(ch!='.'&&ch!='#'){65 j--;continue;66 }67 dt[i][j]=(int)(ch=='.');68 }69 k=read();70 for(int i=1;i<=m;i++)71 for(int j=1;j<=n;j++)72 if((!vis[i][j])&&dt[i][j]) {73 storm[num++]=dfs(i,j);74 }75 while(num--)76 if(storm[num]>=k) ans++,s=max(s,storm[num]);77 cout<
              
               <<" "<

Impression

AWSL

End

转载于:https://www.cnblogs.com/send-off-a-friend/p/11387966.html

你可能感兴趣的文章