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。

#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++ 实现球迷 今日头条面试题，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • C++数字三角形问题与dp算法

    题目:数字三角形 题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和. 输入:第一行值n,代表n行数值:后面的n行数据代表每一行的数字. 输出:经过数字的最大和. 例: 输入: 4 1 3 2 4 10 1 4 3 2 20 输出: 24 分析:这也是一个典型的贪心算法无法解决的问题,同样可以用动态规划(dp算法)来解决.把边界数字首先初始化到结果矩阵中,再根据状态方程完成结果矩阵的遍历.需要注意的就是数组不是矩形而是三角形,与传统

  • C++使用异或运算实现交换两个数的值

    异或交换两个数的值是资源开销最小的方法,不需要中介数,原理简单的来说就是异或的负负得正 代码: #include <stdio.h> int main() { int a = 11, b = 22; printf("a=%d b=%d\n", a, b); a = a ^ b; b = a ^ b; a = a ^ b; printf("a=%d b=%d\n", a, b); } 编译: gcc test.c -o test 执行: a=11 b=22

  • C++实现产生随机数和相应的猜拳小游戏实例代码

    C++实现产生随机数和相应的猜拳小游戏实例代码

    一.简介 c++中,产生随机数的通用方法就是调用 srand()和 rand()  函数. Rand 单纯的rand()会返回一个0至RAND_MAX之间的随机数值,而RAND_MAX的值与int位数有关,最小是32767.不过rand()是一次性的,因为系统默认的随机数种子为1,只要随机数种子不变,其生成的随机数序列就不会改变. 其实,对于rand()的范围,我们是可以进行人为设定的,只需要在宏定义中定义一个random(int x)函数,就可以生成范围为0至x的随机数值.当然,也可以定义为r

  • 解决C++全局变量只能初始化不能赋值的问题

    C++中,全局变量只能声明.初始化,而不能赋值 也就是说,下面这样是不被允许的: #include <cstdio> using namespace std; int a; a = 2; int main() { return 0; } 错误提示是: C++ requires a type specifier for all declarations 声明.初始化与赋值的区别: 声明:int a; 初始化:int a = 2;(在声明的时候顺带赋值叫做初始化) 赋值:a = 2; 只有定义(i

  • c++使用正则表达式提取关键字的方法

    下面看下c++通过正则表达式提取关键字,代码如下所示: string text = "岳云鹏的对象叫铁锤"; regex pattern("(.*)的对象叫(.*)"); smatch results; if (regex_match(text, results, pattern)) { for (auto it = results.begin(); it != results.end(); ++it) cout << *it << endl

  • 详解C++ 动态内存分配与命名空间

    1.C++中的动态内存分配 通过new关键字进行动态内存申请 C++中的动态内存申请时基于类型进行的 delete关键用于内存释放 C语言其实是不支持动态内存分配的,是通过malloc库函数来实现的,可能有一些硬件根本不支持malloc:而C++ new是一个关键字,不管在任意编译器上,任意硬件平台上都是能够进行动态内存分配的,这是本质区别. malloc是基于字节来进行动态内存分配的,new则是基于类型来进行动态内存分配 // 变量申请: Type * pointer = new Type;

  • Visual Studio Code配置C、C++环境并编写运行的方法

    弄了半天,总算弄好了,结合网上的教程,整理分享一下~ 总体流程: 下载安装vscode 安装cpptools插件 安装编译.调试环境 修改vscode调试配置文件 下载安装vscode  https://code.visualstudio.com/Download Visual Studio Code 64位 v1.26.0 官方最新安装版:https://www.jb51.net/softs/606746.html Visual Studio Code 32位 v1.26.0 官方最新安装版:

  • C++模拟键盘按键的实例

    这个与模拟鼠标点击的函数差不多,直接上函数 keybd_event(VK_RETURN,0,0,0); keybd_event(VK_RETURN,0,KEYEVENTF_KEYUP,0); 这是模拟按下.抬起回车键 我直接上一个我曾经用它与一些函数写的一个刷屏程序 我用自己的小号试过,如果对方用的是手机,效果很显著 #include<iostream> #include<windows.h> using namespace std; int b[11000],top=0; cha

  • 浅析Java、C/C++、JavaScript、PHP、Python分别用来开发什么?

    首先,我们先普及一下编程语言的基础知识.用任何编程语言来开发程序,都是为了让计算机干活,比如编写一篇文章,下载一首MP3等,而计算机干活的CPU只认识机器的指令,所以,尽管不同的编程语言差异极大,最后都得"翻译"成CPU可以执行的机器指令.理论上任何语言干任何事情几乎都可以, 但是主要干什么那就不一样了. 01.Java java常常跟"企业"联系在一起, 因为具备一些很好的语言特性, 以及丰富的框架, 在企业应用中最被青睐, 你总可以听到关于J2EE,JSP,Hi

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

    试题描述: 一个球场C的球迷看台可容纳M*N个球迷.官方想统计一共有多少球迷群体,最大的球迷群体有多少人. 球迷选座特性:同球迷群体会选择相邻座位,不同球迷群体选择不相邻的座位.(相邻包括前后相邻.左右相邻.斜对角相邻): 给定一个M*N的二维球场,0代表该位置没人,1代表该位置有人,希望输出球队群体个数P,最大的球队群体人数Q. 输入: 第一行,2个数字,M.N,使用英文逗号隔开. 接下来M行,每行N个数字,使用英文逗号隔开. 输出: 一行,2数字,P和Q. 输入样例: 10,10 0,0,0

  • IOS仿今日头条滑动导航栏

    IOS仿今日头条滑动导航栏

    之前在我们平台给大家分享了网易首页导航封装类.网易首页导航封装类优化,今天在前两个的基础上仿下今日头条. 1.网易首页导航封装类中主要解决了上面导航的ScrollView和下面的页面的ScrollView联动的问题,以及上面导航栏的便宜量. 2.网易首页导航封装类优化中主要解决iOS7以上滑动返回功能中UIScreenEdgePanGestureRecognizer与ScrollView的滑动的手势冲突问题. 今天仿今日头条滑动导航和网易首页导航封装类优化相似,这个也是解决手势冲突,UIPanG

  • iOS自定义UITabBar仿今日头条效果

    iOS自定义UITabBar仿今日头条效果

    动机 关于自定义 TabBar,早就有过很多讨论,开源网站上也有很多造好的轮子,多半是纯代码实现有个性的 TabBar,当然我们可以很方便的使用它.周末闲着没事干,自己也写了一下,模仿今日头条的 TabBar 效果,实现方式是Storyboard + 代码. 效果图 实现步骤在 Storyborad 上搭建项目基础结构 在界面上设置每个 TabBarItem 的相关属性 需要自定义的 item 不需要在界面上设置. 自定义 UITabBarViewController 目的 替换默认的 UITa

  • java实现简单的爬虫之今日头条

    前言 需要提前说下的是,由于今日头条的文章的特殊性,所以无法直接获取文章的地址,需要获取文章的id然后在拼接成url再访问.下面话不多说了,直接上代码. 示例代码如下 public class Demo2 { public static void main(String[] args) { // 需要爬的网页的文章列表 String url = "http://www.toutiao.com/news_finance/"; //文章详情页的前缀(由于今日头条的文章都是在group这个目

  • Android仿今日头条APP实现下拉导航选择菜单效果

    Android仿今日头条APP实现下拉导航选择菜单效果

    本文实例为大家分享了在Android中如何实现下拉导航选择菜单效果的全过程,供大家参考,具体内容如下 关于下拉导航选择菜单效果在新闻客户端中用的比较多,当然也可以用在其他的项目中,这样可以很方便的选择更多的菜单.我们可以让我们的应用顶部有左右滑动或进行切换的导航菜单,也可以为了增强用户体验在应用中添加这样的下拉导航选择菜单效果. 关于它的实现原理,其实也是挺简单的,就是使用PopupWindow来进行展现,在显示时控制其高度并配置以相应的动画效果.在PopupWindow中我使用GridView

  • Android使用RecyclerView实现今日头条频道管理功能

    Android使用RecyclerView实现今日头条频道管理功能

    使用过今日头条的伙计们对这个效果肯定很熟悉.拖拽可排序,点击标签后可以删除.今天我们采用RecyclerView来实现. 实现思路: 通过ItemTouchHelper来绑定RecyclerView的子控件触摸事件. 当滑动拖拽的时候,通知适配器来交换两个子控件的显示位置. 更改数据源,使数据源与子空间显示内容一致. 这就是实现的基本思路,是不是很简单?当然,首先要了解一下ItemTouchHelper这哥们儿是干啥的,有什么作用. This is a utility class to add

  • Android仿今日头条滑动页面导航效果

    Android仿今日头条滑动页面导航效果

    最近项目中用到了滑动页面,也就是和目前市场上很火的"今日头条"页面滑动类似,在网上找了一下,大部分都是用ViewPager来实现的,刚开始我用的是ViewPager+ViewGroup,上面的标题按钮用的是HorizontalScrollView,写完之后感觉效果比较生硬,果断换掉,发现了一个效果比较好的第三方,也就是今天的主题:PagerSlidingTabStrip.好了,下面来具体介绍一下PagerSlidingTabStrip,进行一下源码解析. 一.看一下demo的样子吧 二

  • Android 仿今日头条简单的刷新效果实例代码

    Android 仿今日头条简单的刷新效果实例代码

    点击按钮,先自动进行下拉刷新,也可以手动刷新,刷新完后,最后就多一行数据.有四个选项卡. 前两天导师要求做一个给本科学生预定机房座位的app,出发点来自这里.做着做着遇到很多问题,都解决了.这个效果感觉还不错,整理一下. MainActivity package com.example.fragmentmytest; import android.content.DialogInterface; import android.graphics.Color; import android.os.B

  • Android 仿今日头条评论时键盘自动弹出的效果(推荐)

    Android 仿今日头条评论时键盘自动弹出的效果(推荐)

    Android 仿今日头条评论时键盘自动弹出的效果:当点击评论时,弹出对话框,同时弹出软键盘,当点击返回键时,将对话框关闭,不只是关闭软键盘. 效果图: 对这个对话框设置一个style效果: <style name="inputDialog" parent="@android:style/Theme.Holo.Light.Dialog"> <item name="android:windowBackground">@col

  • Android实现仿网易今日头条等自定义频道listview 或者grideview等item上移到另一个view中

    Android实现仿网易今日头条等自定义频道listview 或者grideview等item上移到另一个view中

    我这里只是简单的用了两个listview来实现的,先上效果图.比较粗糙.预留了自定义的空间. 思路: 从上图应该可以看的出来.就是上下两个listview.点击下面的ltem.会动态的移动到上一个listview的最后.上面的listview 为listview1,下面的为listview2. 点击listview2,获取到view ,设置一个动画,移动到listview1 ,listview2中删除被点的item.listview1中新增一个. 上代码: Mainactivity.java 部

随机推荐