程序设计:引爆炸弹 (计蒜客 - A1139)

简介: 程序设计:引爆炸弹 (计蒜客 - A1139)

题目:

在一个 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 5
00010
00010
01001
10001
01000

样例输出

2

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

程序代码:

#include<stdio.h>
#include<string.h>
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<m;i++)
    {
      if(a[x][i]==1)
        dfs(x,i);
    }
  }
  if(c[y]==0)//标记列
  {
    c[y]=1;
    for(j=0;j<n;j++)
    {
      if(a[j][y]==1)
        dfs(j,y);
    }
  }
}
int main()
{
  int i,k,j,sum;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    sum=0;
    memset(c,0,sizeof(c));
    memset(b,0,sizeof(b));
    for(i=0;i<n;i++)
      scanf("%s",s[i]);
    for(i=0;i<n;i++)
      for(j=0;j<m;j++)
        a[i][j]=s[i][j]-'0';
    for(i=0;i<n;i++)
      for(j=0;j<m;j++)
      {
        if(a[i][j]==1&&b[i]==0&&c[j]==0)
        {
          dfs(i,j);
          sum++;
        } 
      }
    printf("%d\n",sum);
  }
  return 0;
} 





目录
打赏
0
0
0
0
63
分享
相关文章
C语言十九练——养兔子
C语言十九练——养兔子
92 0
【C语言】民间传统游戏——三子棋详细教学
三子棋(介绍) 游戏分为双方对战,双方依次在9宫格棋盘上摆放棋子,率先将自己的三个棋子走成一条线就视为胜利,而对方就算输了,但是三子棋在很多时候会出现和棋的局面。 🌞
一日一技:你的代码是如何被炫技毁掉的
一日一技:你的代码是如何被炫技毁掉的
129 0
小波从此逝,江海寄余生,不但是文坛巨擘还是不世出的编程奇才,天才程序员王小波
二十六年前,王小波先生因病于北京逝世,享年四十四周岁。喜爱他的人,都知道他是一个特立独行的人,拥有谦虚与自豪并存的强大气质,并且留下无数传世作品,无可争议的文坛巨擘,他的力量、有趣,对媚众形式束缚的反抗,以及一以贯之的,对待生活无比真诚的态度都让我们为之倾倒。 然而,鲜为人知的是,他不仅仅在文学上造诣非凡,与此同时,他还是一位不世出的编程奇才。在整个九十年代,除了和文字跳舞,王小波还将他的才华通过键盘喷涌而出,天才的脑细胞幻化为一行一行的代码, 挥洒自如,回转如意。王小波在编程领域的惊人艺业,我们也许可以通过他的书信以及著作中的内容略窥一二。
小波从此逝,江海寄余生,不但是文坛巨擘还是不世出的编程奇才,天才程序员王小波
程序人生 - 为什么大人永远不懂孩子的世界?
程序人生 - 为什么大人永远不懂孩子的世界?
126 0
程序人生 - 为什么大人永远不懂孩子的世界?

相关实验场景

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等