防御洪水【dfs深度搜索】

题目描述

OIBH被突来的洪水淹没了> .< 还好OIBH总部有在某些重要的地方起一些围墙，用*号表示，而一个封闭的*号区域洪水是进不去的……现在给出OIBH的围墙建设图，问OIBH总部没被淹到的重要区域（由" 0" 表示）有多少。

输入

第一行是两个数，x和y（x,y< =500） 第二行及以下是一个由*和0组成的x*y的图。

输出

输出没被水淹没的OIBH总部的“0”的数量。

样例输入

5 4
00000
00*00
0*0*0
00*00
5 5
*****
*0*0*
**0**
*0*0*
*****

输出样例

1
5

思路

首先将连通的区域进行标记，然后遍历剩余未标记累积求和。个人认为此题还是比较简单。

参考代码

#include <iostream>
 
#define MAX_LEN 505
 
using namespace std;
 
int n,m;
 
char Map[MAX_LEN][MAX_LEN];
 
int dir[8][2] = {{0,-1},{0,1},{-1,0},{1,0},};
 
void dfs(int x,int y)
{
    if(x<0 || x>=n || y<0 || y>=m ||Map[x][y] == '*')
    {
        return ;
    }
     
    if(Map[x][y] == '0')
    {
        Map[x][y] = '*';//标记
    }
     
    for(int i=0;i<4;i++)//继续从其他方向搜索
    {
        dfs(x+dir[i][0],y+dir[i][1]);
    }
    return ;
}
 
int main()
{
    while(cin>>m>>n)
    {
        for(int i=0;i<n;i++)
        {
            cin>>Map[i];
        }
        int count = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if((i==0||i==n-1||j==0||j==m-1) && Map[i][j] == '0')
                {
                    dfs(i,j);
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(Map[i][j] == '0')
                {
                    count++;
                }
            }
        }
         
        cout<<count<<endl;
    }
    return 0;
}