[UVA][IDA*] 11163 - Jaguar King＠Morris' Blog｜PChome Online 個人新聞台

2013-08-28 07:38:05| 人氣3,261| 回應0 | 上一篇 | 下一篇

[UVA][IDA*] 11163 - Jaguar King

推薦 0 收藏 0 轉貼0 訂閱站台

J	Next Generation Contest 3	Time Limit: 8 seconds
	Jaguar King

In a deep forest, a war is going to begin. Like other animals, the jaguars are preparing for this ultimate battle. Though they are mighty strong and lightening fast, they have an extra advantage over other animals. It�s their wise and brave king, the Jaguar King.

The king knows that only speed and strength is not enough for winning the war. They have to make a perfect formation. The king has set up a nice formation and placed all the Jaguar Warriors according to that formation. There are N positions for N jaguar warriors (including the king). The king is marked by 1 and the other jaguar warriors are marked by a number from 2 to N. The warriors are placed according to their number.

But then the king realizes that to make the formation perfect and effective, some positions should have stronger jaguars and some should have faster jaguars. Since the strength and speed of all the jaguars are not equal, the king decided to change the positions of some jaguars. The wise king knows the ability of each and every jaguar, so his decision is perfect but the problem is how to change the jaguars.

One of the wise jaguars has given an idea. The idea is simple. All the jaguars will wait for the king's signal, all eyes upon the king. Suppose the king is in the ith position. The king jumps to jth position and when the jaguar at jth position sees the king coming, he immediately jumps to ith position. The king repeats this procedure until they are formatted like the new formation. Now there is another problem. Collision can occur while jumping. So, some wise jaguars have made a jumping scheme so that no collision can occur. The scheme is noted below:

If the king is in the ith position

������� If (i % 4 = 1) The king can jump to position (i+1), (i+3), (i+4), (i-4)

������� If (i % 4 = 2) The king can jump to position (i+1), (i-1), (i+4), (i-4)

������� If (i % 4 = 3) The king can jump to position (i+1), (i-1), (i+4), (i-4)

������� If (i % 4 = 0) The king can jump to position (i-3), (i-1), (i+4), (i-4)

Any position is valid if it lies in between 1 and N.

Actually the king can jump much higher between these positions so, no collision can occur. Now you are one of the prisoners (actually they kept you to eat after the war). You have got a chance to get out alive. You know all their ideas and the new formation. If you can tell the king the minimum number of times the king has to jump to gain the new formation, they could be generous and release you.

Input

The input file contains several sets of inputs. The total number of sets will be less than 50. The description of each set is given below:

Each set starts with one integer N (4 ≤ N ≤ 40) which indicates the total number of jaguar warriors. You can assume that N is multiple of 4. The next line will contain N numbers which indicates the final formation of the jaguars. Consecutive numbers will be separated by a single space.

The input will be terminated by the set where N = 0. And this set should not be processed.

Output

For each set in the input, you should first print the set number starting from 1. And the next line should be the minimum number of times the king has to jump to gain the new formation.

Check the sample input-output for more details. Output should be formatted like the sample output.

Sample Input

Output for Sample Input

1 2 3 4

4 2 3 1

5 2 3 4 8 6 7 1

5 2 8 3 6 7 1 4

Set 1:

Set 2:

Set 3:

Set 4:

Hope you get out alive.

Problem Setter: Jane Alam Jan
Special Thanks: Sohel Hafiz

題目描述：

只有豹王1 可跳躍，跳到的地方與原本的豹交換位置，求排序最少的跳躍次數。

豹王跳躍的地方根據當前位置有所限制，但是不跳出序列外。

題目解法：

IDA* 搜索，估價函數跟 8-puzzle 一樣，計算每個點歸位的最短路徑，由於特殊的限制，

因此先做一次最短路徑，把所有點的移動最少路徑加總。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int g[45][45];
int dx[4][4] = {{-3,-1,+4,-4},{+1,+3,+4,-4},{+1,-1,+4,-4},{+1,-1,+4,-4}};
int A[45], n;
void build() {
    int i, j, k;
    for(i = 1; i <= 40; i++) {
        for(j = 1; j <= 40; j++)
            g[i][j] = 0xfffffff;
        g[i][i] = 0;
    }
    for(i = 1; i <= 40; i++)
        for(j = 0; j < 4; j++)
            if(i+dx[i%4][j] > 0 && i+dx[i%4][j] <= 40)
                g[i][i+dx[i%4][j]] = 1;
    for(k = 1; k <= 40; k++)
        for(i = 1; i <= 40; i++)
            for(j = 1; j <= 40; j++)
                g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
}
int H() {
    int i, sum = 0;
    for(i = 1; i <= n; i++) {
        if(A[i] == 1)   continue;
        sum += g[i][A[i]];
    }
    return sum;
}
int singleH(int pos) {
    return g[pos][A[pos]];
}
int mxdep, solved;
int IDA(int x, int prev, int dep, int hv) {
    if(hv == 0) {
        solved = dep;
        return dep;
    }
    if(dep+hv > mxdep) return dep+hv;
    int i, tx;
    int submxdep = 0xfffffff, shv, tmp;
    for(i = 0; i < 4; i++) {
        tx = x+dx[x%4][i];
        if(tx == prev || tx <= 0 || tx > n)
            continue;
        shv = hv;
        shv -= singleH(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;
    build();
    while(scanf("%d", &n) == 1 && n) {
        for(i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        printf("Set %d:\n", ++cases);
        int initH = H();
        if(initH == 0)
            puts("0");
        else {
            solved = 0;
            mxdep = initH;
            for(i = 1; i <= n; i++)
                if(A[i] == 1)
                    x = i;
            while(solved == 0)
                mxdep = IDA(x, -1, 0, initH);
            printf("%d\n", solved);
        }
    }
    return 0;
}

我要檢舉

#11163#Jaguar King

台長： Morris

您可能對以下文章有興趣

[UVA][遞迴] 12596 - Recursive Texting

[UVA][Greedy] 12405 - Scarecrow

[UVA][DP] 435 - Block Voting

[UVA] 196 - Spreadsheet

人氣(3,261) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][dp] 1172 - The Bridges of Kolsberg
此分類上一篇:[UVA][A*] 1217 - Route Planning

回應(0)