掷硬币计数游戏C++数据结构！
Coin Flipping Counting Game C++ Data Structure！
问题来了。在游戏中，有一个长方形的硬币网格，正面 = 1，反面 = 0。游戏有一个简单的规则：玩家不能掷一枚硬币，相反，玩家可以选择一排（或一列）和同时翻转该行（或该列）中的所有硬币。游戏的objective就是找出抛硬币的策略，使正面硬币的数量最大。第一个输入值是行 >> 然后是列 >> 和硬币
Sample inputs:
5 4
1010
0101
1010
1010
1010 //Sample output of this: 20
5 4
0010
1101
0110
0110
1011 //Sample output of this: 17
我用计数'0'和'1'的方法完成了我的代码，如果零更多，切换它。这种方法只通过了简单的测试用例，但是当进入到困难的测试用例时，它失败了，因为有些情况需要推特不止一次。我想不出另一种更好的处理方式。
这是我的代码：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool ConeIsMore(vector <vector<char> > table, int size, int j) {
int countzero = 0;
int countone = 0;
for (int i = 0; i < size; i++) {
(table[i][j] == '0')?++countzero: ++countone;
}
if (countone >= countzero) {
return true;
}
return false;
}
bool RoneIsMore(vector <vector<char> > table, int size, int i) {
int countzero = 0;
int countone = 0;
for (int j = 0; j < size; j++) {
(table[i][j] == '0') ? ++countzero : ++countone;
}
if (countone >= countzero) {
return true;
}
return false;
}
int main() {
//Initialise row and column
int row;
int column;
while (cin >> row >> column) {
//Initiallise 2D vector
vector <vector<char> > table(row, vector<char>(column));
//get each digit of number and store it into number
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
cin >> table[i][j];
}
}
//check for column
for (int j = 0; j < column; j++) {
if (!ConeIsMore(table, row, j)) {
for (int i = 0; i < row; i++) {
(table[i][j] == '0') ? table[i][j] = '1' : table[i][j] = '0';
}
}
}
//check for row
for (int j = 0; j < row; j++) {
if (!RoneIsMore(table, column, j)) {
for (int i = 0; i < column; i++) {
(table[j][i] == '0') ? table[j][i] = '1' : table[j][i] = '0';
}
}
}
//Count One in the table
int ans = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
(table[i][j] == '1') ? (ans++) : (ans = ans);
}
}
cout << ans << endl;
}
return 0;
}
在研究测试用例的过程中，我发现有些需要检查各种时间，这让我觉得我的方法不是很好。谁能提出更好的处理方法？非常感谢。
以下是较难的测试用例：
5 4
0010
1101
0110
0110
1011 //17
5 4
0110
1111
0101
0110
0100 //16
5 4
0110
1001
0011
1110
1000 //16
5 4
1100
0001
1111
0101
1010 //16
5 4
0101
0110
1001
1000
0011 //16
5 4
0111
1100
0100
1000
1011 //16
5 4
1101
1110
0111
1011
0111 //15
5 4
1100
1001
0110
1001
1000 //17
您或许应该输出您的策略结果，而不仅仅是计算正面人数，以便更好地了解正在发生的事情。改进实施的两个想法：
1) 当行或列中的硬币数量为偶数时，您的代码没有执行您描述的算法。你说：
counting the '0' and '1', if zero is more, switch it.
您的代码：
if (!ConeIsMore(table, row, j)) {
// switch it
}
没有更多人头时切换。
结果，当硬币数量为偶数时，您也会切换
正面和反面的数量相等。当计数相等时切换是推测性的，目前尚不清楚它是否会有所改善，因此您或许应该特别对待它。
2) 你也许可以继续迭代直到没有
尾巴多于头的列或行。
从数据结构开始 std::vector<bool> table(row*column) 可能会更有效率，但也需要更加小心才能正确处理。
我们需要跟踪如果您翻转每一列或每一行，您的正面总数会增加多少。对于给定的行或列，如果您决定翻转该行或列，请计算反面的数量减去正面的数量以产生正面的净增加。将这些值存储在两个数组中，一个用于列，一个用于行。此时您应该有两个数组，一个大小行和一个大小列，具有负值、零值或正值。
5 4
1010
0101
1010
1010
1010 //Sample output of this: 20
row: [0, 0, 0, 0, 0]
column: [-3, 3, -3, 3]
现在遍历行向量和列向量，如果遇到正值，则需要翻转该行或列。如果遇到负值，不要翻转。 如果您遇到零值，您应该根据该行或该列的第一枚硬币是否已经是正面来决定翻转。这将有助于解决边缘情况，例如这个：
2 2
10
01 // output should be: 4
row: [0, 0] // How can we know to flip row 1 but not row 0? Because arr[0][0] = 1 already
column: [0, 0]
您必须采取的另一个步骤是，当您翻转一行时，您还必须更新列数组中的值，反之亦然。您还应该更新内存中的二维硬币数组以反映新状态。第一次翻转后，问题状态看起来像这样
5 4
1010
1010 // this row was flipped because arr[1][0] was 0
1010
1010
1010
row: [0, 0, 0, 0, 0]
column: [-5, 5, -5, 5]
继续，直到没有更多的行或列可以翻转。实现中有递归的好机会。
以下是我在Peter Cheng帮忙提供算法后的代码。它一直工作到计算行和列但不能翻转 table。
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int RcountDifference(vector <vector<char> > table, int col, int var) {
int Difference = 0;
for (int j = 0; j < col; j++) {
if (table[var][j]=='1') {
Difference -= 1;
}
else {
Difference += 1;
}
}
return Difference;
}
int CcountDifference(vector <vector<char> > table, int row, int var) {
int Difference = 0;
for (int i = 0; i < row; i++) {
if (table[i][var] == '1') {
Difference -= 1;
}
else {
Difference += 1;
}
}
return Difference;
}
int main() {
//Initialise row and column
int r;
int c;
while (cin >> r >> c) {
//Initiallise 2D vector
vector <vector<char> > table(r, vector<char>(c));
//get each digit of number and store it into number
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> table[i][j];
}
}
//Build two arrays to store the value "zero-one"
vector <int> row;
vector <int> column;
//store for vector
//For Row
for (int i = 0; i < r; i++) {
row.push_back(RcountDifference(table, c, i));
}
//For Column
for (int j = 0; j < c; j++) {
column.push_back(CcountDifference(table, r, j));
}
Flip(r, c, table, row, column);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
//Flip for row
if (row[i]>0) {
(table[i][j] == '0') ? '1' : '0';
}
else if (row[i] == 0 && table[i][0]=='0') {
(table[i][j] == '0') ? '1' : '0';
}
else {
(table[i][j] == '0') ? '0' : '1';
}
row.clear();
row.push_back(RcountDifference(table, c, i));
column.clear();
column.push_back(CcountDifference(table, r, j));
//Flip for column
if (column[j] > 0) {
(table[i][j] == '0') ? '1' : '0';
}
else if (column[j] == 0 && table[0][j] == '0') {
(table[i][j] == '0') ? '1' : '0';
}
else {
(table[i][j] == '0') ? '0' : '1';
}
row.clear();
row.push_back(RcountDifference(table, c, i));
column.clear();
column.push_back(CcountDifference(table, r, j));
}
}
//Output Check
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << table[i][j];
}
}
}
return 0;
}
我的解决方案完成后，我也想把它放在这里，对于像我这样刚接触编码的人来说，学习不同的问题会很好。
抱歉，@Peter Cheng 的回答在某些测试用例中可能不正确。简单地用他的算法试试这个：
1 0 1 0
1 1 0 1
1 0 0 1
1 1 1 1
1 1 1 0
C[-5,-1,-1,-1]
R[0,-2,0,-4,-2]
根据他的算法，答案将是 14。但是，您可以翻转第三行，然后翻转第四列，得到 15 个正面。
我建议对这两种情况进行测试。如果您遇到零值，您应该根据该行或该列的第一枚硬币是否已经是正面来决定是否翻转。并且，如果遇到零值，则应根据该行或该列的第一枚硬币是否为正面来决定是否翻转，然后取较高的值作为最终答案。
问题来了。在游戏中，有一个长方形的硬币网格，正面 = 1，反面 = 0。游戏有一个简单的规则：玩家不能掷一枚硬币，相反，玩家可以选择一排（或一列）和同时翻转该行（或该列）中的所有硬币。游戏的objective就是找出抛硬币的策略，使正面硬币的数量最大。第一个输入值是行 >> 然后是列 >> 和硬币
Sample inputs:
5 4
1010
0101
1010
1010
1010 //Sample output of this: 20
5 4
0010
1101
0110
0110
1011 //Sample output of this: 17
我用计数'0'和'1'的方法完成了我的代码，如果零更多，切换它。这种方法只通过了简单的测试用例，但是当进入到困难的测试用例时，它失败了，因为有些情况需要推特不止一次。我想不出另一种更好的处理方式。
这是我的代码：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool ConeIsMore(vector <vector<char> > table, int size, int j) {
int countzero = 0;
int countone = 0;
for (int i = 0; i < size; i++) {
(table[i][j] == '0')?++countzero: ++countone;
}
if (countone >= countzero) {
return true;
}
return false;
}
bool RoneIsMore(vector <vector<char> > table, int size, int i) {
int countzero = 0;
int countone = 0;
for (int j = 0; j < size; j++) {
(table[i][j] == '0') ? ++countzero : ++countone;
}
if (countone >= countzero) {
return true;
}
return false;
}
int main() {
//Initialise row and column
int row;
int column;
while (cin >> row >> column) {
//Initiallise 2D vector
vector <vector<char> > table(row, vector<char>(column));
//get each digit of number and store it into number
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
cin >> table[i][j];
}
}
//check for column
for (int j = 0; j < column; j++) {
if (!ConeIsMore(table, row, j)) {
for (int i = 0; i < row; i++) {
(table[i][j] == '0') ? table[i][j] = '1' : table[i][j] = '0';
}
}
}
//check for row
for (int j = 0; j < row; j++) {
if (!RoneIsMore(table, column, j)) {
for (int i = 0; i < column; i++) {
(table[j][i] == '0') ? table[j][i] = '1' : table[j][i] = '0';
}
}
}
//Count One in the table
int ans = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
(table[i][j] == '1') ? (ans++) : (ans = ans);
}
}
cout << ans << endl;
}
return 0;
}
在研究测试用例的过程中，我发现有些需要检查各种时间，这让我觉得我的方法不是很好。谁能提出更好的处理方法？非常感谢。
以下是较难的测试用例：
5 4
0010
1101
0110
0110
1011 //17
5 4
0110
1111
0101
0110
0100 //16
5 4
0110
1001
0011
1110
1000 //16
5 4
1100
0001
1111
0101
1010 //16
5 4
0101
0110
1001
1000
0011 //16
5 4
0111
1100
0100
1000
1011 //16
5 4
1101
1110
0111
1011
0111 //15
5 4
1100
1001
0110
1001
1000 //17
您或许应该输出您的策略结果，而不仅仅是计算正面人数，以便更好地了解正在发生的事情。改进实施的两个想法：
1) 当行或列中的硬币数量为偶数时，您的代码没有执行您描述的算法。你说：
counting the '0' and '1', if zero is more, switch it.
您的代码：
if (!ConeIsMore(table, row, j)) {
// switch it
}
没有更多人头时切换。 结果，当硬币数量为偶数时，您也会切换 正面和反面的数量相等。当计数相等时切换是推测性的，目前尚不清楚它是否会有所改善，因此您或许应该特别对待它。
2) 你也许可以继续迭代直到没有 尾巴多于头的列或行。
从数据结构开始 std::vector<bool> table(row*column) 可能会更有效率，但也需要更加小心才能正确处理。
我们需要跟踪如果您翻转每一列或每一行，您的正面总数会增加多少。对于给定的行或列，如果您决定翻转该行或列，请计算反面的数量减去正面的数量以产生正面的净增加。将这些值存储在两个数组中，一个用于列，一个用于行。此时您应该有两个数组，一个大小行和一个大小列，具有负值、零值或正值。
5 4
1010
0101
1010
1010
1010 //Sample output of this: 20
row: [0, 0, 0, 0, 0]
column: [-3, 3, -3, 3]
现在遍历行向量和列向量，如果遇到正值，则需要翻转该行或列。如果遇到负值，不要翻转。 如果您遇到零值，您应该根据该行或该列的第一枚硬币是否已经是正面来决定翻转。这将有助于解决边缘情况，例如这个：
2 2
10
01 // output should be: 4
row: [0, 0] // How can we know to flip row 1 but not row 0? Because arr[0][0] = 1 already
column: [0, 0]
您必须采取的另一个步骤是，当您翻转一行时，您还必须更新列数组中的值，反之亦然。您还应该更新内存中的二维硬币数组以反映新状态。第一次翻转后，问题状态看起来像这样
5 4
1010
1010 // this row was flipped because arr[1][0] was 0
1010
1010
1010
row: [0, 0, 0, 0, 0]
column: [-5, 5, -5, 5]
继续，直到没有更多的行或列可以翻转。实现中有递归的好机会。
以下是我在Peter Cheng帮忙提供算法后的代码。它一直工作到计算行和列但不能翻转 table。
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int RcountDifference(vector <vector<char> > table, int col, int var) {
int Difference = 0;
for (int j = 0; j < col; j++) {
if (table[var][j]=='1') {
Difference -= 1;
}
else {
Difference += 1;
}
}
return Difference;
}
int CcountDifference(vector <vector<char> > table, int row, int var) {
int Difference = 0;
for (int i = 0; i < row; i++) {
if (table[i][var] == '1') {
Difference -= 1;
}
else {
Difference += 1;
}
}
return Difference;
}
int main() {
//Initialise row and column
int r;
int c;
while (cin >> r >> c) {
//Initiallise 2D vector
vector <vector<char> > table(r, vector<char>(c));
//get each digit of number and store it into number
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> table[i][j];
}
}
//Build two arrays to store the value "zero-one"
vector <int> row;
vector <int> column;
//store for vector
//For Row
for (int i = 0; i < r; i++) {
row.push_back(RcountDifference(table, c, i));
}
//For Column
for (int j = 0; j < c; j++) {
column.push_back(CcountDifference(table, r, j));
}
Flip(r, c, table, row, column);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
//Flip for row
if (row[i]>0) {
(table[i][j] == '0') ? '1' : '0';
}
else if (row[i] == 0 && table[i][0]=='0') {
(table[i][j] == '0') ? '1' : '0';
}
else {
(table[i][j] == '0') ? '0' : '1';
}
row.clear();
row.push_back(RcountDifference(table, c, i));
column.clear();
column.push_back(CcountDifference(table, r, j));
//Flip for column
if (column[j] > 0) {
(table[i][j] == '0') ? '1' : '0';
}
else if (column[j] == 0 && table[0][j] == '0') {
(table[i][j] == '0') ? '1' : '0';
}
else {
(table[i][j] == '0') ? '0' : '1';
}
row.clear();
row.push_back(RcountDifference(table, c, i));
column.clear();
column.push_back(CcountDifference(table, r, j));
}
}
//Output Check
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << table[i][j];
}
}
}
return 0;
}
我的解决方案完成后，我也想把它放在这里，对于像我这样刚接触编码的人来说，学习不同的问题会很好。
抱歉，@Peter Cheng 的回答在某些测试用例中可能不正确。简单地用他的算法试试这个：
1 0 1 0
1 1 0 1
1 0 0 1
1 1 1 1
1 1 1 0
C[-5,-1,-1,-1]
R[0,-2,0,-4,-2]
根据他的算法，答案将是 14。但是，您可以翻转第三行，然后翻转第四列，得到 15 个正面。
我建议对这两种情况进行测试。如果您遇到零值，您应该根据该行或该列的第一枚硬币是否已经是正面来决定是否翻转。并且，如果遇到零值，则应根据该行或该列的第一枚硬币是否为正面来决定是否翻转，然后取较高的值作为最终答案。