Title Description

After successfully inventing the magic cube, Mr. Rubik invented a two-dimensional version of it, called the magic board. This is a magic board with 8 grids of the same size:

1 2 3 4

8 7 6 5

We know that each square of the magic board has a color. These eight colors are represented by the first eight positive integers. A color sequence can be used to represent a magic board state. It is specified that starting from the upper left corner of the magic board, integers are taken out in turn clockwise to form a color sequence. For the state of the magic board in the figure above, we use the sequence (1, 2, 3, 4, 5, 6, 7, 8). This is the basic state.

Three basic operations are provided here, which are represented by capital letters "A", "B" and "C" (the state of the magic board can be changed through these operations):

"A": exchange the upper and lower lines;

"B": insert the rightmost column into the leftmost column;

"C": the four spaces in the center of the magic board rotate clockwise.

The following is an example of operating the basic state:

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

For each possible state, these three basic operations can be used.

You should program and calculate, complete the transformation from the basic state to the target state with the least basic operation, and output the basic operation sequence.

[input format]

There are multiple sets of test data entered

There is only one line, including 8 integers, separated by spaces (these integers are in the range of 1-8), indicating the target state.

[output format]

Line 1: includes an integer indicating the length of the shortest operation sequence.

Line 2: the earliest operation sequence in the dictionary sequence, which is represented by a string. Except for the last line, each line outputs 60 characters.

Sample Input

2 6 8 4 5 7 3 1

Sample Output

7 BCABCCB

Idea: use 8-bit integers to record the status. When processing, first convert it to character array form, and then convert it back to integers after processing. The steps are recorded with vector.

#include <cstdio> #include <queue> #include <unordered_map> using namespace std; int goal = 0; struct node { int num, step; vector<char> v; } Node; unordered_map<int, bool> inq; //Mark whether to join the team void change(char str[], int way) { //Three operations if (way == 0) { char temp; for (int i = 0; i < 4; i++) { temp = str[i]; str[i] = str[7 - i]; str[7 - i] = temp; } } else if (way == 1) { char temp = str[3]; for (int i = 3; i > 0; i--) { str[i] = str[i - 1]; } str[0] = temp; temp = str[4]; for (int i = 4; i < 7; i++) { str[i] = str[i + 1]; } str[7] = temp; } else if (way == 2) { char temp = str[1]; str[1] = str[6]; str[6] = str[5]; str[5] = str[2]; str[2] = temp; } } void BFS() { queue<node> Q; Node.num = 12345678;//Initial state Node.step = 0; Q.push(Node); inq[12345678] = true; char temp1[10]; int temp2; while (!Q.empty()) { node top = Q.front(); Q.pop(); if (top.num == goal) { //Get target status printf("%d\n", top.step); for (int i = 0; i < top.step; i++) { if (i % 60 == 0 && i != 0) { printf("%c\n", top.v[i]); } else { printf("%c", top.v[i]); } } } for (int i = 0; i < 3; i++) { sprintf(temp1, "%d", top.num); //Convert numbers to character arrays change(temp1, i); //Three operations sscanf(temp1, "%d", &temp2); //Then convert the character array to numbers if (!inq[temp2]) { Node.num = temp2; Node.step = top.step + 1; Node.v = top.v; Node.v.push_back(i + 'A'); //Record steps Q.push(Node); inq[temp2] = true; } } } } int main() { int n = 0; for (int i = 0; i < 8; i++) { scanf("%d", &n); goal = goal * 10 + n; } BFS(); return 0; }