sicily_1150 简单魔板

题目

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge

Description

魔板由8个大小相同方块组成，分别用涂上不同颜色，用1到8的数字表示。

其初始状态是

1 2 3 4
8 7 6 5

对魔板可进行三种基本操作：

A操作（上下行互换）：

8 7 6 5
1 2 3 4

B操作（每次以行循环右移一个）：

4 1 2 3
5 8 7 6

C操作（中间四小块顺时针转一格）：

1 7 2 4
8 6 3 5

用上述三种基本操作，可将任一种状态装换成另一种状态。

Input

输入包括多个要求解的魔板，每个魔板用三行描述。

第一行步数N（不超过10的整数），表示最多容许的步数。

第二、第三行表示目标状态，按照魔板的形状，颜色用1到8的表示。
当N等于-1的时候，表示输入结束。

Output

对于每一个要求解的魔板，输出一行。

首先是一个整数M，表示你找到解答所需要的步数。接着若干个空格之后，从第一步开始按顺序给出M步操作（每一步是A、B或C），相邻两个操作之间没有任何空格。
注意：如果不能达到，则M输出-1即可。

Sample Input

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

Sample Output

2 AB
1 A

评分：M超过N或者给出的操作不正确均不能得分。

思路

1. 封装魔板的状态，每个状态对应一个到达此状态的最优路径
2. 用广度搜索来获得每个状态的最优路径。例如，AA、BBBB、CCCC这几个操作是没有效果的，所以可以把一个已经遍历的过的状态放在closed表里面，这样就可以利用已经遍历过的状态简化。
3. 把所有步数小于等于N的状态都查找过了，才算是查找完成。

代码

剪枝版代码

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// 1150 简单魔板: http://soj.sysu.edu.cn/1150
#include <cstdio>
#include <string>
#include <queue>
#include <vector>

using namespace std;

struct Node {
  int state[2][4];
  string opt;
};

Node doA(Node node);
Node doB(Node node);
Node doC(Node node);

bool isEqualState(Node A, Node B);
int find(vector<Node> closed, Node tofind);

int main() {
  int maxSteps;
  Node aim;

  Node start;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 4; j++) {
      if (!i) {
        start.state[i][j] = j + 1;
      } else {
        start.state[i][j] = 8 - j;
      }
    }
  }

  while (scanf("%d", &maxSteps) != EOF && maxSteps != -1) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 4; j++) {
        scanf("%d", &aim.state[i][j]);
      }
    }

    vector<Node> closed;
    queue<Node> que;

    que.push(start);
    // closed.push_back(start);
    while (!que.empty()) {
      Node current = que.front();
      que.pop();

      if (current.opt.size() > maxSteps) {
        printf("-1\n");
        break;
      }

      if (isEqualState(current, aim)) {
        printf("%d %s\n", current.opt.size(), current.opt.c_str());
        break;
      }

      int index = find(closed, current);
      if (index != -1) {
        current = closed[index];
      } else {
        closed.push_back(current);
      }

      Node Anext = doA(current);
      if (find(closed, Anext) == -1) que.push(Anext);
      Node Bnext = doB(current);
      if (find(closed, Bnext) == -1) que.push(Bnext);
      Node Cnext = doC(current);
      if (find(closed, Cnext) == -1) que.push(Cnext);
    }
  }

  return 0;
}

Node doA(Node node) {
  Node Anext;
  for (int i = 0; i < 4; i++) {
    Anext.state[0][i] = node.state[1][i];
    Anext.state[1][i] = node.state[0][i];
  }

  Anext.opt = node.opt + 'A';

  return Anext;
}

Node doB(Node node) {
  Node Bnext;
  for (int i = 0; i < 4; i++) {
    Bnext.state[0][i] = node.state[0][(i - 1 + 4) % 4];
    Bnext.state[1][i] = node.state[1][(i - 1 + 4) % 4];
  }
  Bnext.opt = node.opt + 'B';

  return Bnext;
}

Node doC(Node node) {
  Node Cnext;
  for (int i = 0; i < 4; i++) {
    Cnext.state[0][i] = node.state[0][i];
    Cnext.state[1][i] = node.state[1][i];
  }

  Cnext.state[0][1] = node.state[1][1];
  Cnext.state[0][2] = node.state[0][1];
  Cnext.state[1][1] = node.state[1][2];
  Cnext.state[1][2] = node.state[0][2];

  Cnext.opt = node.opt + 'C';

  return Cnext;
}

bool isEqualState(Node A, Node B) {
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 4; j++) {
      if (A.state[i][j] != B.state[i][j]) return false;
    }
  }
  return true;
}

int find(vector<Node> closed, Node tofind) {
  for (int i = 0; i < closed.size(); i++) {
    if (isEqualState(closed[i], tofind)) return i;
  }
  return -1;
}

参考

http://blog.csdn.net/chocolate_22/article/details/6543684