c++ Lake Counting

Lake Counting(bfs dfs)

题目描述

样例输入

10 12
W . . . . . . . . W W .
. W W W . . . . . W W W
. . . . W W . . . W W .
. . . . . . . . . W W .
. . . . . . . . . W . .
. . W . . . . . . W . .
. W . W . . . . . W W .
W . W . W . . . . . W .
. W . W . . . . . . W .
. . W . . . . . . . W .

样例输出

3

dfs代码

#include <stdio.h>//includes
#include <iostream>//up
using namespace std;//
int N, M;//定义行,列
char field[101][101];//整个院子(矩阵)
void dfs(int x,int y)//dfs
{
    field[x][y] = '.';//标为没有积水
    for (int dx = -1; dx <= 1; dx++)//枚举x坐标
    {//循环遍历8个方向
        for (int dy = -1; dy <= 1; dy++)//枚举x坐标
        {
            int nx = x + dx, ny = y + dy;//移动到遍历的方向
            if (0 <= nx && nx < N && 0 <= ny && ny < M&&field[nx][ny] == 'W')//判断是否穿墙 并且有积水
                dfs(nx, ny);//递归搜索下一个积水
        }
    }
    return;//退出
}

void solve()//solve基本输入 调用函数 
{
    int res = 0;//计数器
    for (int i = 0;i < N;i ++)//输入
    {
        for (int j = 0;j < M;j ++)//up
        {
            cin >> field[i][j];//up
        }
    }
    for (int i = 0; i < N; i++) //查找第一处积水
    {
        for (int j = 0; j < M; j++) //up
        {
            if (field[i][j] == 'W') //如果有积水
            {
                dfs(i, j);//调用函数递归查找所有节点
                res++;//计数器 + 1
            }
        }
    }
    printf("%d", res);//打印结果 Print res
}

int main() //main
{
    scanf("%d%d", &N,&M);//输入行和列
    solve();//调用solve
   // system("pause");
    return 0;//return
}