Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【Aizu - 0118】Property Distribution

Sky丨Star 2019-07-11 21:50:00 阅读数:49 评论数:0 点赞数:0 收藏数:0

-->Property Distribution

原文是日语,算了算了,直接上我大中华母语吧

 Descriptions:

在H * W的矩形果园里有苹果、梨、蜜柑三种果树, 相邻(上下左右)的同种果树属于同一个区域,给出果园的果树分布,求总共有多少个区域。 

Input

多组数据,每组数据第一行为两个整数H、W(H <= 100, W <= 100), H =0 且 W = 0代表输入结束。以下H行W列表示果园的果树分布, 苹果是@,梨是#, 蜜柑是*。

Output

对于每组数据,输出其区域的个数。

Sample Input

10 10
####*****@
@#@@@@#*#*
@##***@@@*
#****#*@**
##@*#@@*##
*@@@@*@@@#
***#@*@##*
*@@@*@@##@
*@*#*@##**
@****#@@#@
0 0

Output for the Sample Input

33

题目链接:

https://vjudge.net/problem/Aizu-0118

 

dfs加染色吧 比较经典的入门题

偷偷告诉你们 样例只有一组哦

 

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 105
using namespace std;
int n,m;
int num;//总共几种颜色
int vis[Maxn][Maxn];//染色计数
char mp[Maxn][Maxn];//原始地图
int dt[][]= {{,},{-,},{,},{,-}};//4个方向
void dfs(int x,int y,char ch)//横纵坐标 那个地方的字母
{
    if(vis[x][y])
        return;
    vis[x][y]=num;
    for(int i=; i<; i++)
    {
        int tx=x+dt[i][];
        int ty=y+dt[i][];
        if(!vis[tx][ty]&&mp[tx][ty]==ch)//没有被染色且这个地方是"ch"
            dfs(tx,ty,ch);
    }
}
int main()
{
    while(cin>>n>>m,n+m)
    {
        num=;//初始化
        MEM(mp,'X');
        MEM(vis,);
        for(int i=; i<n; i++)//读入地图
            for(int j=; j<m; j++)
                cin>>mp[i][j];
        for(int i=; i<n; i++)//开始搜索
            for(int j=; j<m; j++)
            {
                if(!vis[i][j]&&mp[i][j]!='X')
                {
                    num++;
                    dfs(i,j,mp[i][j]);
                }
            }
        cout<<num<<endl;
    }
}

 

版权声明
本文为[Sky丨Star]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sky-stars/p/11172999.html