题解：P10449 费解的开关

· · 题解

P10449 费解的开关

暴力深搜

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

优点：

  1. 能过。
  2. ......

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

思路：找到图中为 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 oper(int a,int b){//操作 （ operate的简写 ） ， 改变坐标为(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;//找到的点不在图中，无法改变
                                                  //状态。
        oper(x2,y2);//改变该点的状态。
        su(a+1);//继续深搜修改过后的图。
        oper(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;
}