VIJOS-P1294 拯救OIBH总部

洛谷 P1506 拯救oibh总部

洛谷传送门

JDOJ：1405: VIJOS-P1294 拯救OIBH总部

JDOJ传送门

Description

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

Input

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

Output

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

Sample Input

样例输入1 4 5 00000 0000 000 0000 样例输入2 5 5 ***** 00* 0 00* *****

Sample Output

样例输出1 1 样例输出2 5

题解：

一道深搜的题，坑点在读入和递归出口上，已经在代码中高亮说明，请大家尽情享用。

#include<cstdio>

#include<iostream>

using namespace std;

int n,m,ans;

int map[501][501];

char ch;

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

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

void dfs(int x,int y)

{

    if(x<0 || y<0 || x>n+1 || y>m+1 || map[x][y])//gaoliang

        return;

    map[x][y]=2;

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

        dfs(x+dx[i],y+dy[i]);

}

int main()

{

    scanf("%d%d",&n,&m);

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

        for(int j=1;j<=m;j++)

        {

            cin>>ch;//gaoliang

            if(ch=='0')

                map[i][j]=0;

            else

                map[i][j]=1;

        }

    dfs(0,0);

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

        for(int j=1;j<=m;j++)

            if(!map[i][j])

                ans++;

    printf("%d",ans);

    return 0;

}