山东第一届省赛 Balloons (dfs)

前言：

第一次做的时候没读懂题，唉~

题目描述：

Both Saya and Kudo like balloons. One day, they heard that in the central park, there will be thousands of people fly balloons to pattern a big image.

They were very interested about this event, and also curious about the image.

Since there are too many balloons, it is very hard for them to compute anything they need. Can you help them?

You can assume that the image is an N∗N matrix, while each element can be either balloons or blank.

Suppose element A and element B are both balloons. They are connected if:

They are adjacent;

There is a list of element C1,C2,…,Cn, while A and C1 are connected, C1 and C2 are connected …Cn and B are connected.

And a connected block means that every pair of elements in the block is connected, while any element in the block is not connected with any element out of the block.

To Saya, element A(xa,ya) and B(xb,yb) is adjacent if |xa−xb|+|ya−yb|≤1.

But to Kudo, element A(xa,ya) and element B(xb,yb) is adjacent if |xa−xb|≤1 and |ya−yb|≤1

They want to know that there’s how many connected blocks with there own definition of adjacent?

大意：就是数给出矩阵在两个人条件下的连通块

Saya的条件是一个气球上下左右四个方向算是它的相邻气球

Kudo的条件是一个气球所有八个方向都算是它的相邻气球

所有相邻的气球共同组成一个连通块，数最终有多少个连通块

输入：

The input consists of several test cases.

The first line of input in each test case contains one integer N (0

Each of the next N lines contains a string whose length is N, represents the elements of the matrix. The string only consists of 0 and 1, while 0 represents a block and 1 represents balloons.

The last case is followed by a line containing one zero.

输出：For each case, print the case number (1, 2 …) and the connected block’s numbers with Saya and Kudo’s definition. Your output format should imitate the sample output. Print a blank line after each test case.

大意：多组输入，每组给出数组的行列大小，以 0 结束输入，每组答案之间有空行

思路：dfs搜索即可

搜索每一个点，如果是气球就返回true，此时把所有与他连通的气球和本身都标记为已走过，那么在后面的搜索中，要是遇到已走过的气球那就直接跳过，只有每个连通块的第一个气球会被计数

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e5+100;
const int p = 1e4;
const double eps = 1e-8;
int n,cnt1,cnt2,cnts;
int flag[101][101];//标记数组
int a[101][101];
char c;
int dir1[4][2]={0,1,0,-1,1,0,-1,0};//四个方向
int dir2[8][2]={0,1,0,-1,1,0,-1,0,1,1,-1,-1,1,-1,-1,1};//八个方向
bool dfs1(int x,int y)//Saya
{
  if(x<1||y<1||x>n||y>n) return false;//超出范围不计数
  if(flag[x][y]==1||a[x][y]==0) return false;//没气球或者已经走过也是不计数
  flag[x][y]=1;//走过的标记
  for(int i=0;i<4;i++)
  {
    int xx=x+dir1[i][0];
    int yy=y+dir1[i][1];
    dfs1(xx,yy);
  }//搜索相邻的气球
  return true;//块里的第一个气球要计数
}
bool dfs2(int x,int y)//kudo
{
  if(x<1||y<1||x>n||y>n) return false;
  if(flag[x][y]==1||a[x][y]==0) return false;
  flag[x][y]=1;
  for(int i=0;i<8;i++)
  {
    int xx=x+dir2[i][0];
    int yy=y+dir2[i][1];
    dfs2(xx,yy);
  }//把所有连通的地方标记上 
  return true;
}
int main()
{
  while(cin>>n)
  {
    if(n==0) return 0;
    cnt1=0;cnt2=0;
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
      {
        cin>>c;
        if(c=='1') a[i][j]=1;
        else a[i][j]=0;     
      }
    }
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
      {
        if(dfs1(i,j)) cnt1++; 
      } 
    }
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
      {
        if(dfs2(i,j)) cnt2++; 
      } 
    }
    cout<<"Case "<<++cnts<<": "<<cnt1<<" "<<cnt2<<endl<<endl;
  }
}