洛谷 P1506 拯救oibh总部

P1506 拯救oibh总部

题目背景

oibh总部突然被水淹没了！现在需要你的救援……

题目描述

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

输入输出格式

输入格式：

第一行是两个数，x和y（x,y<=500）

第二行及以下是一个由*和0组成的x*y的图。

输出格式：

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

输入输出样例

输入样例#1： 

样例输入1

4 5

00000

00*00

0*0*0

00*00

样例输入2

5 5

*****

*0*0*

**0**

*0*0*

*****

输出样例#1： 

样例输出1

1

样例输出2

5
思路：搜索。

#include<iostream>

#include<cstdio>

using namespace std;

char ch;

int x,y,ans;

int map[][];

int dx[]={,,-,,};

int dy[]={,,,,-};

void dfs(int m,int n)  {

    if(m<||n<||m>x+||n>y+||map[m][n])

        return;

    map[m][n]=;

    for(int i=;i<=;i++)

        dfs(m+dx[i],n+dy[i]);

}

int main(){

    scanf("%d%d",&x,&y);

    for(int i=;i<=x;i++)

        for(int j=;j<=y;j++){

            cin>>ch;

            if(ch=='')

                map[i][j]=;

            else map[i][j]=;

        }

    dfs(,);

    for(int i=;i<=x;i++)

        for(int j=;j<=y;j++)

            if(!map[i][j])

                ans++;

    printf("%d",ans);

    return ;

}