首页 > ACM题库 > HDU-杭电 > HDU 3484-Matrix Game-枚举-[解题报告]HOJ
2014
04-04

HDU 3484-Matrix Game-枚举-[解题报告]HOJ

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3484

题目大意:现在给出两个0/1矩阵,对于矩阵可以执行两种操作,交换行和将一列的数都取非,问能不能通过一系列的操作把一个矩阵变为另外一个矩阵。

解题思路:对于两个矩阵,分别几位A和B,我们考虑先将一种操作执行完,对于取非操作,多次是没有意义的,我们考虑A矩阵的第几行是对于B矩阵的第一行(枚举),将其交换到第一行,在通过取非操作时两个矩阵的第一行相同,之后就不能在执行取非操作,我们就不断判断没行是否相同并进行交换,最终能否是两个矩阵相同。

通过代码:

#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;
}

参考:http://blog.csdn.net/ruptins/article/details/21418651


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

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  5. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?