2014
04-04

# Matrix Game

At the start of the matrix game, we have an n * m chessboard in which each grid is painted alternatively in white or black. Every time, we can apply one of the two following operations:
Row flip operation: we can change the color of every grid in a single row.
Column swap operation: we can swap two columns (i.e., switch the colors between corresponding grids).
The task of the problem is, determine whether it’s possible to reach the target from the original chessboard by applying the two operations several times. Print ‘Yes’ or ‘No’ for each case.

There are several test cases. For each case, there are two integers n and m in the first line (1 ≤ n, m ≤ 100), followed by two n * m 0/1 matrixes (0 stands for white color and 1 stands for black color) which are the original chessboard and the target chessboard respectively.
The input ends up with two negative numbers, which should not be processed as a case.

There are several test cases. For each case, there are two integers n and m in the first line (1 ≤ n, m ≤ 100), followed by two n * m 0/1 matrixes (0 stands for white color and 1 stands for black color) which are the original chessboard and the target chessboard respectively.
The input ends up with two negative numbers, which should not be processed as a case.

2 2
1 1
1 0
0 0
0 1
2 2
1 1
1 0
0 0
0 0
-1 -1

Yes
No

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

#define N 110
using namespace std;
int n,m;
int map[N][N];
int a[N][N];
int b[N][N];

bool solve(){
for (int i=2;i<=m;i++){
int flag=0;
for (int j=1;j<=n;j++)
if (a[j][i]!=b[j][i]) {flag=1;break;}
if (!flag) continue;
int exc=0;
for (int j=i+1;j<=m;j++){
flag=0;
for (int t=1;t<=n;t++)
if (a[t][j]!=b[t][i]) {flag=1;break;}
if (flag) continue;
exc=1;
for (int t=1;t<=n;t++)
swap(a[t][j],a[t][i]);
break;
}
if (!exc) return false;
}
return true;
}

int main(){
while (scanf("%d%d",&n,&m)==2){
if (n<0&&m<0) break;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
int flag=0;
for (int i=1;i<=m;i++){

for (int j=1;j<=n;j++)
for (int t=1;t<=m;t++)
a[j][t]=map[j][t];

for (int j=1;j<=n;j++)
swap(a[j][1],a[j][i]);

for (int j=1;j<=n;j++){
if (a[j][1]!=b[j][1]){
for (int t=1;t<=m;t++)
a[j][t]=1-a[j][t];
}
}

if (solve()) {flag=1;break;}
}
if (flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}


1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

5. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;