AcWing 1107. 魔板(不会用map的悲哀)
原题链接
简单
#include <queue>
#include <stack>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5;
int a[2][MAXN];
bool vis[9][9][9][9][9][9][9][9];
struct node {
stack<char> rou;
int tem[2][MAXN];
};
queue<node> s;
void MakeSet();
void bfs();
void inout(node);
int main() {
for(int i = 1; i <= 4; i++) scanf("%d", &a[0][i]);
for(int i = 1; i <= 4; i++) scanf("%d", &a[1][5 - i]);
MakeSet();
bfs();
// for(int i = 1; i <= 4; i++) printf("%d ", a[1][i]);
// printf("\n");
// for(int i = 1; i <= 4; i++) printf("%d ", a[2][i]);
return 0;
}
void MakeSet() {
node z;
for(int i = 1; i <= 4; i++) z.tem[0][i] = i;
for(int i = 1; i <= 4; i++) z.tem[1][i] = 9 - i;
s.push(z);
// for(int i = 1; i <= 4; i++) printf("%d ", z.tem[1][i]);
// printf("\n");
// for(int i = 1; i <= 4; i++) printf("%d ", z.tem[2][i]);
}
void bfs() {
while(1) {
node z = s.front();
bool flag = true;
for(int i = 1; i <= 4; i++)
if(z.tem[0][i] != a[0][i] || z.tem[1][i] != a[1][i])
flag = false;
if(flag == true) {
inout(z);
return;
}
// for(int i = 1; i <= 4; i++) printf("%d ", z.tem[0][i]);
// printf("\n");
// for(int i = 1; i <= 4; i++) printf("%d ", z.tem[1][i]);
// printf("\n");
// char he[MAXN * MAXN];
// int sum = 0;
// while(!z.rou.empty()) he[++sum] = z.rou.top(), z.rou.pop();
// for(int i = sum; i >= 1; i--) printf("%c", he[i]), z.rou.push(he[i]);
// printf("\n\n");
s.pop();
for(int i = 1; i <= 4; i++) swap(z.tem[0][i], z.tem[1][i]);
if(vis[z.tem[0][1]][z.tem[0][2]][z.tem[0][3]][z.tem[0][4]][z.tem[1][1]][z.tem[1][2]][z.tem[1][3]][z.tem[1][4]] == 0) {
vis[z.tem[0][1]][z.tem[0][2]][z.tem[0][3]][z.tem[0][4]][z.tem[1][1]][z.tem[1][2]][z.tem[1][3]][z.tem[1][4]] = 1;
z.rou.push('A');
s.push(z);
z.rou.pop();
}
for(int i = 1; i <= 4; i++) swap(z.tem[0][i], z.tem[1][i]);//还原
//A
for(int i = 4; i >= 1; i--) z.tem[0][i + 1] = z.tem[0][i], z.tem[1][i + 1] = z.tem[1][i];
z.tem[0][1] = z.tem[0][5], z.tem[1][1] = z.tem[1][5];
if(vis[z.tem[0][1]][z.tem[0][2]][z.tem[0][3]][z.tem[0][4]][z.tem[1][1]][z.tem[1][2]][z.tem[1][3]][z.tem[1][4]] == 0) {
vis[z.tem[0][1]][z.tem[0][2]][z.tem[0][3]][z.tem[0][4]][z.tem[1][1]][z.tem[1][2]][z.tem[1][3]][z.tem[1][4]] = 1;
z.rou.push('B');
s.push(z);
z.rou.pop();
}
for(int i = 1; i <= 4; i++) z.tem[0][i] = z.tem[0][i + 1], z.tem[1][i] = z.tem[1][i + 1];//还原
//B
int pro = z.tem[0][2];
z.tem[0][2] = z.tem[1][2];
z.tem[1][2] = z.tem[1][3];
z.tem[1][3] = z.tem[0][3];
z.tem[0][3] = pro;
if(vis[z.tem[0][1]][z.tem[0][2]][z.tem[0][3]][z.tem[0][4]][z.tem[1][1]][z.tem[1][2]][z.tem[1][3]][z.tem[1][4]] == 0) {
vis[z.tem[0][1]][z.tem[0][2]][z.tem[0][3]][z.tem[0][4]][z.tem[1][1]][z.tem[1][2]][z.tem[1][3]][z.tem[1][4]] = 1;
z.rou.push('C');
s.push(z);
}
//C
}
}
void inout(node x) {
int sum = 0;
stack<char> ans;
while(!x.rou.empty()) ans.push(x.rou.top()), x.rou.pop(), sum++;
printf("%d\n", sum);
while(!ans.empty()) printf("%c", ans.top()), ans.pop();
}
我。。。。
6
666
你是真的秀和😂
666