描述

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

现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。

输入

　　第一行输两个整数 n,m，用空格隔开。

　　接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。

数据约定：

　　对于 60% 的数据：1 ≤ n, m ≤ 100；

　　对于 100% 的数据： 1 ≤ n, m ≤ 1000；

输出

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

输入样例 1 

5 5
00010
00010
01001
10001
01000

输出样例 1

2

解题思路

　　这道题是典型的DFS（其实都很典型），我们从头搜索，如果有炸弹没有被炸，就引爆它，然后把它所引爆的炸弹继续引爆下去......直到搜完。而我用来联系炸弹之间的是用的

题解

#include<bits/stdc++.h>
using namespace std;
char dt[1050][1050];//存图
int a[1050];//横坐标
int b[1050];//纵坐标
int ans=0;//引爆炸弹次数
int n,m;
void dfs(int x,int y)//核心部分
{
    dt[x][y]='0';//给炸弹解除标记
    if(a[x]==0)//如果这行没被炸
    {
        a[x]=1;//那么现在被炸了
        for(int i=1;i<=m;i++)
        {
            if(dt[x][i]=='1')//引爆这行的
            {
                dfs(x,i);//继续爆
            }
        }
    }
    if(b[y]==0)//列的操作，同上
    {
        b[y]=1;
        for(int i=1;i<=n;i++)
        {
            if(dt[i][y]=='1')
            {
                dfs(i,y);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>dt[i][j]; //存图
        }
    } 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(dt[i][j]=='1')//搜炸弹
            {
                dfs(i,j);
                ans++;//引爆++
            }
        }
    } 
    cout<<ans;//输出
    return 0;
}