智慧点灯&打开所有的灯-题解

题目：普及难度 DFS算法(暴力求解) 洛谷

目录

1.题目分析&推证DFS边界

2.代码实现

题目分析&推证DFS边界

读题可知，这道题求的就是最少多少步，可以打开全部灯泡
那么我们很容易可以想到使用DFS暴力枚举每一种结果，也就是模拟每一次开灯的位置

但是此处的DFS如何确定边界呢？？？

如样例:

0 1 1
1 0 0
1 0 1

点击两次(2,2)
结果还是

0 1 1
1 0 0
1 0 1

依次点击(2,2)(3,3)这样重复两次 结果还是

0 1 1
1 0 0
1 0 1

我们可以知道点击同一个地方两次，结果不会发生任何改变 (废话

这样的话就可以得出结论

对于点击一个或多个地方两次或以上次数是无用(重复)的

这样的话我们就很清晰地确定了DFS的边界

当出现已经点击过的灯时跳过

当步数step>9时结束DFS剪枝(这个好像没用)

对于实现可以使用vis标记数组，不要忘记回溯

代码实现

#include <bits/stdc++.h>
using namespace std;
int vis[8][8];//标记数组 
int G[8][8];
int dir_x[]={-1,1,0,0,0};//方向数组 
int dir_y[]={0,0,-1,1,0};
int amin=10000000;
void turn_back(int x,int y){//转换&&回溯函数 
	for(int i=0;i<=4;i++){
		int ax=x+dir_x[i];
		int ay=y+dir_y[i];
		G[ax][ay]=!G[ax][ay];
	}	
}
void dfs(int x,int y,int step){
	vis[x][y]=0;
	turn_back(x,y);
	
	int ans=0;
	for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){ans+=G[i][j];}}
	if(ans==9){
		amin=min(step,amin);
		return ;
	}//遍历G,查看是否全部变为1 
	
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(vis[i][j]){
				dfs(i,j,step+1);
				vis[i][j]=1;
				turn_back(i,j);
			}
		}
	}
}
int main(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			cin>>G[i][j];
			vis[i][j]=1;
		}
	} 
	for(int i=1;i<=3;i++){//每个都Dfs,暴力搜索求解0 
		for(int j=1;j<=3;j++){
			dfs(i,j,1);
			cout<<"建设良好ACGO社区,拒绝一味题解抄袭"<<endl;
			vis[i][j]=1;
			turn_back(i,j);
		}
	}
	cout<<amin;
	return 0;
}