#include<bits/stdc++.h> #define swap(a, b) { int t = a; a = b; b = t; } usingnamespace std; constint N = 3; constint M = 4; constint TARGRT = 123804765; constint dx[M] = {0, 1, 0, -1}; constint dy[M] = {1, 0, -1, 0}; structpoint { int x, y; }; map<int, int> dist;
inlineintboard2number(int board[N][N]) { int number = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) number = number * 10 + board[i][j];
return number; } inline point number2board(int number, int board[N][N]) { point zero; for (int i = N - 1; i >= 0; i--) for (int j = N - 1; j >= 0; j--) { board[i][j] = number % 10; number /= 10; if (board[i][j] == 0) { zero.x = i; zero.y = j; } } return zero; }
voidbfs(int start) { int board[N][N]; queue<int> q; q.push(start); dist[start] = 0; while (!q.empty()) { int now = q.front(); q.pop(); if (now == TARGRT) return; point zero = number2board(now, board); point next; for (int i = 0; i < M; i++) { next.x = zero.x + dx[i]; next.y = zero.y + dy[i]; if (next.x >= 0 && next.x < N && next.y >= 0 && next.y < N) { swap(board[zero.x][zero.y], board[next.x][next.y]); int next_number = board2number(board); if (dist.count(next_number) == 0) { dist[next_number] = dist[now] + 1; q.push(next_number); } swap(board[zero.x][zero.y], board[next.x][next.y]); } } } } intmain() { int start; cin >> start; bfs(start); cout << dist[TARGRT] << endl; }
int now = TARGRT; int father = search_log[now].first; int direction = search_log[now].second; ans.push_back(dir[direction]); // printf("%c", dir[direction]); while (father != -1) { now = father; father = search_log[now].first; direction = search_log[now].second; ans.push_back(dir[direction]); // printf("%c", dir[direction]); } reverse(ans.begin(), ans.end()); cout << ans<<endl; }
intmain() { while (1) { search_log.clear(); int start = read(); bfs(start); print(); }
// cout << dist[TARGRT] << endl; }
使用康托展开
为了解决 TLE 的问题,我减少了 STL 的使用,不再使用 map 去重和保存历史,而是使用简单的结构体数组
#include<bits/stdc++.h> #define swap(a, b) \ { \ int t = a; \ a = b; \ b = t; \ } usingnamespace std; constint N = 3, M = 4, MAX = 362880, TARGRT = 0; constint FACT[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}; constint dx[M] = {0, 1, 0, -1}; constint dy[M] = {1, 0, -1, 0}; constchar dir[M] = {'u', 'r', 'd', 'l'}; structpoint { int x, y; }; structlog { bool vis; int father; int move_direction; } search_log[MAX]; structnode { int state[9]; point zero_pos; int CantorValue; } start;
inlineintTo1D(point p) { return p.x * 3 + p.y; } inline point To2D(int x) { point p; p.x = x % 3; p.y = x / 3; return p; }
inlineintCantor(int a[9]) { int x = 0; for (int i = 0; i < 9; i++) { int count = 0; for (int j = i + 1; j < 9; j++) { if (a[i] > a[j]) count++; } x += FACT[9 - i - 1] * count; } return x; }
inlinevoidbfs() { //memset(search_log, 0, sizeof(search_log)); queue<node> q; q.push(start); search_log[start.CantorValue].vis = true; search_log[start.CantorValue].father = -1; search_log[start.CantorValue].move_direction = -1; while (!q.empty()) { node now = q.front(); q.pop(); if (now.CantorValue == TARGRT) return;
for (int i = 0; i < M; i++) { point swap_pos = now.zero_pos; swap_pos.x += dx[i]; swap_pos.y += dy[i]; if (swap_pos.x < 0 || swap_pos.x >= 3 || swap_pos.y < 0 || swap_pos.y >= 3) continue; node next = now; swap(next.state[To1D(swap_pos)], next.state[To1D(now.zero_pos)]); next.CantorValue = Cantor(next.state); if (search_log[next.CantorValue].vis) continue; search_log[next.CantorValue].vis = true; next.zero_pos = swap_pos; search_log[next.CantorValue].father = now.CantorValue; search_log[next.CantorValue].move_direction = i; q.push(next); } } } inlineboolis_digit(char c) { return c >= '0' && c <= '9'; } inlineboolread() { char a[9], tmp = getchar(); int i = 0; while (i != 9) { while (!is_digit(tmp) && tmp != 'x') if ((tmp = getchar()) == EOF) returnfalse;
#include<bits/stdc++.h> #define swap(a, b) \ { \ int t = a; \ a = b; \ b = t; \ } usingnamespace std; constint N = 3, M = 4, MAX = 362880, TARGRT = 0; constint FACT[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}; constint dx[M] = {0, 1, 0, -1}; constint dy[M] = {1, 0, -1, 0}; // const char dir[M] = {'u', 'r', 'd', 'l'}; constchar dir[M] = {'l', 'u', 'r', 'd'}; structpoint { int x, y; }; structlog { bool vis; int father; int move_direction; } search_log[MAX]; structnode { int state[9]; point zero_pos; int CantorValue; } start,target = { {1, 2, 3, 4, 5, 6, 7, 8, 9}, {2, 2}, 0};
inlineintTo1D(point p) { return p.x * 3 + p.y; } inline point To2D(int x) { point p; p.x = x % 3; p.y = x / 3; return p; }
inlineintCantor(int a[9]) { int x = 0; for (int i = 0; i < 9; i++) { int count = 0; for (int j = i + 1; j < 9; j++) { if (a[i] > a[j]) count++; } x += FACT[9 - i - 1] * count; } return x; }