金币布列阵问题

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

有m*n(m<=100 , n<=100 )枚金币放在桌子上,成n*m阵列。用1表示金币的正面,0表示金币的反面。

规则:

(1):可以将任何一行的金币翻过来放在原来的位置上

(2):可以任选两列,交换这两列的位置

算法设计:给定金币阵列的初始状态和目标状态,按照规则进行计算,求出将金币从初始状态转到目标状态用的最少的翻转次数。如果不存在,输出-1。

输入样例:

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

输出样例:

2

-1

这道题目题意很明确,但不是很好想。这里有一个解法:先将初始状态下的数组每一列都与目标状态下的第一列进行比较,如果金币不一致,则翻转初始状态的金币阵列,这样做能保证初始阵列的第一列与目标阵列的第一列相等。接下来由于不能进行金币的翻转(因为一旦翻转,则第一列的金币就会出错)只能进行列交换。由于有很多列都要进行交换,如果贸然对输入的数组进行转换会造成初始状态的破坏,所有我们要用另一个数组进行状态的保存。代码如下:

 

#include <bits/stdc++.h>

using namespace std;
//金币布列阵问题
const int maxn = 100;
int mobTim = 0,row,col;
int arr1[maxn][maxn];
int arr2[maxn][maxn];
int tmp[maxn][maxn];
void trans(int i,int j)
{
    int t;
    for(int k=1; k<=row; k++)
    {
        t = tmp[k][i];
        tmp[k][i] = tmp[k][j];
        tmp[k][j] = t;
    }
    if(i!=j)
        mobTim++;
}
void change(int i)
{
    for(int j=1; j<=col; j++)
    {
        tmp[i][j] = 1-tmp[i][j];
    }
    mobTim++;
}
bool same(int i,int j) //
{
    bool f = true;
    for(int k=1; k<=row; k++)
    {
        if(arr2[k][i]!=tmp[k][j])
        {
            f = false;
            break;
        }
    }
    return f;
}
int main()
{
    int t,i,k,j,minn;
    cin>>t;
    while(t--)
    {
        minn = 0xffff;

        cin>>row>>col;
        for(i=1; i<=row; i++)
        {
            for(j=1; j<=col; j++)
            {
                cin>>arr1[i][j];
            }
        }
        for(i=1; i<=row; i++)
        {
            for(j=1; j<=col; j++)
            {
                cin>>arr2[i][j];
            }
        }
        for(k=1; k<=col; k++)
        {
            for(i=1; i<=row; i++)
            {
                for(j=1; j<=col; j++)
                {
                    tmp[i][j] = arr1[i][j];
                }
            }
            mobTim=0;    //注意这里,在每一次进行状态变化之前和每一列进行判断之后,翻转次数要转//为0
            trans(1,k); //进行列之间的转换
            //开始进行tmp的第一列与arr2的第一列的比较
            for(i=1; i<=row; i++)
            {
                if(tmp[i][1] != arr2[i][1])
                {
                    change(i);
                }
            }
            int found;
            for(i=2; i<=col; i++)
            {
                found = 0;
                for(j=i; j<=col; j++)
                {
                    if(same(i,j))
                    {
                        found = 1;
                        trans(i,j);
                        break;
                    }
                }
                if(!found)
                    break;
            }
            if(found && minn > mobTim)
                minn = mobTim;
        }
        if(minn!=0xffff)
            cout<<minn<<endl;
        else
            cout<<-1<<endl;
    }
    return 0;
}

 

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《金币布列阵问题》 发布于2018-09-26

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录