C++ achieve fans today headline interview question

  • 2020-06-07 05:01:25
  • OfStack

Question Description:

1 stadium C stands can accommodate M*N fans. Officials want to know how many fans there are and how many are the largest.

Seat selection characteristics: the same fan group will choose adjacent seats, different fan groups choose non-adjacent seats. (Adjacent includes before and after adjacent, right and left adjacent, diagonally adjacent);

Given a 2-dimensional field of M*N, 0 means no one at the position, 1 means there are people at the position, and we hope to output the number of team groups P, the largest team group number Q.

Input:

In line 1, two Numbers, M and N, are separated by English commas.
Next, M lines, each with N Numbers separated by English commas.

Output:

1 row, 2 Numbers, P and Q.

Input sample:

[

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

]

Output sample:

[

6,8

]

Other:

For 100% of the data, 1 < =M,N < e3 = 3.

This question is an obvious depth-first search and is 10 points easy.

But when you look at the input examples, you see that there is one character after each data, and the carriage return is also a character.

So we have to deal with the data first.

The auxiliary tool we need to use is getchar (). People who don't know can use getchar () as a claw. Every time a character of char type is entered, getchar () can accurately capture it.

But getchar () ignores the first character of each line.

So we can define an array and use getchar () after the first number. You can store all zeros and ones in an n*m 2-dimensional array.

dfs, for example, is 10 minutes. You just need to determine the eight possible directions and use a counter to count them.

But to avoid repeating the same route, it's also to avoid time overruns. So we can define an array of type bool to record the path traveled.

At the same time, write a two-tier nested loop in the main function, find each 1, and then dfs.

Also be careful to use scanf and printf.

You also need to use 1 putchar () at the end, which is equivalent to output 1 character.

On the fast one, 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);
 }

conclusion


Related articles: