【POJ - 2386】Lake Counting (dfs+染色)


-->Lake Counting

直接上中文了

Descriptions:

由于近日阴雨连天,约翰的农场中中积水汇聚成一个个不同的池塘,农场可以用 N x M (1 <= N <= 100; 1 <= M <= 100) 的正方形来表示。农场中的每个格子可以用'W'或者是'.'来分别代表积水或者土地,约翰想知道他的农场中有多少池塘。池塘的定义:一片相互连通的积水。任何一个正方形格子被认为和与它相邻的8个格子相连。 

给你约翰农场的航拍图,确定有多少池塘

Input

Line 1: N 和 M 

Lines 2..N+1: M个字符一行,每个字符代表约翰的农场的土地情况。每个字符中间不包含空格

Output

Line 1: 池塘的数量

Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample Output

3

Hint

样例解释: 
左下方,左上方,右边三块
 
题目链接:
 
经典dfs+染色例题,很适合新手,值得注意的是这题不是传统的4个方向,注意四个斜角也要算进去,那就是8个方向了
 
AC代码
#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 1000
using namespace std;
int n,m;
int num;//总共几种颜色
int vis[Maxn][Maxn];//染色计数
char mp[Maxn][Maxn];//原始地图
int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}};//八个方向
bool judge(int xx,int yy)//判断是否满足条件
{
    if(!vis[xx][yy]&&mp[xx][yy]=='W')//没有被染色且这个地方是"W"
        return true;
    return false;
}
void dfs(int x,int y)
{
    if(vis[x][y])
        return;
    vis[x][y]=num;
    for(int i=0;i<8;i++)//八个方向
    {
        int tx=x+dt[i][0];
        int ty=y+dt[i][1];
        if(judge(tx,ty))
            dfs(tx,ty);
    }
}
int main()
{
    num=0;
    MEM(vis,0);
    cin>>n>>m;
    for(int i=0;i<n;i++)//读入地图
        for(int j=0;j<m;j++)
            cin>>mp[i][j];
    for(int i=0;i<n;i++)//开始搜索
        for(int j=0;j<m;j++)
        {
            if(judge(i,j))
                {
                    num++;
                    dfs(i,j);
                }
        }
    cout<<num<<endl;
}

 


作者:Sky丨Star,发布于:2019/07/11
原文:https://www.cnblogs.com/sky-stars/p/11166538.html