金币阵列问题

金币阵列问题

时间: 1ms        内存:64M

描述:

有m× n(m≤100,n≤100)个金币在桌面上排成一个m行n 列的金币阵列。每一枚金币或正面朝上或背面朝上。用数字表示金币状态,0表示金币正面朝上,1 表示背面朝上。金币阵列游戏的规则是:(1)每次可将任一行金币翻过来放在原来的位置上;(2)每次可任选2 列,交换这2 列金币的位置。给定金币阵列的初始状态和目标状态,计算按金币游戏规则,将金币阵列从初始状态变换到目标状态所需的最少变换次数。

输入:

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

输出:

将计算出的最少变换次数按照输入数据的次序输出。相应数据无解时输出 -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

提示:

参考答案(内存最优[1388]):

#include <fstream>
#include <iostream>
using namespace std;
const int size = 100;
int k,n,m,ccount,best;
int b0[size+1][size+1],b1[size+1][size+1],b[size+1][size+1];
bool found;
void print()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << b1[i][j] << " ";
        cout << endl;
    }
}

void trans1(int x)
{
    for(int i = 1; i <= m; i++)
        b1[x][i] = b1[x][i]^1;
    ccount++;
}
void trans2(int x, int y)
{
    for(int i = 1; i <= n; i++)
        swap(b1[i][x],b1[i][y]);
    if (x != y) ccount++;  
}
bool same(int x, int y)
{
    for(int i = 1; i <= n; i++)
        if (b0[i][x] != b1[i][y])
            return false;
    return true;
}
void acpy(int a[size+1][size+1], int b[size+1][size+1])
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            a[i][j] = b[i][j];
}
void answer()
{
 int x,y,j,p;
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        cin >> n >> m;
        for( x = 1; x <= n; x++)
            for( y = 1; y <= m; y++)
                cin >> b0[x][y];
        for( x = 1; x <= n; x++)
            for(int y = 1; y <= m; y++)
                cin >> b1[x][y];
        acpy(b,b1);
        best = m + n + 1;
        for( j = 1; j <= m; j++)
        {
            acpy(b1,b);
            ccount = 0;
            trans2(1,j);
            int p;
            for( p = 1; p <= n; p++)
                if (b0[p][1] != b1[p][1])
                    trans1(p);
            for(p = 1; p <= m; p++)
            {
                found = false;
                for(int q = p; q <= m; q++)
                    if (same(p,q))
                    {
                        trans2(p,q);
                        found = true;
                        break;
                    }
                if (!found) break;
            }

            if (found && ccount < best)
                best = ccount;
        }
        if (best < m + n + 1)
            cout << best << endl;
        else
            cout << -1 << endl;
    }
}
int main()
{
    answer();
    return 0;
}

参考答案(时间最优[56]):

#include <fstream>
#include <iostream>
using namespace std;
const int size = 100;
int k,n,m,ccount,best;
int b0[size+1][size+1],b1[size+1][size+1],b[size+1][size+1];
bool found;
void print()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << b1[i][j] << " ";
        cout << endl;
    }
}

void trans1(int x)
{
    for(int i = 1; i <= m; i++)
        b1[x][i] = b1[x][i]^1;
    ccount++;
}
void trans2(int x, int y)
{
    for(int i = 1; i <= n; i++)
        swap(b1[i][x],b1[i][y]);
    if (x != y) ccount++;  
}
bool same(int x, int y)
{
    for(int i = 1; i <= n; i++)
        if (b0[i][x] != b1[i][y])
            return false;
    return true;
}
void acpy(int a[size+1][size+1], int b[size+1][size+1])
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            a[i][j] = b[i][j];
}
void answer()
{
 int x,y,j,p;
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        cin >> n >> m;
        for( x = 1; x <= n; x++)
            for( y = 1; y <= m; y++)
                cin >> b0[x][y];
        for( x = 1; x <= n; x++)
            for(int y = 1; y <= m; y++)
                cin >> b1[x][y];
        acpy(b,b1);
        best = m + n + 1;
        for( j = 1; j <= m; j++)
        {
            acpy(b1,b);
            ccount = 0;
            trans2(1,j);
            int p;
            for( p = 1; p <= n; p++)
                if (b0[p][1] != b1[p][1])
                    trans1(p);
            for(p = 1; p <= m; p++)
            {
                found = false;
                for(int q = p; q <= m; q++)
                    if (same(p,q))
                    {
                        trans2(p,q);
                        found = true;
                        break;
                    }
                if (!found) break;
            }

            if (found && ccount < best)
                best = ccount;
        }
        if (best < m + n + 1)
            cout << best << endl;
        else
            cout << -1 << endl;
    }
}
int main()
{
    answer();
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注