您现在的位置是：首页 >技术杂谈 >算法日记14：SC339（二维联通，洪水灌溉）DFS+set网站首页技术杂谈

一、题目

二、题解：

2.1：由题目得出，此题为类迷宫问题，因此我们可以考虑DFS/BFS

• 假如使用DFS来解决问题，可以得出时间复杂度为$O(n\ast m)$，且$(1\le n,m\le 10^3)$，因此时间复杂度大致为$1e9$，可以解决问题
• BFS同理，一样为$1e9$

2.2:首先，让我们来用DFS来解决问题

1、因为题目要求我们按照升序来进行答案的输出，因此我们可以考虑使用$set()$函数/使用(vector+sort)

2、在迷宫问题中，我们需要考虑不能重复访问同一块区域的问题，因此我们使用st[N]数组来表示某个点是否范围过

const int N = 1007;
int g[N][N];
bool st[N][N];  //用来统计这个点是否被计算过
int n,m,k;
set<int>res;    //存储答案

3、样例的输入：应当是访问到合理的区局块时（如果[x][y]没有被走过,并且可以走），才开始计算面积，也就是才开始调用DFS函数来进行这个区域的覆盖+面积计算

for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {        
           if(st[i][j]==false && g[i][j]==0) //如果[x][y]没有被走过,并且可以走
           {
               int cnt=dfs(i,j);
               if(cnt>=k) res.insert(cnt);
           }       
        }
    }

• 这样，既防止了重复访问，又减轻的时间复杂度

4、DFS函数

• 1):因为我们需要计算一整块的面积总和（每一块洪水区域的方块总和）因此需要使用int型的DFS递归函数
• 2):在每一次DFS的递归过程中，我们一直往下递，直到访问到了非法的边界，就开始归(return) 一步步求出总的面积和，最后返回递归的总和即可

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dfs(int x,int y)    //能进DFS意味着一定可以走
{
    
    int temp=1; //用来存储单块面积
    st[x][y]=true;  //走
        
    for(int i=0;i<4;i++)    //四联通
    {
        int a=x+dx[i],b=y+dy[i];
            
        if(a<1 || a>n || b<1 || b>m) continue;  //越界
        if(st[a][b]==true) continue;    //走过不走
        if(g[a][b]==1) continue;    //表示障碍物,不走
            
        temp+=dfs(a,b); //面积+dfs块
    }
    return temp;
}

5、注意题目中有多个样例，因此在每一轮的样例中，都要清空状态数组st和答案数组set<int>res

//清空
res.clear();
memset(st,0,sizeof(st));

三、完整代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1007;
int g[N][N];
bool st[N][N];  //用来统计这个点是否被计算过
int n,m,k;
set<int>res;    //存储答案

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

int dfs(int x,int y)    //能进DFS意味着一定可以走
{
    
    int temp=1; //用来存储单块面积
    st[x][y]=true;  //走
        
    for(int i=0;i<4;i++)    //四联通
    {
        int a=x+dx[i],b=y+dy[i];
            
        if(a<1 || a>n || b<1 || b>m) continue;  //越界
        if(st[a][b]==true) continue;    //走过不走
        if(g[a][b]==1) continue;    //表示障碍物,不走
            
        temp+=dfs(a,b); //面积+dfs块
    }
    return temp;
}

void solve() 
{
    //清空
    res.clear();
    memset(st,0,sizeof(st));
    
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {        
           if(st[i][j]==false && g[i][j]==0) //如果[x][y]没有被走过,并且可以走
           {
               int cnt=dfs(i,j);
               if(cnt>=k) res.insert(cnt);
           }       
        }
    }
    if(res.empty()) //set为空
    {
        cout<<-1<<'
';
        return ;
    }
    for(auto i:res)
    {
        cout<<i<<' ';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;cin>>_;
    while (_--) solve();
    return 0;
}