当前位置：首页 > article >正文

开心消消乐

article 2025/3/10 6:03:30

题目描述

给定一个N行M列的二维矩阵，矩阵中每个位置的数字取值为0或1。矩阵示例如：
1100
0001
0011
1111
现需要将矩阵中所有的1进行反转为0，规则如下：
1）当点击一个1时，该1便被反转为0，同时相邻的上、下、左、右，以及左上、左下、右上、右下8 个方向的1（如果存在1）均会自动反转为0；
2）进一步地，一个位置上的1被反转为0时，与其相邻的8个方向的1（如果存在1）均会自动反转为0；

按照上述规则示例中的矩阵只最少需要点击2次后，所有值均为0。请问，给定一个矩阵，最少需要点击几次后，所有数字均为0？

输入描述

第一行输入两个数字N，M，分别表示二维矩阵的行数、列数，并用空格隔开

之后输入N行，每行M个数字，并用空格隔开

输出描述

最少需要点击几次后，矩阵中所有数字均为0

用例

输入
4 4
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1

输出 2
说明无

如下图所示：
在这里插入图片描述
即，含有1的块数总共2块，需要点击2次才能把所有1变为0。

解题思路

本题可以用并查集求解。步骤如下：

根据输入矩阵的行数和列数，初始化并查集。实现并查集中初始化、查找根节点、添加节点关系等方法；
遍历输入矩阵；
如果当前位置数值为0，该位置不是1,1的总块数需要减1，即并查集的size减1；
如果当前位置为1，向上下左右四个方向搜索临近点。如果搜索位置不越界，且数值为1，则添加点关系；
遍历结束，得到并查集的Size，即1的总块数；
释放并查集对象，返回总块数。

代码实现

用文章开头算例为输入条件，根据上面的思路编写代码。

class UnionFindCol//并查集类
{
public:
	int Size;
	vector<int> ParentList;
	UnionFindCol(int size)//初始化并查集
	{
		Size = size;
		for (int i = 0; i < size; ++i)
		{
			ParentList.push_back(i);
		}
	}

	int GetRoot(int index)//获取根节点
	{
		if (ParentList[index] == index) return index;
		ParentList[index] = GetRoot(ParentList[index]);//路径压缩
		return ParentList[index];
	}

	void Join(int index1,int index2)//添加节点间关系
	{
		int parent1 = GetRoot(index1);//点1根节点
		int parent2 = GetRoot(index2);//点2根节点
		if (parent1 == parent2) return;//根节点一致，不处理
		ParentList[parent2] = parent1;//根节点不一致，节点2根节点的根节点重置
		Size--;//块数-1
	}
};

int GetCount(std::vector<std::vector<int>> matrix)
{
	int rowCount = matrix.size();
	int colCount = matrix[0].size();
	vector<int> dirs = { 0,1,0,-1,0 };
	UnionFindCol* ufc = new UnionFindCol(rowCount * colCount);
	for (int i = 0; i < rowCount; ++i)
	{
		for (int j = 0; j < colCount; ++j)
		{
			if (matrix[i][j] == 0) { ufc->Size--; continue; }
			int index = i * colCount + j;
			for (int k = 0; k < 4; ++k)
			{
				int nextRow = i + dirs[k];
				int nextCol=j+ dirs[k+1];
				if (nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount && matrix[nextRow][nextCol] != 0)
				{
					int nextIndex= nextRow * colCount + nextCol;
					ufc->Join(index, nextIndex);
				}
			}
		}
	}
	int result = ufc->Size;;
	delete ufc;
	return result;
}

int main()
{
	std::vector<std::vector<int>> matrix =
	{
		{1,1,0,0},
		{0,0,0,1},
		{0,0,1,1},
		{1,1,1,1},
	};
	int result = GetCount(matrix);
	std::cout << result;
}