成品网站建设价格建站推广网站

题目描述：

25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

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

主要思想：每一行的暗灯都由下面一行去点亮。

第一步我们先要去枚举第一行的所有按法

枚举第一行的所有按法是用来减少步数的，如果从第二行开始其实就已经固定了最后的答案，这样的解不一定是最少的甚至可能超出范围而没有解。

枚举第一行的意义是：不需要在意第一行的灯是灭是暗，只需把第一行的按法枚举一遍，也就是我们说的 “操作”，每个位置都有两种选择，按(用1表示)或者不按(用0表示)，遍历这32种操作引发的情况，每一次再通过res = min(res, step);把最小步数存一下，就能找到最优解

步骤：

1️⃣枚举第一行时：1表示按一下，0表示不按
2️⃣在遍历整个矩阵时：1是灯亮，0是灯灭
3️⃣memcpy 可以用来复制数组，这里是先把原数组备份一下，然后对本数组操作，本次操作结束后，要再把备份数组还原回来，再进行下一次操作

代码:

#include <bits/stdc++.h>
using namespace std;const int N = 6;char g[N][N],backup[N][N];
int dx[] = {-1,0,1,0,0},dy[] = {0,1,0,-1,0};void turn(int x,int y)
{for (int i = 0;i < 5;i++){int ax = x + dx[i],ay = y + dy[i];if(ax < 0 || ax > 4 || ay < 0 || ay > 4) continue;g[ax][ay] ^= 1;}
}int main()
{int t;cin >> t;while (t--)