[UVA][IDA*] 10073 - Constrained Exchange Sort
Problem D
Constrained Exchange Sort
Input : standard input
Output : standard output
Given a permutation of 12 letters 'A'-'L', you are invited to write a program to sort them in ascending order under the following set of constraints:
q The only allowed operation is the exchange of letters between two locations (locations are numbered from 1 to 12).
q The letter 'L' must be involved in each operation.
q The letter 'L' at location l1 can be swapped with the letter at location l2 provided l1 ~ l2 = di and floor((l1 - 1) / di + 1) = floor((l2 - 1) / di + 1)for i = 1 | 2 | 3, where (d1, d2, d3, d4) = (1, 3, 6, 12).
q You must use the minimum number of exchange operations possible.
Input
The first line of the input file contains an integer representing the number of test cases to follow.
Each test case contains a permutation of the letters 'A'-'L' on a line by itself. It is guaranteed that the given permutation can be sorted in ascending order under the given set of constraints.
Output
For each test case first output the permutation number on a line by itself. The next line will contain a sequence of letters where the letter at location i represents the letter with which 'L' is swapped in the i-th exchange during the sorting process. Output an empty line after each test case.
Sample Input
2BKLAIGFHEDCJ
LIFDHJAKEGCB
Sample Output
Permutation #1EHCJGIKCJGIECBADFJGFJGHIFKEF
Permutation #2
AKIHCBJCBJEFCEFIKGJKHBEF
Rezaul Alam Chowdhury
題目描述：
A-L 12 個字母要做排序，找最少交換次數。
每次交換兩個字母，並且其中一個要是 L。
而交換的距離必須恰好符合給定的條件。
題目解法：
先把可以交換的情況都做紀錄，並且做一次 all pair 的最短路徑。
用這個最短路徑做估價函數，直接套用 IDA* 模板即可。
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
using namespace std;
int g[12][12];// loaction shortest path
int moveable[12][12] = {};
int dx[] = {1,3,6,-1,-3,-6};
int A[12], n;
void build() {
int i, j, k;
for(i = 0; i < 12; i++) {
for(j = 0; j < 12; j++)
g[i][j] = 0xfffffff;
g[i][i] = 0;
}
for(i = 0; i < 12; i++) {
for(j = 0; j < 12; j++) {
int di = abs(i-j);
if(di == 1 && i/3 == j/3)
moveable[i][j] = g[i][j] = 1;
if(di == 3 && i/6 == j/6)
moveable[i][j] = g[i][j] = 1;
if(di == 6 && i/12 == j/12)
moveable[i][j] = g[i][j] = 1;
}
g[i][i] = 0;
}
for(k = 0; k < 12; k++)
for(i = 0; i < 12; i++)
for(j = 0; j < 12; j++)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
/*for(i = 0; i < 12; i++, puts(""))
for(j = 0; j < 12; j++)
printf("%d ", g[i][j]);*/
}
int H() {
int i, sum = 0;
for(i = 0; i < 12; i++) {
if(A[i] == 11) continue;
sum += g[i][A[i]];
}
return sum;
}
int singleH(int pos) {
return g[pos][A[pos]];
}
int mxdep, solved;
int step[105], ret[105];
int IDA(int x, int prev, int dep, int hv) {
if(hv == 0) {
solved = dep;
for(int i = 0; i < dep; i++)
printf("%c", step[i]+'A');
puts("");
return dep;
}
if(dep+hv > mxdep) return dep+hv;
int i, tx;
int submxdep = 0xfffffff, shv, tmp;
for(i = 0; i < 6; i++) {
tx = x+dx[i];
if(tx == prev || tx < 0 || tx >= 12)
continue;
if(moveable[x][tx] == 0)
continue;
shv = hv;
shv -= singleH(tx);
step[dep] = A[tx];
swap(A[x], A[tx]);
shv += singleH(x);
tmp = IDA(tx, x, dep+1, shv);
if(solved) return solved;
swap(A[x], A[tx]);
submxdep = min(submxdep, tmp);
}
return submxdep;
}
int main() {
int i, j, k, x;
int cases = 0;
int testcases;
char s[1024];
build();
scanf("%d", &testcases);
while(testcases--) {
scanf("%s", s);
for(i = 0; i < 12; i++)
A[i] = s[i]-'A';
printf("Permutation #%d\n", ++cases);
int initH = H();
if(initH == 0)
puts("");
else {
solved = 0;
mxdep = initH;
for(i = 0; i < 12; i++)
if(A[i] == 11)
x = i;
while(solved == 0) {
mxdep = IDA(x, -1, 0, initH);
}
}
puts("");
}
return 0;
}