《算法竞赛·快冲300题》每日一题:“点灯游戏”

这篇具有很好参考价值的文章主要介绍了《算法竞赛·快冲300题》每日一题:“点灯游戏”。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。


点灯游戏” ,链接: http://oj.ecustacm.cn/problem.php?id=1134

题目描述

【题目描述】 有一个n*n的灯泡矩阵,b表示灯暗,w表示灯亮。每个灯的位置上都有控制着这盏灯的按钮。当按下一个按钮后,该按钮以及周围位置(上下左右)的灯都会改变状态(亮->暗,暗->亮)。最少按下多少个按钮可以使得所有的灯都亮或者都暗。
【输入格式】 输入有多组数据,每组数据第一行有一个整数n(1≤n≤10),接下来n行,每行n个字符表示初始的灯泡矩阵。
【输出格式】 如果可以使得所有的灯泡都亮或者都暗,输出最少按下的按钮数目。如果无法达到,输出"Impossible"(不含引号) 。
【输入样例】

4
bwwb
bbwb
bwwb
bwww
4
bwbw
wwww
bbwb
bwwb

【输出样例】

4
Impossible

题解

   “点灯游戏”是一个经典问题,有多种解法。
  如果没有限制“最少按钮数”,只要求能实现全暗或全灭,如何操作?这里介绍一种被称为“首行穷举法”的方法,简单易行。设目标是把所有的灯变黑(暗),操作如下:
  (1)第一行不按动按钮,只需找到白灯的位置;
  (2)第二行对应第一行的白灯的位置,都是按钮,按下后,它上下左右的灯都变色,特别是上一行的白灯都会变黑,从而保证第一行都变成黑色;
  (3)每一行的按钮,都对应上一行的白灯,使上一行全变黑。
  本题要求得“最少按钮数”,可以把所有按钮都试一遍,找到最少的那种。为了减少尝试的次数,可以结合上述方法。本题的n≤10,规模很小,这种暴力法也可行。
  假设目标是最后都变成黑色,从第一行开始,逐行按动按钮。
  第一行有0000~1111共16种按按钮的方法。0000表示1个都不按,0001表示只按第1个按钮,0010表示只按第2个按钮,0011表示按第1、第2个按钮,…,等等。
  第一行选择一种方法按完之后,继续按动第二行。第二行如何按?显然要保证第一行都变成黑色才行。那么应该让第二行的按钮位置跟第一行的白色位置一样,因为第二行的按钮按动之后,它上面的白色会跟着变成黑色。
  按上述规则继续按后面的行,直到结束。
  下面举例说明。图中的“初态”是第一个样例的灯,黑表示暗,白表示亮。左上角坐标(0,0),右下角坐标(3,3)。
《算法竞赛·快冲300题》每日一题:“点灯游戏”,算法竞赛快冲300题,算法,游戏
  (1)第一行的按钮设置。以第一行按0011为例,就是按第1、2个按钮。按第1个按钮(0,0)后得到图(1),再按第2个按钮(0,1)后得到图(2)。记录两个按钮的坐标(0,0)、(0,1)。
  (2)第二行的按钮设置。此时第一行只有第2个灯是白的,需要变成黑色。那么第二行必须按第2个按钮,才能让上面的白灯变成黑灯。第二行需要按的按钮的坐标是(1,1),得到图(3)的结果,第一行全黑了。
  (3)第三行的按钮设置。由于第二行全是黑的,所以第三行不用按了。
  (4)第四行的按钮设置。第三行的第3个灯是白的,需要变成黑色。那么第四行必须按第3个按钮,才能让上面的白灯变成黑灯。得到图(4)的结果,第三行全黑了。第四行需要按的按钮坐标是(3,2)。
  这四行结束后,第四行也变成了全黑,说明这是一次成功的操作,共按了4个按钮。
  第一行共有16种按钮设置方法,都按以上步骤操作一遍,其中按动按钮最少的就是结果全是黑灯的答案。
  以上假设最后都是黑色,也可以假设最后都是白色,再操作一次即可。取最少的按钮次数就是本题的答案。
  请读者按这个思路编码。下面的代码供参考。
【重点】 思维 。

C++代码

