【蓝桥杯】翻硬币及其引申题

目录

【蓝桥杯】翻硬币

【翻硬币引申题】费解的开关

【翻硬币引申题】 飞行员兄弟

---

【蓝桥杯】翻硬币

---

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。

我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步 *** 作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小 *** 作步数

数据范围

输入字符串的长度均不超过100。

数据保证答案一定有解。

输入样例1：

**********
o****o****

输出样例1：

5

输入样例2：

*o**o***o***
*o***o**o***

输出样例2：

1

思路：

        乍一看毫无头绪，实现之后发现并不是很难！

        一个位置 *** 作两次是毫无意义的，所以每一个位置的 *** 作次数只有0次和1次的可能，下面就是确定每一个位置究竟是翻转还是不 *** 作。

        我们可以从头开始比较初始字符串和目标字符串，如果二者不同，则说明这个位置需要 *** 作一次，那么我们就 *** 作它，然后计数器自增一次，一直比较到n-1的位置(因为有n个硬币说明有n-1个空位，仔细想一下）。

        遍历完这一次之后 计数器cnt即为我们所求的答案！

时间复杂度分析：

        只需要遍历一遍，设字符串长度为n，则时间复杂度为O(n)

思路实现：

1.翻转 *** 作

void turn(int x)
{
    if(coin_init[x] == 'o')
        coin_init[x] = '*';
    else
        coin_init[x] = 'o';
}

完整代码（C++）：

#include
#include
#include
#include

using namespace std;

const int N = 110;
char coin_init[N],coin_t[N];//初始串和目标串

void turn(int x)
{
    if(coin_init[x] == 'o')
        coin_init[x] = '*';
    else
        coin_init[x] = 'o';
}

int main()
{
    cin >> coin_init >> coin_t;
    int cnt = 0;
    int len = strlen(coin_t);
    
    for(int i = 0; i < len - 1; i++)
    {
        if(coin_init[i] != coin_t[i])
        {
            turn(i), turn(i + 1);
            cnt++;
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

【翻硬币引申题】费解的开关

---

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

数据范围

0

输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

3
2
-1

思路：

        与上一题相似，只不过换成了二维，首先还是要想明白：一个地方 *** 作两次是无意义的，所以每一个位置只有 *** 作0次或1次的可能，接下来思考每个地方该如何 *** 作。

        我们可以一行一行的考虑，第一行灯的状态可以由 *** 作第一行和 *** 作第二行改变（比较特殊），假设第一行的灯已经由第一行和第二行的 *** 作变为全亮了，那么第二行的状态只能由第三行的 *** 作决定，因为如果 *** 作第二行或者第一行，那么之前已经 *** 作好的灯的状态就没有了，同理第三行由第四行决定，第四行由第五行决定。

第五行下面没有灯了，所以如果此时灯全亮了，说明这个方案是可行的，如果第五行有灯没有亮，说明这个方案不可行。

        第一行灯的状态可以由 *** 作第一行和 *** 作第二行改变——可以枚举第一行的 *** 作总数，先 *** 作第一行，然后在第二行根据第一行的灯的亮灭进行第二行的 *** 作，三四五行根据上一行灯的亮灭进行 *** 作。

思路实现：

1.题目中灯状态的转换

int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0}; //使用偏移量和for循环转换状态

void turn_one(int x, int y)
{
    if(g[x][y] == '0') g[x][y] = '1';
    else g[x][y] = '0';
}

void turn_all(int x, int y)
{
    for(int i = 0; i < 5; i++)
    {
        int rx = dx[i] + x, ry = dy[i] + y;
        if(rx < 0 || rx >= 5 || ry < 0 || ry >= 5) //越界不处理
            continue;
        turn_one(rx, ry);
    }
}

2.对第一行状态的枚举

/*
每一行有五个灯  *** 作可以由二进制数表示 0 表示不 *** 作 1 表示 *** 作
那么需要五位二进制数表示 00000 ~ 11111 转换为十进制的范围就是 0 ~ 2^5-1
取每一位的 *** 作使用位运算：
第一位右移 0 位 然后 与 1
第二位右移 1 位 然后 与 1
第二位右移 2 位 然后 与 1
...
如果取到的数位为 1 则 *** 作这一位 step 自增
*/

for(int op = (1 << 5) - 1; op >= 0; op--)
{
    for(int i = 0; i < 5; i++)
    if(op >> i & 1)
    {
        step++;
        turn_all(0, i);
    }
}

3. 上一行如果有灭的灯，则 *** 作下一行的同一位置

//第一行已经 *** 作完了 从第二行到第五行遍历
for(int i = 1; i < 5; i++) 
    for(int j = 0; j < 5; j++)
    {
        if(g[i - 1][j] == '0') //如果上一行有灭的灯 就操作这一行的同一位置 step 自增
        {
            turn_all(i, j);
            step++;
        }
    }
}

4.遍历整个数组 检查方案是否可行

    bool is_dark = false;
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            if(g[i][j] == '0')
            is_dark = true;
            
    if(!is_dark)
    {
        res = min(res, step);
    }

完整代码（C++）：

#include
#include
#include
#include

using namespace std;

const int N = 5 + 10;
char g[N][N], backup[N][N];
int step;
int res = 7;
int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0}; //偏移量

void turn_one(int x, int y)
{
    if(g[x][y] == '0') g[x][y] = '1';
    else g[x][y] = '0';
}

void turn_all(int x, int y)
{
    for(int i = 0; i < 5; i++)
    {
        int rx = dx[i] + x, ry = dy[i] + y;
        if(rx < 0 || rx >= 5 || ry < 0 || ry >= 5)
            continue;
        turn_one(rx, ry);
    }
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        res = 7; //因为题目中要寻找小于等于6步的情况，所以res只要大于6就不会影响答案
        for(int i = 0; i < 5; i++)
            cin >> g[i];
        memcpy(backup, g, sizeof g); //备份 用于每次枚举完一次之后的复原
        for(int op = (1 << 5) - 1; op >= 0; op--)
        {
            
            step = 0;
            for(int i = 0; i < 5; i++)
                if(op >> i & 1)
                {
                    step++;
                    turn_all(0, i);
                }
            
            for(int i = 1; i < 5; i++)
                for(int j = 0; j < 5; j++)
                {
                    if(g[i - 1][j] == '0')
                    {
                        turn_all(i, j);
                        step++;
                    }
                }
            
            bool is_dark = false;
            
            for(int i = 0; i < 5; i++)
                for(int j = 0; j < 5; j++)
                    if(g[i][j] == '0')
                        is_dark = true;
            
            if(!is_dark)
            {
                res = min(res, step);
                //cout << step << endl;
            }
                
            
            memcpy(g, backup, sizeof g); //复原
        }
        if(res > 6) res = -1;
        cout << res << endl;
    }
    
    return 0;
}

