gpt4 book ai didi

C++ 实现球迷 今日头条面试题

转载 作者:qq735679552 更新时间:2022-09-28 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++ 实现球迷 今日头条面试题由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

试题描述:

一个球场C的球迷看台可容纳M*N个球迷。官方想统计一共有多少球迷群体,最大的球迷群体有多少人.

球迷选座特性:同球迷群体会选择相邻座位,不同球迷群体选择不相邻的座位。(相邻包括前后相邻、左右相邻、斜对角相邻); 。

给定一个M*N的二维球场,0代表该位置没人,1代表该位置有人,希望输出球队群体个数P,最大的球队群体人数Q.

输入:

第一行,2个数字,M、N,使用英文逗号隔开。 接下来M行,每行N个数字,使用英文逗号隔开.

输出:

一行,2数字,P和Q.

输入样例:

10,10 0,0,0,0,0,0,0,0,0,0 0,0,0,1,1,0,1,0,0,0 0,1,0,0,0,0,0,1,0,1 1,0,0,0,0,0,0,0,1,1 0,0,0,1,1,1,0,0,0,1 0,0,0,0,0,0,1,0,1,1 0,1,1,0,0,0,0,0,0,0 0,0,0,1,0,1,0,0,0,0 0,0,1,0,0,1,0,0,0,0 0,1,0,0,0,0,0,0,0,0 。

输出样例:

6,8 。

其他:

对于100%的数据,1<=M,N<=3e3.

这道题是一道明显的深度优先搜索,而且十分简单.

但是在看到输入示例后会发现每个数据的后面都存在着一个字符,而且回车也属于字符.

所以我们要先对数据进行处理.

我们需要使用的的辅助工具就是getchar()了,不知道的人可以把getchar()作为一个爪子,每当一个char类型的字符被输入后,getchar()就可以准确的捕捉到他.

但是getchar()是会忽略每行第一个字符的.

所以我们可以定义一个数组,在取完第一个数后再使用getchar()。就可以把所有的0和1存储在一个n*m的二维数组中了.

再说dfs,就十分简单了,只需要判断可能走的8个方向,再使用一个计数器计数就可以了.

但是为了避免走重复的路,也是为了避免时间超限。所以我们可以定义一个bool类型的数组,记录走过的路.

同时在主函数中做写一个两层的嵌套循环,找到每个1,再进行dfs.

也要注意使用scanf和printf.

在最后也需要使用一个putchar(),相当于是输出一个字符.

论速度那个快       putchar(),getchar>scanf,printf>cin,cout.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stdio.h>
using namespace std;
int n,m,l,k,sum,ans,cnt;
char a[4000][4000],op;
bool b[4000][4000]={0};
int dfs( int x, int y)
{
  if (a[x-1][y]== '1' &&b[x-1][y]==0)
  {
   b[x-1][y]=1;
   dfs(x-1,y);
   ans++;
  }
  if (a[x][y+1]== '1' &&b[x][y+1]==0)
  {
   b[x][y+1]=1;
   dfs(x,y+1);
   ans++;
  }
  if (a[x-1][y+1]== '1' &&b[x-1][y+1]==0)
  {
   b[x-1][y+1]=1;
   dfs(x-1,y+1);
   ans++;
  }
  if (a[x+1][y]== '1' &&b[x+1][y]==0)
  {
   b[x+1][y]=1;
   dfs(x+1,y);
   ans++;
  }
  if (a[x][y-1]== '1' &&b[x][y-1]==0)
  {
   b[x][y-1]=1;
   dfs(x,y-1);
   ans++;
  }
  if (a[x+1][y-1]== '1' &&b[x+1][y-1]==0)
  {
   b[x+1][y-1]=1;
   dfs(x+1,y-1);
   ans++;
  }
  if (a[x+1][y+1]== '1' &&b[x+1][y+1]==0)
  {
   b[x+1][y+1]=1;
   dfs(x+1,y+1);
   ans++;
  }
  if (a[x-1][y-1]== '1' &&b[x-1][y-1]==0)
  {
   b[x-1][y-1]=1;
   dfs(x-1,y-1);
   ans++;
  }
  return ans;
}
int main()
{
  scanf ( "%d%c%d" ,&n,&op,&m);
  for ( int i=1;i<=n;i++)
  {
   for ( int j=1;j<=m;j++)
   {
    getchar ();
    a[i][j]= getchar ();
   }
  }
  for ( int i=1;i<=n;i++)
  {
   for ( int j=1;j<=m;j++)
   {
    ans=0;
    if (a[i][j]== '0' )b[i][j]=1;
     if (a[i][j]== '1' &&b[i][j]==0)
     {
     sum++;
     cnt=max(cnt,dfs(i,j));
     }
   }
  }
  char p= ',' ;
  printf ( "%d" ,sum);
  putchar (p);
  printf ( "%d" ,cnt);
  }

总结 。

以上所述是小编给大家介绍的C++ 实现球迷 今日头条面试题,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我网站的支持! 。

原文链接:https://www.cnblogs.com/FXY-180/p/9492160.html 。

最后此篇关于C++ 实现球迷 今日头条面试题的文章就讲到这里了,如果你想了解更多关于C++ 实现球迷 今日头条面试题的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com