题目链接
题意:给们一个n*m的方格地图,在这个地图上一些网格中有炸弹,我可以选择引爆其中一个炸弹,当炸弹爆炸后,会将该💣所在的行和列的炸弹也引爆,被引爆的炸弹,也依次引爆它们所在行和列中的💣,问我最少需要人工引爆几次炸弹,才能把所有的炸弹全部引爆完
思路:这一题给我启发用并查集来解决这一题,是炸弹之间爆炸的连锁效应,一个💣爆炸会回关联到同行、列的炸弹,之后又会连锁到其他同行列的炸弹,所以我们可以把在同行或列的炸弹放入到同一个集合中去,这样不同集合间的炸弹引爆是不会影响下一个集合的炸弹的,所以最后我们只需要判读集合的数量就是这题的答案了
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
void fre() { freopen(","r",stdin), freopen(","w",stdout); }
#define ll long long
const int mxn = 2005;
char ar[mxn][mxn];
int br[mxn][mxn];
int pre[2000005];int find(int x)
{if(pre[x] == x) return x;return pre[x] = find(pre[x]);
}void Union(int x, int y)
{int fx = find(x);int fy = find(y);if(fx != fy)pre[fx] = fy;
}int cnt;
void init()
{cnt = 0;for(int i = 0; i < 2000005 ; i ++)pre[i] = i;memset(br, 0, sizeof(br));
}int main()
{/* fre(); */init(); int m, n;scanf("%d %d ", &m, &n);for(int i = 0; i < m; i ++)for(int j = 0; j < n; j ++){scanf("%c", &ar[i][j]);if(ar[i][j] == '1'){br[i][j] = cnt;for(int a = j - 1; a >= 0; a --){if(ar[i][a] == '1'){Union(cnt, br[i][a]);break;}}for(int a = i - 1; a >= 0; a --){if(ar[a][j] == '1'){Union(cnt, br[a][j]);break;}}cnt ++;}if(j == n - 1)getchar();}int ans = 0;for(int i = 0; i < cnt; i ++)if(pre[i] == i)ans ++;printf("%dn", ans);return 0;
}
本文发布于:2024-02-02 09:26:29,感谢您对本站的认可!
本文链接:https://www.4u4v.net/it/170683718842872.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |