Eight digital issues
In 3 × On the chessboard of 3, there are eight pieces, each marked with a number from 1 to 8. There is a space in the chessboard, which is represented by 0. The pieces around the space can be moved into the space.
the above is the description of the eight digit problem.
Eight numbers and reverse order pairs
Now, given two game situations with numbers, please judge whether there is a way to move spaces so that one situation can be changed into another.
two situations of eight digital games can be reached. If and only if the two situations are written in one-dimensional form, the parity of the reverse order pair of numbers is the same. The proof is simple, divided into two cases. The first case: when we move the space position left and right, the one-dimensional form sequence remains unchanged, so the reverse order pair parity remains unchanged. The second case: when we move the space position up and down, the performance in one-dimensional form is that a number is exchanged with two numbers in its front (rear) face. At this point, we will discuss it in two cases.
- If the two numbers exchanged with it are larger (smaller) than it, the number of reverse pairs will be reduced (increased) by 2. The number parity of the reverse order pair remains unchanged.
- If one of the two numbers exchanged with him is larger than him and the other is smaller than him, then the addition and subtraction of the number of reverse pairs will not change, so the parity of the number of reverse pairs remains unchanged.
then we can maintain a tree array for the given situation twice, find the number of reverse pairs twice (or use merge sort to find the reverse pairs), and then judge whether the parity is the same.
Portal: tree array and reverse pair
#include<bits/stdc++.h>
using namespace std;
int n = 8;
int a[10] = { 0 };
int b[10] = { 0 }; // Initial state
int c[10] = { 0 }; // End state
int t[50] = { 0 }; // Tree array
inline int lowbit(int x){
return x & -x;
}
void add(int index, int val){
for(; index <= n; index += lowbit(index)){
t[index] += val;
}
}
int query(int x){
int ans = 0;
for(; x; x -= lowbit(x)){
ans += t[x];
}
return ans;
}
int main(){
scanf("%1d %1d %1d %1d %1d %1d %1d %1d %ld", &a[1], &a[2], &a[3], &a[4], &a[5], &a[6], &a[7], &a[8], &a[9]);
bool is1 = false;
for(int i = 1; i <= n + 1; i++){
if(!a[i]) { is1 = true; continue; }
if(is1) b[i-1] = a[i];
else b[i] = a[i];
}
/*
for(int i = 1; i <= n; i++){
printf("%d ", b[i]);
}
puts("");
*/
scanf("%1d %1d %1d %1d %1d %1d %1d %1d %ld", &a[1], &a[2], &a[3], &a[4], &a[5], &a[6], &a[7], &a[8], &a[9]);
bool is2 = false;
for(int i = 1; i <= n + 1; i++){
if(!a[i]) { is2 = true; continue; }
if(is2) c[i-1] = a[i];
else c[i] = a[i];
}
/*
for(int i = 1; i <= n; i++){
printf("%d ", c[i]);
}
puts("");
*/
int ans1 = 0;
for(int i = n; i >= 1; i--){
ans1 += query(b[i] - 1);
add(b[i], 1);
}
//printf("ans1 = %d\n", ans1);
memset(t, 0, sizeof(t));
int ans2 = 0;
for(int i = n; i >= 1; i--){
ans2 += query(c[i] - 1);
add(c[i], 1);
}
//printf("ans2 = %d\n", ans2);
if(ans1 % 2 == ans2 % 2){
printf("Can be reached\n");
}
else{
printf("Can not be reached\n");
}
return 0;
}
VIII. Digital problems and A*
The problem to be solved now is to give an initial layout (initial state) and target layout (in order to make the topic simple, set the target state as 123804765), find a minimum step moving method, and realize the transformation from initial layout to target layout.
first, use the above method to judge whether the problem is solvable. If the problem has A solution, we use the A * algorithm to search A scheme with the minimum number of steps of the mobile part. We make the evaluation function as the current position and the target position. There are several different positions, namely:
f
(
s
t
a
t
e
)
=
∑
i
=
1
9
(
s
t
a
t
e
x
i
=
=
g
o
a
l
x
i
a
n
d
s
t
a
t
e
y
i
=
=
g
o
a
l
y
i
)
?
0
:
1
f(state) = \sum_{i=1}^{9} (state_{xi} == goal_{xi} \; and \; state_{yi} == goal_{yi}) \; ? \; 0 \; : \; 1
f(state)=i=1∑9(statexi==goalxiandstateyi==goalyi)?0:1
then every time we use the current steps g(state) plus f(state) to expand, the final state is the optimal solution when it is taken out of the heap for the first time.
#include<bits/stdc++.h>
using namespace std;
const int px[4] = { 1, 0, -1, 0 };
const int py[4] = { 0, 1, 0, -1 };
int n = 8;
char s[20];
int x = 0; int y = 0; // Coordinates of 0
string goal = "123804765";
int h(string current){ // There are several different positions between the current position and the target position (evaluation function)
int ans = 0;
for(int i = 0; i < 9; i++){
if(goal[i] != current[i] and goal[i] != 0) ans++;
}
return ans;
}
struct Tnode{
int f, step; // The value of the current evaluation function and the number of steps taken
string now; // Current arrangement
bool operator < (const Tnode &x) const {
return step + f > x.step + x.f; // Sort by the current number of steps plus the evaluation function
}
};
int ans = 0x7fffffff;
priority_queue<Tnode> q;
map<string, int> dis;
map<string, bool> way;
void bfs(char s[]){
way[s] = 1; dis[s] = 0;
q.push((Tnode){h(s), 0, s}); // Starting point stacking
while(!q.empty()){
Tnode t = q.top(); q.pop();
string cur = t.now;
if(cur == "123804765"){
printf("%d\n", t.step);
exit(0);
}
int tx = 0; int ty = 0;
for(int i = 0; i < 9; i++){ // Position of current arrangement 0
if(cur[i] - '0' == 0){
tx = i / 3 + 1; ty = i % 3 + 1;
}
}
int idx1 = (tx - 1) * 3 + ty - 1; // Position in one-dimensional arrangement
for(int i = 0; i < 4; i++){ // extend
int nx = tx + px[i]; int ny = ty + py[i];
if(nx < 1 or nx > 3 or ny < 1 or ny > 3) continue;
int idx2 = (nx - 1) * 3 + ny - 1; // Location after expansion
swap(cur[idx1], cur[idx2]);
if(!way[cur] or (way[cur] and (t.step + 1) < dis[cur])){
dis[cur] = t.step + 1;
q.push((Tnode){h(cur), t.step + 1, cur});
way[cur] = 1;
}
swap(cur[idx1], cur[idx2]);
}
}
}
int main(){
scanf("%s", s);
for(int i = 0; i < 9; i++){
if(s[i] - '0' == 0){
x = i / 3 + 1; y = i % 3 + 1; // Initial coordinates of 0
}
}
if(h(s) == 0){ // Initial status and target status: return directly
printf("%d\n", 0);
return 0;
}
while(!q.empty()) q.pop();
bfs(s); // Start search
return 0;
}
The above is the code of Luogu P1379. Portal: luoguP1379