题解：P10449 费解的开关

· · 题解

分析

由题意得，开关灯的操作是可逆的，也就是说，在 6 步内可以变成灯全亮的游戏状态都可以通过将一个灯全亮的状态在按 6 步内按成。

简而言之，一个灯全亮的矩阵，在按 6 步或更少的步数后所能成为的矩阵即是所有的可还原游戏状态，且所按步数为还原的最小步数。

思路

从全亮的状态开始，递归搜索 6 步以内所能达到的全部灯的状态，由于每一个矩阵由 25 个二进制元素组成，所以可以状态压缩为一个在 [0,33,554,431] 范围内的整数，由此可以直接将其存入一个数组内，用下标表示这个整数（即游戏状态），用数值表示最小步数。

可行的剪枝：

  1. 记录前一个按到的灯坐标，避免多次按同一个位置
  2. 如果发现这个状态比已存储的状态所需步数还多，那么其引申出的所有状态也一定比更优状态引申出的状态步数多，此时没有必要继续递归（更优状态引申出的状态一定更优）

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

short bt[35000000];
inline int compress(bool b[10][10]) //状态压缩函数，将一个游戏状态压缩为一个整数 
{
    int zip=0;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            zip=(zip<<1)+b[i][j];
    return zip;
}
void DFS(bool now[10][10],int lx,int ly,int step)   //lx，ly 分别表示前一个按灯的坐标 
{
    int zip=compress(now);
    if(bt[zip]<=step) return;   //剪枝 #2 
    bt[zip]=min(bt[zip],(short)step);
    if(step>=6) return;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
        {
            if(i==lx&&j==ly) continue;  //剪枝 #1 
            now[i][j]^=1,now[i-1][j]^=1,now[i+1][j]^=1,now[i][j-1]^=1,now[i][j+1]^=1;
            DFS(now,i,j,step+1);
            now[i][j]^=1,now[i-1][j]^=1,now[i+1][j]^=1,now[i][j-1]^=1,now[i][j+1]^=1;
        }
    return;
}

bool haha[10][10];
char st[10];
int main()
{
    memset(bt,0x3f,sizeof(bt));
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            haha[i][j]=true;    //构造灯全亮的状态 
    DFS(haha,-1,-1,0);
    int n; scanf("%d",&n);
    while(n--)
    {
        for(int i=1;i<=5;i++)
        {
            scanf("%s",st);
            for(int j=1;j<=5;j++)
                haha[i][j]=st[j-1]-'0';
        }
        int zip=compress(haha);
        printf("%d\n",bt[zip]==0x3f3f?-1:bt[zip]);  //读取储存的状态 
    }
    return 0;
}