题目传送门：P2040 打开所有的灯

---

用深度优先搜索实现的一个填色题。

题目步骤：

1..dfs

        首先dfs要判断是否符合题意，如果符合题意就更新最短路；

        如果不符合题意就枚举  如果是关的就把周围四个包括  给标记上和原来相反的（代码实现：）

2.main

        直接输入进这个二维数组然后把ans要判断min的值设大一点就行了

这道题dfs不需要用什么值来判定边界，只需要一个step来记录步数就行了。

代码：

#include<bits\stdc++.h>
#include<math.h>
using namespace std;
long long a[5][5],ans;
bool mapp[5][5]={false};
void dfs(long long step){bool flag=true;for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){if(a[i][j]==0){flag=false;break;}}}if(flag){ans=min(ans,step-1);}//更新最小值else{for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){if(!mapp[i][j]){mapp[i][j]=true;a[i][j]!=a[i][j];a[i-1][j]!=a[i-1][j];a[i][j-1]!=a[i][j-1];a[i+1][j]!=a[i+1][j];a[i][j+1]!=a[i][j+1];dfs(step+1);//搜索mapp[i][j]=false;a[i][j]!=a[i][j];a[i-1][j]!=a[i-1][j];//回溯a[i][j-1]!=a[i][j-1];a[i+1][j]!=a[i+1][j];a[i][j+1]!=a[i][j+1];}}}}
}
int main(){for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cin>>a[i][j];}}ans=9999999999;//设大一点memset(mapp,false,sizeof(mapp));dfs(1);cout<<ans;return 0;
}