C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 6240K, 提交时间: 2019-01-07 16:55:43
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define N 1000005
#define M 7
#define UP 1
#define DOWN -1
char a[M], b[M];
int factor[M], num[6];
bool vis[N][6];
struct Node{
int val, idx, step;
Node(int v, int i, int s): val(v), idx(i), step(s) {}
};
int get_hash(char s[M]){
int res = 0;
for(int i = 0; i < 6; ++i)
res = s[i] - '0' + res * 10;
return res;
}
inline int swap(int num, int idx1, int idx2){
int v1 = (num / factor[idx1]) % 10;
int v2 = (num / factor[idx2]) % 10;
num += (v2 - v1) * factor[idx1];
num += (v1 - v2) * factor[idx2];
return num;
}
inline int up_down(int num, int idx, int ops){
return num + ops * factor[idx];
}
int bfs(int orig, int dest){
memset(vis, false, sizeof(vis));
queue<Node> qu;
qu.push(Node(orig, 0, 0));
vis[orig][0] = true;
while(!qu.empty()){
Node cur = qu.front();
qu.pop();
int sta = cur.val, idx = cur.idx, step = cur.step;
if(sta == dest)
return step;
++step;
if(idx != 0){ //swap0
int next = swap(sta, 0, idx);
if(!vis[next][idx])
qu.push(Node(next, idx, step)), vis[next][idx] = true;
}
if(idx != 5){ //swap1
int next = swap(sta, 5, idx);
if(!vis[next][idx])
qu.push(Node(next, idx, step)), vis[next][idx] = true;
}
int val = (sta / factor[idx]) % 10;
if(val != 9 && val != num[idx]){ //up
int next = up_down(sta, idx, UP);
if(!vis[next][idx])
qu.push(Node(next, idx, step)), vis[next][idx] = true;
}
if(val != 0 && val != num[idx]){ //down
int next = up_down(sta, idx, DOWN);
if(!vis[next][idx])
qu.push(Node(next, idx, step)), vis[next][idx] = true;
}
if(idx != 0 && (idx == 5 || val == num[idx])){ //left
if(!vis[sta][idx - 1])
qu.push(Node(sta, idx - 1, step)), vis[sta][idx - 1] = true;
}
if(idx != 5 && (idx == 0 || val == num[idx])){ //right
if(!vis[sta][idx + 1])
qu.push(Node(sta, idx + 1, step)), vis[sta][idx + 1] = true;
}
}
return -1;
}
int main(){
factor[5] = 1;
for(int i = 4; i >= 0; --i)
factor[i] = 10 * factor[i + 1];
scanf("%s %s", a, b);
for(int i = 0; i < 6; ++i)
num[i] = b[i] - '0';
int orig = get_hash(a), dest = get_hash(b);
printf("%d\n", bfs(orig, dest));
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 905ms, 内存消耗: 27860K, 提交时间: 2022-09-12 13:23:02
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define int long long
#define INF 0x7fffffff
using namespace std;
inline int rd(void) {
int x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
int ksm(int a, int b) {
int ans = 1, base = a;
while (b) {
if (b & 1) ans = ans * base;
base = base * base;
b >>= 1;
}
return ans;
}
const int maxn = 999999 * 10 + 20;
int T, n, m;
bool vis[maxn];
int a[8];
struct ss {
int x, val, pos;
};
void solve() {
cin >> n >> m;
a[6] = 1;
for (int i = 5; i >=1; i--) a[i] = a[i + 1] * 10;
ss temp{ n * 10 + 1,0,1 };
queue<ss>q;
q.push(temp);
while (!q.empty()) {
int x = q.front().x, v = q.front().val, pos = q.front().pos;
q.pop();
x /= 10;
if (x == m) {
cout << v << endl;
return;
}
int k;
if (pos != 1) {
k = x * 10 + pos - 1;
if (!vis[k]) {
vis[k] = 1;
ss tmp{ k,v + 1,pos - 1 };
q.push(tmp);
}
}
if (pos != 6) {
k = x * 10 + pos + 1;
if (!vis[k]) {
vis[k] = 1;
ss tmp{ k,v + 1,pos + 1 };
q.push(tmp);
}
}
int tt = (x / a[pos]) % 10;
if (tt != 0) {
k = x - a[pos];
k = k * 10 + pos;
if (!vis[k]) {
vis[k] = 1;
ss tmp{ k,v + 1,pos };
q.push(tmp);
}
}
if (tt != 9) {
k = x + a[pos];
k = k * 10 + pos;
if (!vis[k]) {
vis[k] = 1;
ss tmp{ k,v + 1,pos };
q.push(tmp);
}
}
if (pos != 1) {
int v1 = (x / a[1]) % 10, vp = (x / a[pos]) % 10;
k = x - v1 * a[1] + vp * a[1] - vp * a[pos] + v1 * a[pos] ;
k = k * 10 + pos;
if (!vis[k]) {
vis[k] = 1;
ss tmp{ k,v + 1,pos };
q.push(tmp);
}
}
if (pos != 6) {
int v6 = (x / a[6]) % 10, vp = (x / a[pos]) % 10;
k = x - v6 * a[6] + vp * a[6] - vp * a[pos] + v6 * a[pos] ;
k = k * 10 + pos;
if (!vis[k]) {
vis[k] = 1;
ss tmp{ k,v + 1,pos };
q.push(tmp);
}
}
}
}
signed main()
{
T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}
C++ 解法, 执行用时: 5ms, 内存消耗: 2444K, 提交时间: 2021-12-11 14:19:19
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a,b,sa[8],sb[8],q[100005][8],head=0,tail=0;
bool h[10][10][10][10][10][10][7];
inline void mk(int*s){h[s[1]][s[2]][s[3]][s[4]][s[5]][s[6]][s[7]]=true;}
inline bool vis(int*s){return h[s[1]][s[2]][s[3]][s[4]][s[5]][s[6]][s[7]];}
inline bool enq(int*s)
{
if(!vis(s))
{
mk(s);
s[0]++;
memcpy(q[tail++],s,sizeof(q[tail]));
s[0]--;
}
int i;
for(i=1;i<=6;i++)if(q[head-1][i]!=sb[i])break;
if(i==7)
{
printf("%d\n",q[head-1][0]);
return true;
}
return false;
}
int main()
{
scanf("%d%d",&a,&b);
if(a==b)
{
printf("0\n");
return 0;
}
for(int i=6;i>=1;i--){sa[i]=a%10;a/=10;}
for(int i=6;i>=1;i--){sb[i]=b%10;b/=10;}
sa[0]=0;sa[7]=1;
memcpy(q[tail++],sa,sizeof(sa));
mk(sa);
while(head<tail)
{
int state[8];
memcpy(state,q[head++],sizeof(q[head]));
if(state[7]!=1)
{
swap(state[state[7]],state[1]);
if(enq(state))return 0;
swap(state[state[7]],state[1]);
}
if(state[7]!=6)
{
swap(state[state[7]],state[6]);
if(enq(state))return 0;
swap(state[state[7]],state[6]);
}
if(state[state[7]]!=9)
{
state[state[7]]++;
if(enq(state))return 0;
state[state[7]]--;
}
if(state[state[7]]!=0)
{
state[state[7]]--;
if(enq(state))return 0;
state[state[7]]++;
}
//memcpy(state,q[head],sizeof(q[head]));
if(state[7]==1 || state[7]==6 || state[state[7]]==sb[state[7]])
{
if(state[7]!=1)
{
state[7]--;
if(enq(state))return 0;
state[7]++;
}
if(state[7]!=6)
{
state[7]++;
if(enq(state))return 0;
state[7]--;
}
}
}
return 0;
}
