【做题笔记】洛谷P1506 拯救oibh总部

跑一遍染色法，最后判断哪些位置没被染色即可

一些技巧：

为了判断方便，把字符转换成 int 型的数字。

注意边界问题

详细解释见代码

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

int a[501][501];

int x,y,ans,dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};

//dx，dy数组用于遍历上、下、左、右四个位置

//下标为0的地方用0填充即可

void dfs(int n,int m)

{

    if(n<0||m<0||n>x+1||m>y+1||a[n][m]) return ;

    //边界，如果到建设图外面或者这里有障碍就返回，没法子让洪水灌进来

    a[n][m]=1; //染色

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

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

}

int main()

{

    cin>>x>>y;

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

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

        {

            char ch;

            cin>>ch;

            if(ch=='0') a[i][j]=0;

            else a[i][j]=1;

            //字符 -> 数字

        }

    dfs(0,0); //染色，可以形象的理解为让洪水全部灌进来

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

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

            if(!a[i][j]) //如果这个点没有被水淹

                ++ans;

    cout<<ans<<endl;

    return 0;

}

巴特西

【做题笔记】洛谷P1506 拯救oibh总部

最新文章

热门文章