Problem H

Chinese Checkers

Chinese Checkers is a commercial variant of the older Scandinavian game called Halma. In this contest we propose a simplified version in a rectangular chessboard for two players.

Imagine a rectangular chessboard divided into L lines and C columns (usually C smaller than L). In each square (intersection of a line with a column) of that matrix there is a hole to support a piece of the game. The base of the rectangle (bottom) is line 1 and the top is line L; columns are numbered from 1 to C from left to right.

Each player has as starting field (its "home") at the bottom or at the top of the chess-board, and he has P=2*C pieces (different colors for each players) that inserts into the holes of the two first rows of his field (lines 1 and 2 for the first Player, and lines L-1 and L for the second Player). The main goal of each player is to invade the other player's field with his own P pieces, moving just one piece each time. The winner is the player that first reaches the goal.

One piece can be moved from its position to a free hole on the left, on the right, or in front (moving only one step). Or else, it can jump over one other piece (belonging to any one of both players, colors doesn't matter) in a straight line or along a diagonal to the next hole (right, left or in front) if it is free; this jump can continue as many times as it is possible in the same play (if in the new hole it is possible to jump over a piece to another free hole in the neighborhood).

Problem

The aim is to plan just one round for a selected piece of Player 1 (the one that starts at the base of the chess-board), given the position (coordinates of the hole) of the 2*P pieces, at that precise moment of the game.

The question is to know all the movements that the selected piece can do; we just want to know the number of steps or jumps and the coordinates of the hole achieved. So your task is to write a program to read from an input file the status of the game and to produce the required plan.

Input

The input is composed of several test cases. Each one starts with a line containing two numbers defining, respectively, the number L of rows and the number C of columns in the chess-board. The following 2*P lines, are the coordinates (line and column) of each piece. The last line of each case contains the coordinates of the selected piece, this is the piece of Player 1 for which we want to plan the possible movements.

Output

The output for each test case must be separated by a blank line.

Each test case must have one line for each possible movement, containing 3 numbers separated by one space. These numbers are: the coordinates of the destination hole (line and column) and the number of steps/jumps. The result must be sorted in decreasing order of lines and increasing order of columns. If there is more than one way for a single piece to reach a destination, output the minimum amount of steps/jumps needed to reach that destination.

The following sample illustrates the status of the chessboard at the starting of the game: all pieces are at "home" (this is, in their initial holes in both starting fields). In that configuration, Player 1 wants to plan the movements for piece (1,4).

Sample Input

Sample Output

3 2 1
3 4 1

Pedro Henriques, MIUP'2002

題目描述：

遊戲有點類似跳棋，不過我已經忘了他從哪裡傳來的。

要求找到移動一次，所有可能的步數為何？並且輸出位置以及跳躍的個數，如果不存在跳躍輸出一步。

跳躍可以執行很多次，但每次跳躍只能往左右前、左上、右上，這六種可能，

跳躍的時候必須跨過一個存在的棋子。

而不執行跳躍，則只能走一步，方向只有左、右、前三種。

對於同一個位置，輸出最少的跳躍次數。

題目解法：

BFS 即可。

#include <stdio.h>
#include <set>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
int g[105][105] = {};
int dx[] = {1,0,0,1,1};
int dy[] = {0,1,-1,-1,1};
struct E {
    int x, y, s;
    E(int a, int b, int c):
        x(a), y(b), s(c) {}
    bool operator<(const E &a) const {
        if(x != a.x)    return x > a.x;
        return y < a.y;
    }
};
int main() {
    /*freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout);*/
    int n, m, cases = 0;
    int x, y, s, sx, sy;
    int i, j, k;
    while(scanf("%d %d", &n, &m) == 2) {
        int p = 4*m;
        memset(g, 0, sizeof(g));
        for(i = 0; i < p; i++) {
            scanf("%d %d", &x, &y);
            g[x][y] = 1;
        }
        scanf("%d %d", &sx, &sy);
        set<E> ret;
        queue<int> X, Y, S;
        X.push(sx), Y.push(sy), S.push(0);
        int tx, ty, ttx, tty;
        /*printf("sx : %d sy : %d\n", sx, sy);
        for(i = 1; i <= n; i++, puts(""))
            for(j = 1; j <= m; j++)
                printf("%2d", g[i][j]);*/
        while(!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            s = S.front(), S.pop();
            for(i = 0; i < 5; i++) {
                tx = x+dx[i], ty = y+dy[i];
                if(tx < 1 || ty < 1 || tx > n || ty > m)
                    continue;
                ttx = tx+dx[i], tty = ty+dy[i];
                if(ttx < 1 || tty < 1 || ttx > n || tty > m)
                    continue;
                if(g[tx][ty] == 1 && g[ttx][tty] == 0) {
                    E tmp(ttx, tty, s+1);
                    if(ret.find(tmp) == ret.end()) {
                        ret.insert(tmp);
                        X.push(ttx), Y.push(tty), S.push(s+1);
                    }
                }
            }
        }
        for(i = 0; i < 3; i++) {
            tx = sx+dx[i], ty = sy+dy[i];
            if(tx < 1 || ty < 1 || tx > n || ty > m)
                continue;
            if(g[tx][ty] == 0) {
                ret.insert(E(tx, ty, 1));
            }
        }
        if(cases)   puts("");
        ++cases;
        for(set<E>::iterator it = ret.begin();
            it != ret.end(); it++) {
            printf("%d %d %d\n", it->x, it->y, it->s);
        }
    }
    return 0;
}

我要檢舉

#859#Chinese Checkers

台長： Morris

您可能對以下文章有興趣

[UVA][math][JAVA] 10643 - Facing Problem With Trees

[UVA][dp] 11285 - Exchange Rates

[UVA][dp][BIT] 11240 - Antimonotonicity

[UVA][floyd-warshall][difficult] 125 - Numbering Paths

人氣(1,262) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 949 - Getaway
此分類上一篇:[UVA] 314 - Robot

回應(0)