#include<bits/stdc++.h>
using namespace std;
char Map[11][11];
int n;
int GetBit(int x, int i){             //取出x的第i位
    return (x >> i) & 1;
}
void SetBit(int &x, int i, int v){        //将x的第i位设置成v
    if(v)  x |= (1 << i);
    else   x &= ~(1 << i);
}
void FlipBit(int &x, int i){         //将x的第i位取反
    x ^= (1 << i);
}
int solve(){
    int oriLights[11];    //灯的初态
    int Lights[11];       //按动按钮之后的灯的新状态
    int result[11];       //存需要按动的按钮
    int ans = n * n + 1;  //需要按动的按钮数不会大于n*n
    memset(oriLights, 0, sizeof(oriLights));
    for(int i = 0; i < n; i++)           //把灯用二进制的位来表示,第i行,第j列
        for(int j = 0; j < n; j++){
            if(Map[i][j] == 'b')  SetBit(oriLights[i], j, 0);   //0表示暗
            else                  SetBit(oriLights[i], j, 1);   //1表示亮
        }
    for(int k = 0; k < (1<<n); k++)  {        //k是第0行的按钮,有0000~1111种按钮设置
        memcpy(Lights, oriLights, sizeof(oriLights)); 
        int switchs = k;                      //第0行的按钮,例如k=0011,就是按第1、2个按钮
        for(int i = 0; i < n; i++) {          //逐一处理每行的灯
            result[i] = switchs;              //用result[i]记录第i行的按钮
            for(int j = 0; j < n; j++) {      //逐一处理每一列的灯
                if(GetBit(switchs, j)) {   
                    if(j > 0)    FlipBit(Lights[i], j-1);  //j前面的第j-1灯变色
                    FlipBit(Lights[i], j);                     //第j个灯变色
                    if(j < n-1)  FlipBit(Lights[i], j+1);  //j后面的第j+1灯变色
                }
            }
            if(i < n-1)   Lights[i+1] ^= switchs;      //修改下一行的灯
            switchs = Lights[i];            //第i+1行按钮位置和第i行灯的位置相同
        }
        if(Lights[n-1] == 0) {            //最后一行也全变黑了,成功
            int tmp = 0;                    //tmp为开关矩阵中1的数目
            for(int i = 0; i < n; i++)      //(i,j)就是需要按动的按钮坐标
                for(int j = 0; j < n; j++)
                    if(result[i] & (1<<j))
                        tmp++;
            ans = min(ans, tmp);
        }
    }
    return ans;
}
int main(){
    while(scanf("%d", &n) != EOF)  {
        memset(Map, 0, sizeof(Map));
        for(int i = 0; i < n; i++)  scanf("%s", Map[i]);
        int ans = solve();                  //以全黑为目标做一次
        for(int i = 0; i < n; i++)          //反过来以全白为目标做一次
            for(int j = 0; j < n; j++)
                if(Map[i][j] == 'b')  Map[i][j] = 'w';
                else                  Map[i][j] = 'b';
        ans = min(ans, solve());
        if(ans > n * n)  puts("Impossible");
        else             printf("%d\n", ans);
    }
    return 0;
}

Java代码

import java.util.*;  
public class Main {  
    static int GetBit(int x, int i) {
        return (x >> i) & 1;
    }  
    static int SetBit(int x, int i, int v) {
        if (v == 1)   x |= (1 << i);
        else             x &= ~(1 << i);
        return x;
    }  
    static int FlipBit(int x, int i) {
        x ^= (1 << i);
        return x;
    }  
    static int solve(int n, String[] Map) {
        int[] oriLights = new int[n];
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) {
                if (Map[i].charAt(j) == 'b')  oriLights[i] &= ~(1 << j);
                else        oriLights[i] |= (1 << j);
            }
        int ans = n * n + 1;
        for (int k = 0; k < (1 << n); k++) {
            int switchs = k;
            int[] Lights = oriLights.clone();
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = switchs;
                for (int j = 0; j < n; j++) {
                    if (GetBit(switchs, j) == 1) {
                        if (j > 0)   Lights[i] = FlipBit(Lights[i], j-1);
                        Lights[i] = FlipBit(Lights[i], j);
                        if (j < n-1) Lights[i] = FlipBit(Lights[i], j+1);
                    }
                }
                if (i < n-1)      Lights[i+1] ^= switchs;
                switchs = Lights[i];
            }
            if (Lights[n-1] == 0) {
                int tmp = 0;
                for (int i = 0; i < n; i++) 
                    for (int j = 0; j < n; j++) 
                        if ((result[i] & (1 << j)) != 0) 
                            tmp++;
                ans = Math.min(ans, tmp);
            }
        }
        if (ans > n * n)     return -1;
        else             return ans;

    }
  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n == 0)  break; 
            String[] Map = new String[n];
            for (int i = 0; i < n; i++)  Map[i] = scanner.next();
             int ans = solve(n, Map);
            // 循环遍历数组并替换字符
            for (int i = 0; i < n; i++) {
                Map[i] = Map[i].replace('b', 'x');  // 将'b'替换为临时字符'x'
                Map[i] = Map[i].replace('w', 'b');  // 将'w'替换为'b'
                Map[i] = Map[i].replace('x', 'w');  // 将临时字符'x'替换为'w'
            }
            ans = Math.min(ans, solve(n, Map));
            if (ans == -1)   System.out.println("Impossible");
            else             System.out.println(ans);
        }
        scanner.close();
    }
}

Python代码

  文章来源地址https://www.toymoban.com/news/detail-712664.html

 import sys
def GetBit(x, i):   return (x >> i) & 1
 
def SetBit(x, i, v):
    if v:     x |= (1 << i)
    else:     x &= ~(1 << i)
    return x
 
def FlipBit(x, i):
    x ^= (1 << i)
    return x
 
