# Question D: [introduction to wide search] magic board

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;
}
```

Keywords: codeup

Added by mr_tron on Thu, 03 Feb 2022 06:50:22 +0200