题解 P2040 【打开所有的灯】

潘捷 · 2017-06-22 14:33:58 · 题解

其实有一个很明显的规律：最多不会超过9.

深搜也可以做( •̀ ω •́ )y。不会超时。

如代码：

#include<iostream>
using namespace std;
int a[5][5],ans=0,Mix=10;//定义变量 
void dd(int x,int y)
{
    a[x][y]=1-a[x][y];
    a[x+1][y]=1-a[x+1][y];
    a[x][y+1]=1-a[x][y+1];
    a[x-1][y]=1-a[x-1][y];
    a[x][y-1]=1-a[x][y-1];//处理按一次灯 
}
void dfs(int k)
{
    if(k>Mix) {return;}//限制，Mix不小于k的话会超时 
    int s=0;
    for(int i=1;i<=3;i++)
      for(int j=1;j<=3;j++)
        s+=a[i][j];
    if(s==9){ans=k-1;if(ans<Mix)Mix=ans;}//判断真儿子 
    for(int i=1;i<=3;i++)
      for(int j=1;j<=3;j++)
        {
            dd(i,j);
            dfs(k+1);
            dd(i,j);

}//搜索

    return;
}
int main()//主程序 
{
    for(int i=1;i<=3;i++)
      for(int j=1;j<=3;j++)
        cin>>a[i][j];//输入 
    dfs(1);
    cout<<Mix;//输出 
}