ACM-数细胞

题目描述：数细胞

一矩形阵列由数字0到9组成，数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。编程需要用到的队列及其相关函数已经实现，你只需要完成count函数以及主函数即可。 #include #include using namespace std; const int maxsize =50000; struct pos { int x; int y; }; typedef struct se { pos data[maxsize]; int front,rear; }Sequeue; void init(Sequeue *&Q) { Q=(Sequeue *)malloc(sizeof(Sequeue)); Q->front=-1; Q->rear=-1; } void change(int a[50][50],int m,int n) { int i,j; for(i=0;i<m;i++) for(j="0;j<n;j++)" if(a[i][j]!="0)" a[i][j]="1;" }="" int="" empty(sequeue="" *q)="" {="" if(q-="">rear==Q->front) return 1; else return 0; } void insertsequeue(Sequeue *&Q,int i,int j) { if((Q->rear+1)%maxsize==Q->front) { cout<<"队列已满！"<<endl; exit(0);="" }="" q-="">rear=(Q->rear+1)%maxsize; Q->data[Q->rear].x=i; Q->data[Q->rear].y=j; } void delsequeue(Sequeue *&Q,int &i,int &j) { if(Q->rear==Q->front) { cout<<"队列已空！"<<endl; exit(0);="" }="" q-="">front=(Q->front+1)%maxsize; i=Q->data[Q->front].x; j=Q->data[Q->front].y; } int count(int a[50][50],int m,int n) { } int main() { return 1; }

输入

第一行输入两个整数，分别代表矩阵的行和列 输入m*n的矩阵，由数字0到9组成。

输出

细胞个数。

样例输入

4 10

1 2 3 4 5 1 1 1 6 7

1 0 3 4 5 6 1 5 1 0

2 0 4 5 6 6 1 6 7 1

0 0 6 0 6 6 1 0 8 9

样例输出

思路：题目要使用BFS，我直接用DFS也可以A，数细胞就是数矩阵相连个数，直接每次DFS后计数即可。

// 数细胞.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

/*由1连接成多少个整块*/

#include <iostream>

#include <cstring>

const int MAX = ;

using namespace std;

int n, m, ans, map[MAX][MAX], vis[MAX][MAX];//地图

int dis[][] = { , , -, , , , , -};//标记数组，方向数组

void DFS(int x, int y)//横纵坐标，在递归中将走过的点标记为1

{

    for (int i = ; i < ; i++)

    {

        int tx = x + dis[i][];//根据方向数组改变方向

        int ty = y + dis[i][];

        if (tx >=  && tx<n && ty >=  && ty<m && map[tx][ty] && !vis[tx][ty])//在地图中且是1，并且没走过，走过的地方不能回头

        {

            vis[tx][ty] = ;//标记为走过

            DFS(tx, ty);

        }

    }

}

int main()

{

    while (cin >> n >> m)//行列

    {

        //init

        memset(map, , sizeof(map));

        memset(vis, , sizeof(vis));

        ans = ;

        //read

        for (int i = ; i<n; i++)

        for (int j = ; j < m; j++)

        {

            int t;

            cin >> t;

            if (t >=  && t <= ) map[i][j] = ;

            else map[i][j] = ;

        }

        //找起点，即找到开始递归的坐标

        for (int i = ; i<n; i++)

        {

            for (int j = ; j<m; j++)

            {

                if (map[i][j] && !vis[i][j])

                {

                    vis[i][j] = ;

                    DFS(i, j);//当递归全部结束后，说明已经不能再找到W与这部分相连

                    ans ++;

                }

            }

        }

        cout << ans;

    }

    return ;

}

巴特西

ACM-数细胞

输入

输出

样例输入

样例输出

最新文章

热门文章