计蒜客模拟赛（五）第九题

2024-03-29 17:08

文章标签 模拟第九计蒜客

本文主要是介绍计蒜客模拟赛（五）第九题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计蒜客模拟赛第九题

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

现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输两个整数 n, m，用空格隔开。
接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。
数据约定：
对于60% 的数据： 1≤n,m≤100；
对于 100% 的数据： 1≤n,m≤1000；
数据量比较大，不建议用cin输入。
输出格式
输出要手动引爆的炸弹数。

分析

1.看到这道题我的思路是首先我需要确定炸弹的个数，以及每个炸弹所对应的坐标，由于用到横纵坐标两个参数，所以考虑决定选用结构体构建炸弹的点.
2.根据题目给定的要求需要以字符串，所以决定采用字符数组更为合理，char类型，即输入采用二维数组，根据所给定的m,n进行。
3.对于每一颗炸弹，他均有两个参数，分别是行号和列号，对于所有的炸弹遍历我们将按照，横纵坐标任意一个值相同我们将他们连接起来，然后我们将炸弹形成连通图
题目要求
4.对于不同的炸弹不同的老大大大哥，所以将这些炸弹的大哥哥，放入栈内，最后去重，得到的vector长度即为最终的最优答案

代码实现

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;//首先记录  炸弹即 1  存在的位置坐标
#define Max 1000char a[Max][Max];//每行可以容纳的数量
int pre[Max];
int k = 0;struct Node
{int x;int y;
}p[100];//100个炸弹点int find(int x)
{int r = x;while (r != pre[r])r = pre[r];int i = x, j;while (i != r)//路径压缩{j = pre[i]; // 在改变上级之前用临时变量  j 记录下他的值 pre[i] = r; //把上级改为根节点i = j;}return r;
}int main()
{vector<int> elem;int n, m;cin >> n >> m;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> a[i][j];if (a[i][j] == '1')//记录炸弹，并且统计炸弹的个数{k++;p[k].x = i;p[k].y = j;}}}//炸弹的初始化，设置他们的前驱结点均为自己for (int i = 1; i <= k; i++){pre[i] = i;}//如果任意两个炸弹的  横或者纵坐标相同则连接两个点for (int i = 1; i <= k; i++){for (int j = i + 1; j <= k; j++){if (p[i].x == p[j].x || p[i].x == p[j].y){pre[j] = i;}}}//将每个炸弹的大大大哥找到，压入栈内/*记录每个1的坐标然后对相同的坐标进行爆破，行坐标相同直接爆破，纵坐标相同直接爆破*/for (int i = 1; i <= k; i++){elem.push_back(find(i));}//排序sort(elem.begin(), elem.end());elem.erase(unique(elem.begin(), elem.end()),elem.end());//unique()函数将重复的元素放置在最后//erase将重复的第一个元素开始，到最后一个元素开始，全部擦除cout << elem.size() << endl;//数字的种类既是最终的答案/*for (int i = 1; i <= k; i++)//前驱验证{cout << "第" << i << "个的前驱" << pre[i] << endl;}*//*得到最终的炸弹个数*///cout << k << endl;return 0;
}