金币阵列问题.txt

有m￥n(m￡100,n￡100)个金币在桌面上排成一个m行n列的金币阵列。每一枚金 币或正面朝上或背面朝上。用数字表示金币状态

/*
  Name: 
  Copyright: 
  Author: 
  Date: 05-05-07 20:49
  Description: 
        ===========================================================

 算法实现题1-4 金币阵列问题

问题描述：

有m x n (m<=100, n<=100 ) 个金币在桌面上排成一个m行n 列的金币阵列。每一枚金
币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。
金币阵列游戏的规则是：
（1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选2 列，交换这2 列金币的位置。

编程任务：

给定金币阵列的初始状态和目标状态，编程计算按金币游戏规则，将金币阵列从初始状
态变换到目标状态所需的最少变换次数。

数据输入：

由文件input.txt给出输入数据。文件中有多组数据。文件的第1行有1 个正整数k，表
示有k 组数据。每组数据的第1 行有2 个正整数m 和n。以下的m行是金币阵列的初始状
态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。接着的m行是金币阵列的目标状态。

结果输出:

将计算出的最少变换次数按照输入数据的次序输出到文件output.txt。相应数据无解时
输出-1。
输入文件示例 输出文件示例
input.txt 
2
4 3
1 0 1
0 0 0
1 1 0
1 0 1
1 0 1
1 1 1
0 1 1
1 0 1
4 3
1 0 1
0 0 0
1 0 0
1 1 1
1 1 0
1 1 1
0 1 1
1 0 1

output.txt

2
-1
*/

/*
算法思路：整个就是递归递归再递归。先先判断初始状态bm和目标状态em各行的金币情况是否满足条件，即某行的同种朝向的金币数量是否相同，如果朝上的不同也没关系，只要bm朝下的与em朝上的金币数量相同也行（只要翻转该行就好了），但是如果两者都不满足，那就肯定不行。如果碰到列数为偶数，朝上的和朝下的相等的情况，
那就记录该行，待会递归求解的时候可以考虑翻转和不翻转两种情况。
如果各行的金币都满足条件，那就开始处理每一列了。因为每次可任意交换2列金币的位置，所以要递归分析各列交换与不交换的情况，寻求最佳解。在考虑各列交换与不交换之前，要先考虑各行翻转和不翻转。 
总而言之一句话，回溯，回溯寻求最佳解。 
表达能力有限，大家看代码，自己领会。 
*/
#include<iostream>
#include <time.h>
#include <math.h>

using namespace std;

void PrintMap(const int map[][100], int m, int n);
int YellowBoy(const int beginMap[][100], const int endMap[][100], int m, int n);//主函数 
int ForReverse(int map[][100], const int endMap[][100], const bool flag[], int m, int n, int t);
int Judge(int map[][100], const int endMap[][100], int m, int n, int t) ;
void Reverse(int map[][100], int row, int n);//翻转第row行 
int Count(const int map[][100], int row, int n, int flag);//累积第row行值为flag的元素的数量
bool EqualCel(const int map[][100], const int endMap[][100], int m, int cel);//判断第t列是否相同
void SwapCel(int map[][100], int m, int cel_1, int cel_2);//交换列t和列i 

int main(int argc, char* argv[])
{
    time_t startTime;
    time_t endTime;

    time(&startTime);

    int m = 4;
    int n = 4;
    int beginMap[100][100] = {{1,1,1,1},
                              {1,0,0,1},
                              {1,0,0,0},
                              {0,1,1,0}};
    int endMap[100][100]   = {{0,0,0,0},
                              {1,0,0,1},
                              {0,1,0,0},
                              {0,1,1,0}};;

    cout << endl << "begin:  " << endl;
    PrintMap(beginMap, m, n);
    cout << endl << "end:  " << endl;
    PrintMap(endMap, m, n);

    cout << endl << YellowBoy(beginMap, endMap, m, n) << endl;

    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl;
    system("pause");
    return 0;
}
//---------------------------------------------------------------------------

void PrintMap(const int map[][100], int m, int n)
{
    for (int i=0; i<m; ++i)
    {
        for (int j=0; j<n; ++j)
            cout << map[i][j] << "  ";
        cout << endl;
    }        
}

