计蒜客蓝桥杯模拟赛5 引爆炸弹

以你之姓@ 2022-06-15 05:54 172阅读 0赞

题目：

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

![Center][]

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

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int n,m;
    int map[110][110]={0};
    void dfs(int x, int y)
    {
    	int i,j,xx,yy;
    	//向上
    	xx = x;
    	yy = y;
    	while (xx>=1){
    		if (map[xx][yy] == 1){
    			map[xx][yy] = 0;
    			dfs(xx, yy);
    		}
    		xx--;
    	} 
    	//向下 
    	xx = x;
    	yy = y;
    	while (xx<=n){
    		if (map[xx][yy] == 1){
    			map[xx][yy] = 0;
    			dfs(xx, yy);
    		}
    		xx++;
    	}
    	//向左
    	xx = x;
    	yy = y;
    	while (yy>=1){
    		if (map[xx][yy] == 1){
    			map[xx][yy] = 0;
    			dfs(xx, yy);
    		}
    		yy--;
    	}
    	//向右
    	xx = x;
    	yy = y;
    	while (yy<=n){
    		if (map[xx][yy] == 1){
    			map[xx][yy] = 0;
    			dfs(xx, yy);
    		}
    		yy++;
    	} 
    }
    int main()
    {
    	char ch;
    	int cnt=0;
    	cin>>n>>m;
    	for (int i=1; i<=n; i++)
    	{
    		for (int j=1; j<=m; j++)
    		{
    			cin>>ch;
    			map[i][j] = ch-'0';
    		}
    	}
    	for (int i=1; i<=n; i++)
    	{
    		for (int j=1; j<=m; j++)
    		{
    			if (map[i][j] == 1)
    			{
    				cnt++;
    				map[i][j] = 1;
    				dfs(i,j);
    			}
    		}
    	}
    	cout<<cnt<<endl;
    	return 0;
    }

[Center]: /images/20220615/36b56c422ba34aa4bb3db0abd61c6eac.png