洛谷 P1767 家族_NOI导刊2010普及（10）

题目描述

在一个与世隔绝的岛屿上，有一个有趣的现象：同一个家族的人家总是相邻的（这里的相邻是指东南西北四个方向），不同的家族之间总会有河流或是山丘隔绝，但同一个家族的人不一定有相同姓氏。现在给你岛上的地图，求出岛上有多少个不同的家族。岛上的地图有n行，每行有若干列，每个格子中要么是“ ”，表示大海，要么是“*”，表示河流或山丘，要么是小写字母，表示一户人家的姓氏。

输入输出格式

输入格式：

第一行是个数字N，表示下面信息的行数。接下来是N行字符，每行由小写字母和*号组成，有些行的最前面也可能包含若干连续的空格，表示这些区域是大海，每一行最多不超过200个字符。

输出格式：

一个数字，表示家族数。

输入输出样例

输入样例#1：

4
*zlw**pxh
l*zlwk*hx*
w*tyy**yyy
        zzl

输出样例#1：

说明

10%的数据，n≤1。 30%的数据，n≤10。 100%的数据，n≤100每一行最多不超过200个字符。

_NOI导刊2010普及（10）

dfs

屠龙宝刀点击就送

为啥这么写不对。。

作为一名不愿意调用iostream的人我真是很气恼

　　 scanf("%d",&n);
    char str[N],ch=getchar(); 
    for(int i=1;i<=n;++i)
    {
        gets(str);
        int len=strlen(str);
        m[i]=len;
        for(int j=1;j<=len;++j)
        {
            if(str[j-1]>='a'&&str[j-1]<='z') G[i][j]=1;
            else G[i][j]=0; 
        }
    }

正解

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#define N 500
using namespace std;

int n,G[N][N],ans,m[N],fx[5]={1,-1,0,0},fy[5]={0,0,-1,1};
void bfs(int x,int y)
{
    queue<pair<int,int> >q;
    q.push(make_pair(x,y));
    G[x][y]=0;
    for(;!q.empty();)
    {
        int nowx=q.front().first,nowy=q.front().second;
        q.pop();
        for(int i=0;i<4;++i)
        {
            int tx=nowx+fx[i],ty=nowy+fy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m[tx]&&G[tx][ty])
            G[tx][ty]=0,q.push(make_pair(tx,ty));
        }
    }
}
int Main()
{
    string str;
    scanf("%d",&n);getline(cin,str);
    for(int i=1;i<=n;++i)
    {
        getline(cin,str);
        m[i]=str.length();
        for(int j=1;j<=m[i];++j)
         if(str[j-1]>='a'&&str[j-1]<='z') G[i][j]=1;
    }
    for(int i=1;i<=n;++i)
     for(int j=1;j<=m[i];++j)
      if(G[i][j]) bfs(i,j),ans++;
    printf("%d
",ans);
    return 0;
}
int sb=Main();
int main(int argc,char *argv[]){;}