int YellowBoy(const int beginMap[][100], const int endMap[][100], int m, int n)//主函数 
{
    int map[100][100];//复制原始阵列 
    for (int i=0; i<m; ++i)
        for (int j=0; j<n; ++j)
            map[i][j] = beginMap[i][j];

    bool flag[100] = {0};//判断某行的金币阵翻转前后是否都满足条件，适用于偶数列的情况 
    int sum = 0;    
        
    for (int i=0; i<m; ++i)//先判断各行的金币情况是否满足条件，即某行的同种金币数量相同 
    {
        if (Count(beginMap,i,n,1) != Count(endMap,i,n,1))//如果第i行的背面朝上金币数不同 
        {
            if (Count(beginMap,i,n,0) == Count(endMap,i,n,1))//若bm朝下的与em朝上的金币数量相同  
            {
                Reverse(map, i, n);//翻转map的第i行 
                ++sum;//累计操作的次数 
            }
            else//否则无解 
                return -1;
        }
        else if (n%2 == 0 && Count(beginMap,i,n,0) == Count(endMap,i,n,1))//翻转前后都满足条件
            flag[i] = true;
    }

    int count = ForReverse(map, endMap, flag, m, n, 0);//递归执行或不执行翻转操作，寻求最佳解 
    if (count == -1)
        return -1;
    return sum + count;
}

int ForReverse(int map[][100], const int endMap[][100], const bool flag[], int m, int n, int t)
{
    int max = 100000;//记录操作次数的最小值，设初值为100000，实际操作次数肯定比它小 
    int num = 0;
    int sum = 0;
    if (t == m-1)//递归执行或不执行翻转操作，直到到最后一行 
    {
        num = Judge(map, endMap, m, n, 0);//先不翻转，直接递归寻求最佳解 
        if (num != -1 && num < max)
            max = num;

        if (flag[t])//若能翻转，翻转，并递归寻求最佳解  
        {
            Reverse(map, t, n);
            ++sum;
            num = Judge(map, endMap, m, n, 0);
            if (num != -1 && num < max)
                max = num;
        }
        //返回无解或最佳解 
        if (max == 100000)
            return -1;
        return sum + max;
    }
    else//如果还未到最后一行，分别翻转和不翻转该行，比较返回的解，寻求最佳解 
    {
        num = ForReverse(map, endMap, flag, m, n, t+1);//先不翻转，直接递归处理下一行 
        if (num != -1 && num < max)
            max = num;
        
        if (flag[t])//若能翻转，翻转，并递归处理下一行 
        {
            Reverse(map, t, n);
            num = ForReverse(map, endMap, flag, m, n, t+1);
            if (num != -1 && num < max)
            {
                max = num;
                ++sum;
            }
        }
        //返回无解或最佳解 
        if (max == 100000)
            return -1;

        return sum + max;
    }
}

//递归执行交换列或不交换操作，寻求最佳解 
int Judge(int map[][100], const int endMap[][100], int m, int n, int t) 
{
    int max = 100000;
    int num = 0;
    if (t == n-1)//分析到最后一列，看是否相同，相同则返回操作次数0，否则无解返回-1 
    {
        if (EqualCel(map, endMap, m, t))
            return 0;
        else
            return -1;
    }
    else//还没有分析到最后一列，将该列与所有在其之右的列（包括自己）都交换一次，递归寻求最佳解 
    {
        for (int i=t; i<n; ++i)
        {
            SwapCel(map, m, t, i);//交换列t和列i 
        
            if (EqualCel(map, endMap, m, t))//如果第t列相同，递归分析下一列 
            {
                num = Judge(map, endMap, m, n, t+1);
                if (num != -1 && num < max)
                    max = num;
            }
            
            SwapCel(map, m, t, i);//再换回来 
        }
        //返回无解或最佳解 
        if (max == 100000)
            return -1;
        if (EqualCel(map, endMap, m, t))//没有执行交换 
            return max;
        else
            return max + 1;
    }
}


void Reverse(int map[][100], int row, int n)//翻转第row行 
{
    for (int i=0; i<n; ++i)
        map[row][i] = !map[row][i];
}

int Count(const int map[][100], int row, int n, int flag)//累积第row行值为flag的元素的数量 
{
    int sum = 0;
    for (int i=0; i<n; ++i)
        if (flag == map[row][i])
            ++sum;
            
    return sum;
}

void SwapCel(int map[][100], int m, int cel_1, int cel_2)//交换列t和列i 
{
    int temp;
    
    for (int i=0; i<m; ++i)
    {
        temp = map[i][cel_1];
        map[i][cel_1] = map[i][cel_2];
        map[i][cel_2] = temp;
    }
}

bool EqualCel(const int map[][100], const int endMap[][100], int m, int cel)//判断第t列是否相同 
{
    for (int i=0; i<m; ++i)
    {
        if (map[i][cel] != endMap[i][cel])
            return false;
    }
    return true;
}