内存:64  时间:1

题目描述

在一个n * m 的方格地图上,某些方格上放置着炸弹。手动引爆一个炸弹以后,炸弹会把炸弹所在的行和列上的所有炸弹引爆,被引爆的炸弹又能引爆其它炸弹,这样连锁下去。

第一行输入两个整数nm,(1 <= n <= 1000 , 1 <= m <=1000)用空格隔开,接下来n行,每一行输入一个长度为m的字符串,表示地图信息。0表示没有炸弹,1表示有炸弹。

输出

输出一个整数,表示最少需要手动引爆的炸弹数。

样例输入

5 5
00010
00010
01001
10001
01000

样例输出

2

提示

尝试一下递归的连锁反应,多重递归调用。

代码如下

#include<bits/stdc++.h>
using namespace std;
int t=0;
struct node
{
    int x,y;
}a[1024];
int parent[1024];
int vis[1024];
void init()
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<1024;i++)
        parent[i]=i;
}
int find(int x)
{
    int r=x;
    while(r!=parent[r])
        r=parent[r];
    int i=x,j;
    while(parent[i]!=r)
    {
        j=parent[i];
        parent[i]=r;
        i=j;
    }
    return r;
}
void Union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
        parent[x]=y;
}
void dfs(int x)
{
    vis[x]=1;
    for(int i=0;i<t;i++)
        if(vis[i]==0&&(a[i].x==a[x].x||a[i].y==a[x].y))
    {
        Union(i,x);
        dfs(i);
    }
}
int main()
{
    char c;
    int n,m;
    init();
    scanf("%d%d",&n,&m);
    getchar();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        cin>>c;
        if(c=='1')
        {
            a[t].x=i;
            a[t].y=j;
            t++;
        }
    }
    for(int i=0;i<t;i++)
    dfs(i);
    int ans=0;
    for(int i=0;i<t;i++)
        if(parent[i]==i)
        ans++;
    cout<<ans<<endl;
    return 0;
}

代码来源于互联网,仅供参考!