def solve(n, Map):
    oriLights = [0] * n
    for i in range(n):
        for j in range(n):
            if Map[i][j] == 'b':  oriLights[i]=SetBit(oriLights[i], j, 0) 
            else:                 oriLights[i]=SetBit(oriLights[i], j, 1) 
    ans = n * n + 1
    for k in range(1 << n):
        switchs = k
        Lights = oriLights[:]
        result = [0] * n
        for i in range(n):
            result[i] = switchs
            for j in range(n):
                if GetBit(switchs, j):
                    if j > 0:   Lights[i] = FlipBit(Lights[i], j-1)
                    Lights[i] = FlipBit(Lights[i], j)
                    if j < n-1: Lights[i] = FlipBit(Lights[i], j+1)
            if i < n-1:   Lights[i+1] ^= switchs
            switchs = Lights[i]
        if Lights[-1] == 0:
            tmp = 0
            for i in range(n):
                for j in range(n):
                    if result[i] & (1 << j):
                        tmp += 1
            ans = min(ans, tmp)
    return ans
 
for line in sys.stdin:
    n = int(line.strip())
    if n == 0:  break
    Map = []
    for i in range(n):   Map.append(input().strip())
    ans = solve(n, Map)
    F = {}
    F['b'] = 'w'
    F['w'] = 'b'
    for i in range(n):
        Map[i] = ''.join([F[x] for x in Map[i]])
         
    ans = min(ans,solve(n, Map))
    if ans > n * n:     print("Impossible")
    else:               print(ans)

到了这里,关于《算法竞赛·快冲300题》每日一题:“点灯游戏”的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《算法竞赛·快冲300题》每日一题:“松鼠与栗子”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 松鼠与栗子 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1852 【题目描述】 现在有m棵栗

    2024年02月11日
    浏览(43)
  • 罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1812 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定一个长度为 n 的排列 a,需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出 最小需要移动的元素个数 。 【输入格式】 第一行为正整数 n,1≤n≤100000。

    2024年02月12日
    浏览(40)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“乘积” ← 动态规划

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1781 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给你一个长度为 n 的序列,序列中的元素只包括 1 和 -1。 请问有多少个连续的子序列乘积为正数。 【输入格式】 输入第一行为正整数 n。(n不超过10^6) 第二行包含 n 个整数。 【输

    2024年02月11日
    浏览(51)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“小球配对” ← 并查集

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1850 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定 n 个小球,编号为 1-n ,给定 m 个篮子,编号为 1-m 。 每个球只允许放入样例给定的编号为 Ai 或者 Bi 的两个篮子中的 1 个。 每个球必须放入某个篮子。 如果篮子中球的数量为奇

    2024年02月11日
    浏览(40)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“游泳” ← DFS+剪枝

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1753 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 游泳池可以等分为n行n列的小区域,每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n),小明只能向上下左右四个方向游,不能游出泳池。 而小明对温度十分

    2024年02月10日
    浏览(37)
  • 每日一题(822. 翻转卡片游戏)-集合set

    822. 翻转卡片游戏 简述为:找到桌面卡片中 不重复的最小值,卡片可以来回反转 如果 卡片前面后面的数字相同 则抛弃不用 在剩下的卡片中 找到最小值(前后可以反转 == 卡片不分前后)

    2024年02月14日
    浏览(66)
  • LeetCode每日一题——2682. 找出转圈游戏输家

    n  个朋友在玩游戏。这些朋友坐成一个圈,按  顺时针方向  从  1  到  n  编号。从第  i  个朋友的位置开始顺时针移动  1  步会到达第  (i + 1)  个朋友的位置( 1 = i n ),而从第  n  个朋友的位置开始顺时针移动  1  步会回到第  1  个朋友的位置。 游戏规则如下:

    2024年02月12日
    浏览(40)
  • 【C语言每日一题】10. 超级玛丽游戏

    题目来源:http://noi.openjudge.cn/ch0101/10/ 总时间限制: 1000ms 内存限制: 65536kB 超级玛丽是一个非常经典的游戏。请你用字符画的形式输出超级玛丽中的一个场景。 无。 如样例所示。

    2024年02月10日
    浏览(37)
  • LeetCode·每日一题·822. 翻转卡片游戏·哈希

    作者:小迅 链接:https://leetcode.cn/problems/card-flipping-game/solutions/2368969/ha-xi-zhu-shi-chao-ji-xiang-xi-by-xun-ge-7ivj/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 根据题意,只要有数字满足 fronts[i]=backs[i],那么 fronts[i] 绝对不可能是

    2024年02月14日
    浏览(36)
  • SQL-每日一题【550.游戏玩法分析Ⅳ】

    Table:  Activity 编写一个 SQL 查询,报告在首次登录的第二天再次登录的玩家的比率,四舍五入到小数点后两位。换句话说,您需要计算从首次登录日期开始至少连续两天登录的玩家的数量,然后除以玩家总数。 查询结果格式如下所示:   前置知识 1.ROUND() 函数 ROUND() 函数用于

    2024年02月13日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包