自动搬运

查看原文

来自洛谷，原作者为

	hgfs 不会高精度的看这里！

搬运于2025-08-24 22:58:03，当前版本为作者最后更新于2024-07-20 12:43:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷 P10449 费解的开关

暴力深搜

（ 816ms / 564.00KB / 1011B C++98 O2）

优点：

1. ( 几乎无 ）

故曰 ： 仅作为一种新思路供参考。

思路：找到图中为 $0$ 的点，搜索周围四个点及他本身（改变这 $5$ 个点才能使该点为 $1$ ），直到整张图都为 $1$ 。（因为太过直接和暴力，所以好像再没什么多的解释了。）

部分难点：

1. 偏移数组：利用两个数组对应的元素进行上下左右偏移。（偏移数组通常意味着你有一个指针指向一个数组，并且你想要根据某个偏移量来访问数组中的元素。这可以通过使用指针算术来实现。（百度上的定义））

（剩余胎教请见注释）

代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,s,px[5]={0,-1,0,1,0},py[5]={0,0,1,0,-1};//n 为 n 个待解决的游戏初始状态，
// s 记录每个状态中，遍历到不同的点时最少步数， px 和 py 是偏移数组（见上）。
bool g[10][10],an;//g是geography，即游戏初始状态；an判断是否有answer。
string a;//用来输入。 

int check(){//判断整张图是否都为 1 , 至于为什么是 int , 请看下面的返回值的注释 。 
	for(int i=1;i<=5;i++)
	for(int j=1;j<=5;j++)
	if(!g[i][j]) return i;//返回出现 0 的行数 ，减少运算 。 
	return 0;//表示整张图都为 1 。 
}

void zuo(int a,int b){//操作 （ zuo ） ， 改变坐标为(a,b) 的点及四周的点的状态。 
	for(int i=0;i<=4;i++)
	g[a+px[i]][b+py[i]]=!g[a+px[i]][b+py[i]];
}

void su(int a){//深搜第 a 步。 
    if(a>7) return;//步数过多，直接排除。
	int x=check(),y;//x 行 y 列，即该步改变状态的点的坐标。 
    if(!x){//此时整张图都为 1 。
		s=min(s,a);//每次整张图都为 1 时最小的步数。 
		an=1;//已有 answer !! 
		return;
	}
	for(int i=1;i<=5;i++)//寻找此时图中状态为 0 的点。 
	if(!g[x][i]){// x 已在定义的时候找出了。 
		y=i;//定位到此时状态为 0 的点。
		break;
	}
	for(int i=0;i<=4;i++){//列举包括自己共 5 个点 ， 一一搜索一遍。
		int x2=x+px[i],y2=y+py[i];//确定点的坐标。
		if(x2<1 || x2>5 || y2<1 || y2>5) continue;//找到的点不在图中，无法改变
		                                          //状态。
		zuo(x2,y2);//改变该点的状态。
		su(a+1);//继续深搜修改过后的图。
		zuo(x2,y2);//状态还原，为了不影响以后的遍历。
	}

int main(){
	cin>>n;
	while(n--){
		s=10;// 初始为较大值（大于 6 即可）。
		an=0;// 初始无 answer（答案）。 
		for(int i=1;i<=5;i++){// 输入。
			cin>>a;
			for(int j=1;j<=5;j++) g[i][j]=a[j-1]-'0';
		}
		su(1);// 从第 1 个操作开始。 
		if(an) cout<<s-1<<endl;// 有答案。 
		else cout<<-1<<endl;// 无答案输出 -1 。 
	}
	return 0;