天津协会网站建设,推荐设计网站,现在的网站怎样做推广,在线音乐播放网站模板《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
点…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
点灯游戏” 链接
http://oj.ecustacm.cn/problem.php?id1134 题目描述
【题目描述】 有一个n*n的灯泡矩阵b表示灯暗w表示灯亮。每个灯的位置上都有控制着这盏灯的按钮。当按下一个按钮后该按钮以及周围位置(上下左右)的灯都会改变状态亮-暗暗-亮。最少按下多少个按钮可以使得所有的灯都亮或者都暗。 【输入格式】 输入有多组数据每组数据第一行有一个整数n1≤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)。 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代码
#includebits/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位设置成vif(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*nmemset(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 (1n); k) { //k是第0行的按钮有0000~1111种按钮设置memcpy(Lights, oriLights, sizeof(oriLights)); int switchs k; //第0行的按钮例如k0011就是按第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], j1); //j后面的第j1灯变色}}if(i n-1) Lights[i1] ^ switchs; //修改下一行的灯switchs Lights[i]; //第i1行按钮位置和第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] (1j))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], j1);}}if (i n-1) Lights[i1] ^ 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替换为临时字符xMap[i] Map[i].replace(w, b); // 将w替换为bMap[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代码 import sys
def GetBit(x, i): return (x i) 1def SetBit(x, i, v):if v: x | (1 i)else: x ~(1 i)return xdef FlipBit(x, i):x ^ (1 i)return xdef solve(n, Map):oriLights [0] * nfor 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 1for k in range(1 n):switchs kLights oriLights[:]result [0] * nfor i in range(n):result[i] switchsfor 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], j1)if i n-1: Lights[i1] ^ switchsswitchs Lights[i]if Lights[-1] 0:tmp 0for i in range(n):for j in range(n):if result[i] (1 j):tmp 1ans min(ans, tmp)return ansfor line in sys.stdin:n int(line.strip())if n 0: breakMap []for i in range(n): Map.append(input().strip())ans solve(n, Map)F {}F[b] wF[w] bfor 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)
