服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++ 实现球迷 今日头条面试题

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

2021-07-01 15:53FXY_ssf C/C++

这篇文章主要介绍了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++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27