《反转棋盘》解答
反转棋盘一个N*M大小的棋盘,每个格子都是0或者1,N和M都是奇数。你每次可以选择反转一行或者一列,被反转的行或列的所有0变成1,所有1变成0。要求使用最少的反转次数,使得每行每列的1的个数是偶数。输入格式:从键盘输入,第一行是两个正整数N和M,用空格隔开,都不超过20,都是奇数。接下来有N行,每行M个数,都为0或者1,表示棋盘上的数,数字用空格分隔。输出格式:只有一个数字,表示
[
输入样例A]
3 3
1 1 1
0 1 1
0 0 1
[
输出样例A]
2
|
[
输入样例B]
5 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
[
输出样例B]
3
|
#include <iostream>
using namespace std;
int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
int N, M;
cin >> N >> M; // 读入N行和M列
int Board[20][20]; // 存储棋盘初始情况
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> Board[i][j];
int Ro = 0; // 有奇数个1的行的数目
for (int i = 0; i < N; i++)
{
int temp = 0; // 用于统计每行的1的个数
for (int j = 0; j < M; j++)
temp += Board[i][j];
Ro += temp % 2; // 如果是奇数则加1
}
int Co = 0; // 有奇数个1的列的数目
for (int j = 0; j < M; j++)
{
int temp = 0; // 用于统计每列的1的个数
for (int i = 0; i < N; i++)
temp += Board[i][j];
Co += temp % 2; // 如果是奇数则加1
}
if (Ro % 2 == 0) // 是偶数
cout << min(Ro + Co, N - Ro + M - Co) << endl;
else
cout << min(Ro + M - Co, N - Ro + Co) << endl;
return 0;
}
更多推荐
所有评论(0)