抛砖引玉
#include
#include
#include
const int kMaxK = 5;
const int kMaxN = 8;
const int kMaxS = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5;
#define DEBUG(v) std::cerr << #v << " = " << (v) << "\n"
int N, K, max_state;
short top[kMaxS][kMaxK];
int G[kMaxS][kMaxK * (kMaxK - 1) + 1];
int src = 0, dst = 0;
int f[kMaxS];
int pow(int base, int power) {
int r = 1;
for (int i = 0; i < power; r *= base, ++i);
return r;
}
int get(int num, int d) {
for (int i = 0; i < d; num /= K, ++i);
return num % K;
}
int set(int num, int d, int v) {
int co = 1, r;
for (int i = 0; i < d; co *= K, ++i);
r = num % co;
return ((num / (co * K)) * K + v) * co + r;
}
int init() {
max_state = pow(K, N);
//DEBUG(max_state);
for (int state = 0; state < pow(K, N); ++state) {
//for (int disc = 0; disc < N; ++disc) { std::cout << get(state, disc); }
//std::cout << std::endl;
for (int peg = 0; peg < K; ++peg) {
top[state][peg] = -1;
for (int disc = 0; disc < N; ++disc) {
if (get(state, disc) == peg) {
top[state][peg] = disc;
break;
}
}
//std::cout << top[state][peg] << " ";
}
//std::cout << std::endl;
}
return 0;
}
int BuildGraph() {
memset(G, 0, sizeof(G));
for (int state = 0; state < max_state; ++state) {
for (int pfr = 0; pfr < K; ++pfr) {
for (int pto = 0; pto < K; ++pto) {
if (pfr != pto && top[state][pfr] != -1 &&
(top[state][pto] == -1 || top[state][pfr] < top[state][pto])) {
//std::cout << state << " " << pfr << " " << pto << std::endl;
//for (int i = 0; i < N; ++i) { std::cout << get(state, i); }
//std::cout << "--(" << pfr << ", " << pto << ")-->";
G[state][++G[state][0]] = set(state, top[state][pfr], pto);
//int tmp = G[state][G[state][0]];
//for (int i = 0; i < N; ++i) { std::cout << get(tmp, i); }
//std::cout << std::endl;
//std::cout << G[state][G[state][0]] << std::endl;
}
}
}
}
return 0;
}
void print(int v) {
if (f[v] != v) {
print(f[v]);
for (int i = 0; i < K; ++i) {
int pfr = get(f[v], i), pto = get(v, i);
if (pfr != pto) {
std::cout << pfr + 1 << " " << pto + 1 << std::endl;
break;
}
}
}
}
int solve() {
std::cin >> N >> K;
init();
BuildGraph();
int co = 1;
for (int i = 0; i < N; ++i, co *= K) {
int peg;
std::cin >> peg;
src = src + (peg - 1) * co;
}
co = 1;
for (int i = 0; i < N; ++i, co *= K) {
int peg;
std::cin >> peg;
dst = dst + (peg - 1) * co;
}
//DEBUG(src);
//DEBUG(dst);
for (int state = 0; state < max_state; f[state++] = -1);
f[src] = src;
std::vector queue;
queue.push_back(src);
int top = 0;
while (f[dst] == -1) {
int v = queue[top++];
for (int i = 1; i <= G[v][0]; ++i) {
if (f[G[v][i]] == -1) {
//for (int ii = 0; ii < N; ++ii) {std::cout << get(v, ii); } std::
cout << "->";
//for (int ii = 0; ii < N; ++ii) {std::cout << get(G[v][i], ii); }
std::cout << std::endl;
f[G[v][i]] = v;
queue.push_back(G[v][i]);
}
}
}
print(dst);
return 0;
}
int main(int argc, char *argv[]) {
solve();
return 0;
}
