您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1178 Camelot：國王與騎士的最小聚集移動數 (Floyd-Warshall + DP)

編輯：關於C++

問題描述

在一個 8×8 的棋盤上，放置一個國王和若干騎士（最多 63 個）。國王每步可移動到相鄰的 8 個方格之一（如圖 2），騎士則按「日」字走法跳躍（如圖 3）。棋盤格子足夠大，棋子互不干擾，可重疊。

目標是將所有棋子移動到同一格子，且總移動步數最小。特殊規則：當國王與一個或多個騎士位於同一格時，玩家可選擇讓國王與其中一個騎士合體，之後以騎士的方式移動（視為單一騎士），直到最終聚集點。這種合體移動只算一步。

輸入格式

輸入為一字串，包含最多 64 個互不相同的棋盤位置。第一個位置為國王，其餘為騎士。位置以「字母+數字」表示，字母為橫向座標（A-H），數字為縱向座標（1-8）。騎士數量 0 到 63。

輸出格式

輸出一個整數，表示達成聚集所需的最小移動步數。

範例

Sample Input: D4A3A8H1H8
Sample Output: 10

解題思路

預處理最短路徑：棋盤只有 64 個格子，先用 Floyd-Warshall 算法分別計算國王和騎士在棋盤上任意兩格之間的最短步數。國王移動為 8 向鄰居，騎士為 8 種跳躍，均不超出邊界。
枚舉聚集點：最終聚集點可能是棋盤上任一格子（0~63），枚舉所有可能。
枚舉「接王騎士」：國王必須先走到某格子與某騎士會合，該騎士再背負國王前往聚集點。枚舉會合格子 j（0~63）與負責接王的騎士 k。
計算總步數：
- 國王從起點走到會合點 j：king[kingPos][j]
- 騎士 k 從起點走到會合點 j：knight[knightPos[k]][j]
- 騎士 k 背負國王從 j 走到聚集點 g：knight[j][g]
- 其餘騎士直接從起點走到聚集點 g：sum_{i!=k} knight[knightPos[i]][g]
總步數 = 上述四項之和。取所有 g、j、k 的最小值即為答案。

關鍵代碼片段 (C++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int KING_MOVE[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
const int KNIGHT_MOVE[8][2] = {{1,2},{2,1},{1,-2},{2,-1},{-1,2},{-2,1},{-1,-2},{-2,-1}};
int kingDist[64][64], knightDist[64][64];

int main() {
    // 初始化距離矩陣
    memset(kingDist, 0x3f, sizeof(kingDist));
    memset(knightDist, 0x3f, sizeof(knightDist));
    for (int i = 0; i < 64; ++i) kingDist[i][i] = knightDist[i][i] = 0;
    // 建圖
    for (int r = 0; r < 8; ++r) {
        for (int c = 0; c < 8; ++c) {
            int u = r * 8 + c;
            for (int d = 0; d < 8; ++d) {
                int nr = r + KING_MOVE[d][0], nc = c + KING_MOVE[d][1];
                if (nr >= 0 && nr < 8 && nc >= 0 && nc < 8) {
                    int v = nr * 8 + nc;
                    kingDist[u][v] = 1;
                }
                nr = r + KNIGHT_MOVE[d][0]; nc = c + KNIGHT_MOVE[d][1];
                if (nr >= 0 && nr < 8 && nc >= 0 && nc < 8) {
                    int v = nr * 8 + nc;
                    knightDist[u][v] = 1;
                }
            }
        }
    }
    // Floyd-Warshall
    for (int k = 0; k < 64; ++k)
        for (int i = 0; i < 64; ++i)
            for (int j = 0; j < 64; ++j) {
                kingDist[i][j] = min(kingDist[i][j], kingDist[i][k] + kingDist[k][j]);
                knightDist[i][j] = min(knightDist[i][j], knightDist[i][k] + knightDist[k][j]);
            }
    // 讀入並求解
    string s;
    while (cin >> s) {
        int kingPos = (s[0] - 'A') * 8 + (s[1] - '1');
        vector<int> knights;
        for (size_t i = 2; i < s.size(); i += 2)
            knights.push_back((s[i] - 'A') * 8 + (s[i+1] - '1'));
        int ans = INF;
        // 枚舉聚集點 g
        for (int g = 0; g < 64; ++g) {
            // 若無騎士，國王直接走到 g
            if (knights.empty()) {
                ans = min(ans, kingDist[kingPos][g]);
                continue;
            }
            // 枚舉會合點 j 與接王騎士 k
            for (int j = 0; j < 64; ++j) {
                for (size_t k = 0; k < knights.size(); ++k) {
                    int cost = kingDist[kingPos][j] + knightDist[knights[k]][j] + knightDist[j][g];
                    for (size_t i = 0; i < knights.size(); ++i)
                        if (i != k) cost += knightDist[knights[i]][g];
                    ans = min(ans, cost);
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}