题目描述
在一个n * m 的方格地图上,某些方格上放置着炸弹。手动引爆一个炸弹以后,炸弹会把炸弹所在的行和列上的所有炸弹引爆,被引爆的炸弹又能引爆其它炸弹,这样连锁下去。
第一行输入两个整数n,m,(1 <= n <= 1000 , 1 <= m <=1000)用空格隔开,接下来n行,每一行输入一个长度为m的字符串,表示地图信息。0表示没有炸弹,1表示有炸弹。
输入
输出一个整数,表示最少需要手动引爆的炸弹数。
输出
尝试一下递归的连锁反应,多重递归调用。
样例输入
5 5
00010
00010
01001
10001
01000
样例输出
2
参考代码
#include<stdio.h>
char a[1001][1001];
void boom(int m,int n,int x,int y)
{
int i;
for (i=0;i<y;i++)
{
if(a[m][i]=='1')
{
a[m][i]='0';
boom(m,i,x,y);
}
a[m][i]='0';
}
for (i=0;i<x;i++)
{
if(a[i][n]=='1')
{
a[i][n]='0';
boom(i,n,x,y);
}
a[i][n]='0';
}
}
int main()
{
int i,j,m,n,sum=0;
scanf("%d%d",&m,&n);
for (i=0;i<m;i++)
scanf("%s",a[i]);
for (i=0;i<m;i++)
for (j=0;j<n;j++)
if(a[i][j]=='1')
{
sum++;
boom(i,j,m,n);
}
printf("%d",sum);
return 0;
}
解析
暂无