本文共 739 字，大约阅读时间需要 2 分钟。

题目：

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

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

输入格式

第一行输两个整数 n,mn,mn,m，用空格隔开。 接下来 nnn 行，每行输入一个长度为 mmm 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。 数据约定： 对于 60%60%60% 的数据：1≤n,m≤1001 \le n, m \le 1001≤n,m≤100； 对于 100%100%100% 的数据：1≤n,m≤1000 1 \le n, m \le 10001≤n,m≤1000； 数据量比较大，不建议用cin输入。

输出格式

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

5 50001000010010011000101000

样例输出

2

这个题我用深搜写的，题意是1是炸弹，现在要引爆炸弹，炸弹所在的行和列都会引爆，为了节省时间，可以把炸完的炸弹所在的行和列标记，然后去寻找该炸弹所在行或者列的其他炸弹。

程序代码：

#include
   
    #include
    
     char s[1100][1100];int a[1100][1100];int c[1010],b[1010];int n,m;void dfs(int x,int y){
   	int i,j,k;	a[x][y]=0;	if(b[x]==0)//标记行	{
   		b[x]=1;		for(i=0;i
    
   

转载地址：http://wrxzi.baihongyu.com/