PIPIOJ 1356: PIPI的保险箱

1356: PIPI的保险箱

题目描述

PIPI有一个保险箱，里面装着《中南机试满分秘籍》。为了自己的代码功力大涨，你决定某天趁PIPI外出盗窃这本秘籍。
PIPI的保险箱上有九个旋钮，每个旋钮可以转为1，2，3，4这四个数字之一，但是旋钮只能按照一个方向旋转，即：1→2→3→4→1。同时，PIPI的保险箱为了防盗还有一个特性，每当你手动旋转一个旋钮，另一个旋钮也会由于齿轮带动跟着旋转。只有手动旋转旋钮才会使另一个旋钮跟着旋转，故不存在连锁反应。
身为江湖盗圣，你不难得知这九个旋钮同时为1时，即可开启保险箱。请问你最少手动旋转多少次即可开启PIPI的保险箱？

输入

输入一共9行，每行5个整数，描述保险箱的状态。
第i行第1个数字表示该旋钮的初始状态。接下来4个数字，第j个数字Aij表示这个旋钮在数字为j时手动旋转，会引起第Aij个旋钮旋转。

输出

输出最少旋转次数。
如果无解，输出-1。

样例输入

4 2 3 4 2
4 3 4 5 6
4 4 5 6 4
4 5 6 7 8
4 6 7 8 6
4 7 8 9 1
4 8 9 1 8
4 9 1 2 1
1 1 2 3 4

样例输出

4

思路

广度优先搜索，使用字符串来存储状态，使用集合来标记状态。

#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
    string s;int t;
}node;
int main()
{
    
// freopen("in.cpp", "r", stdin);int a[9][5];string x;for(int i = 0; i < 9; i++){
    for(int j = 0; j < 5; j++)scanf("%d", &a[i][j]);x.push_back(a[i][0] + '0');}unordered_set<string> hash;queue<node> q;q.push({
    x, 0});hash.insert(x);node p;while(!q.empty()){
    p = q.front();q.pop();if(p.s == "111111111"){
    printf("%d\n", p.t);return 0;}for(int i = 0; i < 9; i++){
    x = p.s;x[a[i][x[i] - '0'] - 1]++; //先转动连锁按钮 if(x[a[i][x[i] - '0'] - 1] > '4')x[a[i][x[i] - '0'] - 1] = '1';x[i]++;if(x[i] > '4')x[i] = '1';if(hash.count(x) != 1){
    q.push({
    x, p.t + 1});hash.insert(x);}}}puts("-1");return 0;
}