当前位置：网站首页>引爆炸弹（DFS）

引爆炸弹（DFS）

2022-04-23 01:21:00 【OldLeft】

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
样例输入

5 5
00010
00010
01001
10001
01000

样例输出

2

题解
遍历每一个炸弹，同时把它所在的行和列的炸弹不断递归引爆，并将该炸弹变为0

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char mp[1005][1005];
bool vis1[1005],vis2[1005];
void dfs(int x,int y){
    
    mp[x][y]='0';
    if(!vis1[x]){
    
        vis1[x]=true;
        for(int i=0;i<m;i++){
    
            if(mp[x][i]=='1')
            dfs(x,i);
        }
    }
    if(!vis2[y]){
    
        vis2[y]=true;
        for(int i=0;i<n;i++){
    
            if(mp[i][y]=='1')
           dfs(i,y);
        }
    }
}
int main(){
    
    cin>>n>>m;
    for(int i=0;i<n;i++){
    
        cin>>mp[i];
    }
    for(int i=0;i<n;i++){
    
        for(int j=0;j<m;j++){
    
            if(mp[i][j]=='1'){
    
                ans++;
                dfs(i,j);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

版权声明
本文为[OldLeft]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43833610/article/details/115740357

边栏推荐

猜你喜欢

随机推荐