【翻硬币引申题】 飞行员兄弟

---

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j]上把手的状态。

但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 N，表示所需的最小切换把手次数。

接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤41≤i,j≤4

输入样例：

-+--
----
----
-+--

输出样例：

6
1 1
1 3
1 4
4 1
4 3
4 4

思路：

跟前面两个一样， 4x4 的矩阵数据比较小，直接枚举即可： 枚举每一个开关是否 *** 作，依然使用二进制数和位移 *** 作判断是否 *** 作，最后检查方案是否正确。

思路实现：

1.状态的翻转

void turn_one(int x, int y)
{
    if(g[x][y] == '-') g[x][y] = '+';
    else g[x][y] = '-';
}

void turn_all(int x, int y)
{
    for(int i = 0; i < 4; i++)
    {
        turn_one(i, y);
        turn_one(x, i);
    }
    turn_one(x, y); //因为翻转的两次， 所以需要再翻转一次
}

2.枚举所有可能

//得到每个坐标所对应的映射值
int get(int x, int y)
{
    return x * 4 + y;
}


for(int op = 0; op < 1 << 16; op++)
{
    vector> temp; //因为最后需要输出 *** 作了哪些开关，所以用容器存下来
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
        {
            if(op >> get(i, j) & 1)
            {
                turn_all(i, j);
                temp.push_back({i, j});
            }
        }
}

3.检查

bool is_lock = false;
for(int i = 0; i < 4; i++)
     for(int j = 0; j < 4; j++)
          if(g[i][j] == '+')
              is_lock = true;
        
if(!is_lock)
{
    if(res.empty() || temp.size() < res.size()) //如果第一次存答案，或者找到的答案比上一次小
        res = temp;
}

完整代码（C++）：

#include
#include
#include
#include
#include

using namespace std;

const int N = 4 + 10;
char g[N][N], backup[N][N];
vector> res;

int get(int x, int y)
{
    return x * 4 + y;
}

void turn_one(int x, int y)
{
    if(g[x][y] == '-') g[x][y] = '+';
    else g[x][y] = '-';
}

void turn_all(int x, int y)
{
    for(int i = 0; i < 4; i++)
    {
        turn_one(i, y);
        turn_one(x, i);
    }
    turn_one(x, y);
}

int main()
{
    for(int i = 0; i < 4; i++)
        cin >> g[i];
    
    memcpy(backup, g, sizeof g);
    
    for(int op = 0; op < 1 << 16; op++)
    {
        vector> temp;
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
            {
                if(op >> get(i, j) & 1)
                {
                    turn_all(i, j);
                    temp.push_back({i, j});
                }
            }
        
        bool is_lock = false;
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                if(g[i][j] == '+')
                    is_lock = true;
        
        if(!is_lock)
        {
            if(res.empty() || temp.size() < res.size())
                res = temp;
        }
        memcpy(g, backup, sizeof g);
    }
    
    cout << res.size() << endl;
    for(auto op : res)
    {
        cout << op.first + 1 << ' ' << op.second + 1 << endl;
    }
    
    return 0;
}