C++与矩阵、n*n 网格等相关的cοde
按钮
N x N 网格的每个单元格要么是 0，要么是 1。您将获得两个这样的 N x N 网格：初始网格和最终网格。初始 N x N 网格的每一行和每一列都有一个按钮。按行按钮可切换该行中所有单元格的值，按列按钮可切换该列中所有单元格的值。
您需要找到将网格从初始配置转换为最终配置所需的最少按下按钮次数，以及必须按下的按钮才能进行此转换。
当初始配置和最终配置相同时，打印“0”。
输入
第一行包含 t，测试用例的数量（大约 10 个）。然后是测试用例。
每个测试用例具有以下形式：
- 第一行包含 n，即棋盘的大小 (1 ≤ n ≤ 1000)。
- 接下来有 n 行。第 i 行包含 n 个空格分隔的整数，表示初始网格的第 i 行。每个整数要么是 0，要么是 1。
- 接下来的 n 行代表最终的网格，格式与上面相同。
输出
对于每个测试用例，输出按下行按钮的次数，然后输出必须按下的行按钮。接下来打印按列按钮的次数，后跟必须按的列按钮的 0 索引索引。按下按钮的总数必须最小化。
如果无法从初始配置达到最终配置，则输出“-1”。如果有多个解决方案，请打印其中之一。
输入：
1
3
0 0 0
1 1 0
1 1 0
1 1 0
1 1 1
1 1 1
输出：
1
0
1
2
虽然它在我的机器上工作得很好，但它不接受 codechef 的解决方案，并给了我一个错误的答案。任何人都可以指导我该怎么做吗？
代码是用 C++ 编写的，并使用 g++ 编译器进行编译。
Buttons
Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column.
You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.
When the initial and the final configurations are the same, print "0".
Input
The first line contains t, the number of test cases (about 10). Then t test cases follow.
Each test case has the following form:
- The first line contains n, the size of the board (1 ≤ n ≤ 1000).
- n lines follow. The ith line contains n space separated integers representing the ith row of the initial grid. Each integer is either a 0 or a 1.
- n lines follow, representing the final grid, in the same format as above.
Output
For each test case, output the number of row-button presses, followed by the row buttons that must be pressed. Print the number of column-button presses next, followed by 0-indexed indices of the column buttons that must be pressed. The total number of button presses must be minimized.
Output "-1" if it is impossible to achieve the final configuration from the initial configuration. If there is more than one solution, print any one of them.
Input:
1
3
0 0 0
1 1 0
1 1 0
1 1 0
1 1 1
1 1 1
Output:
1
0
1
2
Though it works absolutely fine on my machine,it doesnt accept a solution at codechef and gives me a wrong answer.Can anyone guide me what to do pls pls pls??
Code has been written in C++ and compiled using g++ compiler.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在发布的代码中，我会在计算“matrixc”后修改代码。我发现很难超越这一点，因此我将停止查看代码并讨论问题。对于没有代码的人，矩阵 C = 初始矩阵 - 最终矩阵。矩阵位于二进制域上。
在此类问题中，请查看解的对称性。存在三种对称性。一是按钮的顺序并不重要。如果您采用有效的解决方案并重新排列它，您将得到另一个有效的解决方案。另一个对称性是，按两次按钮与根本不按按钮是一样的。最后一个对称性是，如果你取一个有效解的补集，你会得到另一个有效解。例如，在 3x3 网格中，如果 S = { row1, row3, col1 } 是一个解，则 S' = { row2, col2, col3 } 也是一个解。
因此，您所需要做的就是找到一种解决方案，然后利用对称性。由于您只需要找到一个，因此只需做您能想到的最简单的事情即可。我只需查看第 1 列和第 1 行来构建解决方案，然后根据整个矩阵检查该解决方案。如果此解决方案为您提供了 N 个以上的按钮来按下 NxN 网格，则采用该解决方案的补集，您最终会得到一个较小的按钮。
对称性是计算机科学中非常重要的概念，几乎无处不在。了解这个问题的对称性可以让你在不检查每个可能的解决方案的情况下解决它。
PS 你说这段代码是 C++，但如果你从顶部删除
#include，它也是完全有效的 C。如果将其编译为 C 语言，编译时间可能会少很多。In the code posted, I would revise the code after you calculate "matrixc". I find it very difficult to follow beyond that point, so I'm going to stop looking at the code and talk about the problem. For those without the code, matrix C = initial matrix - final matrix. The matrices are over the binary field.
In problems like these, look at the symmetries in the solution. There are three symmetries. One is the order of the buttons does not matter. If you take a valid solution and rearrange it, you get another valid solution. Another symmetry is that pressing a button twice is the same as not pressing it at all. The last symmetry is that if you take the complement of a valid solution, you get another valid solution. For example, in a 3x3 grid, if S = { row1, row3, col1 } is a solution, then S' = { row2, col2, col3 } is also a solution.
So all you need to do is find one solution, then exploit the symmetry. Since you only need to find one, just do the easiest thing you can think of. I would just look at column 1 and row 1 to construct the solution, then check the solution against the whole matrix. If this solution gives you more than N buttons to press for an NxN grid, then take the solution's complement and you'll end up with a smaller one.
Symmetry is a very important concept in computer science and it comes up almost everywhere. Understanding the symmetries of this problem is what allows you to solve it without checking every possible solution.
P.S. You say this code is C++, but it is also perfectly valid C if you remove
#include <iostream>from the top. It might take a lot less time to compile if you compile it as C.