网站建设廴金手指花总壹陆,山东已经宣布封城的城市2022年,wordpress略缩图alt,网站域名解析页面题目背景 上元佳节#xff0c;庙会里举办着各式各样的庆典活动#xff0c;牛宝也兴奋地参与其中。突然#xff0c;他被一个新颖的点灯游戏所吸引#xff0c;游戏要求最终点亮所有在场的花灯#xff0c;每盏灯都有开关两种状态#xff0c;每一次点击在场的一盏任意状态的花…题目背景 上元佳节庙会里举办着各式各样的庆典活动牛宝也兴奋地参与其中。突然他被一个新颖的点灯游戏所吸引游戏要求最终点亮所有在场的花灯每盏灯都有开关两种状态每一次点击在场的一盏任意状态的花灯其自身和四周的的花灯都会改变其开关状态。
例如
3*3的花灯阵
0 1 1
1 0 0
1 0 1
点一下最中间的灯【2,2】就变成了
0 0 1
0 1 1
1 1 1
再点一下左上角的灯【1,1】就变成了
1 1 1
1 1 1
1 1 1
最终输出点亮花灯的序号从左上角到右下角序号依次为1-9答案即点亮1号灯和5号灯。 为了奖品牛宝只能尝试破解3*3的花灯阵你能协助他吗
题目描述 给出3*3的花灯阵各盏花灯的初始开关状态请你按照序号从小到大的顺序点亮花灯从左上角到右下角序号依次为1-9同时要求点亮的次数最少避免多余的点亮步骤使得最终全部花灯均被点亮。
输入格式 九个数字3*3的格式输入每两个数字中间只有一个空格表示灯初始的开关状态。0表示关1表示开
输出格式 按照序号从小到大的顺序点亮花灯从左上角到右下角序号依次为1-9输出点亮的序号集合每两个序号之间用空格隔开。
输入输出样例 输入 0 1 1 1 0 0 1 0 1 输出 1 5 说明/提示 牛宝正在脑海中不停地进行尝试。。。
解题思路: 从左上到右下1-9的顺序进行点亮深搜一旦点亮该灯自身和其四周灯亮灭情况变化保留点亮过程灯号 深搜这条路径无法点亮所有的灯则进行回溯自身和其四周灯亮灭情况变化。 深搜边界条件即点亮所有的灯一旦有更少步数的进行更新方案。
代码如下:
#include iostream
using namespace std;
const int N 5;
int g[N][N];
int ans 10;
int path[10];
bool vis[10];
int paths[10];void turn(int x, int y) { //开关灯g[x][y] 1 - g[x][y];g[x - 1][y] 1 - g[x - 1][y];g[x 1][y] 1 - g[x 1][y];g[x][y 1] 1 - g[x][y 1];g[x][y - 1] 1 - g[x][y - 1];
}void dfs(int n) {if (n ans)return ;//剪枝不剪枝会超时//超过最小的次数就返回初始次数为10规律:它总共步骤不会超过9次int sum 0;for (int i 1; i 3; i)for (int j 1; j 3; j)sum g[i][j];if (sum 9) {ans min(ans, n - 1);for (int i 1; i ans; i) {paths[i] path[i];}return ;}for (int i 1; i 3; i)for (int j 1; j 3; j) {turn(i, j);path[n] (i - 1) * 3 j;//将二维数组转换为一维dfs(n 1);turn(i, j);}}int main() {for (int i 1; i 3; i)for (int j 1; j 3; j)cin g[i][j];dfs(1);for (int i 1; i ans; i) {cout paths[i] ;}return 0;
}
当然因为按2下等于没有按所以我们可以增加一个标记数组这样就会少按很多重复的无效的次数相当于剪枝。
代码如下:
#include iostream
using namespace std;
const int N 5;
int g[N][N];
int ans 10;
int path[10];
int paths[10];
bool vis[N][N];void turn(int x, int y) { //开关灯g[x][y] 1 - g[x][y];g[x - 1][y] 1 - g[x - 1][y];g[x 1][y] 1 - g[x 1][y];g[x][y 1] 1 - g[x][y 1];g[x][y - 1] 1 - g[x][y - 1];
}void dfs(int n) {if (n ans)return ;//剪枝不剪枝会超时//超过最小的次数就返回初始次数为10规律:它总共步骤不会超过9次int sum 0;for (int i 1; i 3; i)for (int j 1; j 3; j)sum g[i][j];if (sum 9) {ans min(ans, n - 1);for (int i 1; i ans; i) {paths[i] path[i];}return ;}for (int i 1; i 3; i)for (int j 1; j 3; j) {if (!vis[i][j]) {vis[i][j] true;turn(i, j);path[n] (i - 1) * 3 j;//将二维数组转换为一维dfs(n 1);vis[i][j] false;turn(i, j);}}}int main() {for (int i 1; i 3; i)for (int j 1; j 3; j)cin g[i][j];dfs(1);for (int i 1; i ans; i) {cout paths[i] ;}return 0;
}
当然如果你想不到怎么把二维数组转换为一维也可以这样写
#includebits/stdc.h
using namespace std;
int s[5][5];int book[5][5];int small10;
int t[10];
int tt[10];
int change(int x,int y)
{s[x][y]1-s[x][y];s[x-1][y]1-s[x-1][y];s[x1][y]1-s[x1][y];s[x][y-1]1-s[x][y-1];s[x][y1]1-s[x][y1];return 0;
}
int dfs(int k)
{if(ksmall)return 0;int sum0;for(int i1;i3;i){for(int j1;j3;j){sums[i][j];}}if(sum9){if(ksmall){smallk;for(int i1;ik;i){tt[i]t[i];}}return 0;}for(int i1;i3;i){for(int j1;j3;j){if(book[i][j]0){if(i1j1)t[k1]1;if(i1j2)t[k1]2;if(i1j3)t[k1]3;if(i2j1)t[k1]4;if(i2j2)t[k1]5;if(i2j3)t[k1]6;if(i3j1)t[k1]7;if(i3j2)t[k1]8;if(i3j3)t[k1]9;change(i,j);book[i][j]1;dfs(k1);change(i,j);book[i][j]0;} }}return 0;
}
int main()
{for(int i1;i3;i){for(int j1;j3;j){cins[i][j];}}dfs(0);for(int i1;ismall;i){couttt[i] ;}return 0;
}
