题目描述

从红魔馆的大门往里面看就可以看到一个大花园。园内不止种花，而且还种植了各种魔法药材供帕秋莉使用。芙兰对花园里的药材感到好奇，于是她就问红魔馆的门番兼园丁花园里有多少种不同的药材。但是红师傅在看门的时候不是在睡觉就是在睡觉！她只知道各种药材被分割开来，互不相邻。现在你从帕琪那里拿到了花园的地图，药材用小写字母表示，其他花草用’*'表示，空地用空格表示，你能替那个门番回答二小姐的问题吗？

顺便一提，同种药材也有优劣之分，帕琪可能会用不同的小写字母表示同一种药材，不同种类的药材一定是被其他花草或是空地分割开的。

输入

输入一个正整数n表示地图有n行

接着n行每行有一个字符串,包含小写字母,空格和’*'三种字符,意义如题面。

注意：每行都有可能以若干空格开头，且每行长度也不一定相同!

输出

一个正整数，表示药材的种类数。

样例输入

abca

bbb*

abc e

ccc

样例输出

提示

于10%的数据:n≤10,字符串长度≤10;

对于30%的数据: n≤100,字符串长度≤200;

对于100%的数据: n≤1000,字符串长度≤400;

思路:

因为不确定列数,而且输入带有空格,要用getline来读入

记录下最长的字符串长度当作地图的列数,对空格标记下

接下来BFS求连通块即可

AC代码

#include 
#include 
#include 
#include 
using namespace std;
 
int n,max_y,ans;
char map[1010][1010];
bool exist[1010][1010];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
string tmp;
bool check(int x,int y)
{
 
    if(exist[x][y] == 0 && x >= 1 && x <= n && y >= 1 && y <= max_y && map[x][y] >= 'a' && map[x][y] <= 'z')
        return 1;
    return 0;
}
 
 
 
void BFS(int x,int y)
{
    if(exist[x][y]) return;
    else if(check(x,y))
    {
        ans++;
        exist[x][y] = 1;
        queue<pair<int,int>> que;
        que.push(pair<int,int>(x,y));
        while(!que.empty())
        {
            int xx,yy;
            for(int i = 0; i < 4; i++)
            {
                xx = que.front().first + dx[i];
                yy = que.front().second + dy[i];
                if(check(xx,yy))
                {
                    que.push(pair<int,int>(xx,yy));
                    exist[xx][yy] = 1;
 
                }
            }
            que.pop();
        }
    }
}
 
 
 
int main()
{
    cin >> n;
    getline(cin,tmp);
    for(int i = 1; i <= n; i++)
    {
        getline(cin,tmp);
        int k = tmp.size();
        max_y = max(max_y,k);
        for(int j = 0; j < k; j++)
        {
            if(tmp[j] >= 'a' && tmp[j] <= 'z') map[i][j+1] = tmp[j];
            else exist[i][j+1] = 1;
 
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= max_y; j++)
        {
            BFS(i,j);
            exist[i][j] = 1;
        }
    }
    cout << ans << endl;
 
    return 0;
}