Test Message

b237: CSAPC'09 迷宮任務

內容

在一個 n 乘以 m 大小的迷宮當中，你必須依序執行很多項搬東西的任務。每一個任務都有起始點 A 以及終點 B 。行動的時候如果手上沒有搬東西，就不會耗費任何體力，但是如果手上有東西，那麼耗費的體力就是以移動「一格」消耗一單位的體力來計算。而所謂移動「一格」是指從目前迷宮中的位置往東、南、西、北四個方向前進一步的長度。有趣的是，經過你的縝密觀察，儘管迷宮內部相當複雜，它一定會遵守「右手定則」，也就是說，只要摸著右手邊的牆壁不斷地往前行走，終究可以踏遍迷宮中的每一塊空地，並且連所有空地周圍看得到的圍牆部分都被你摸過了。聰明的你在執行每一個任務的時候，都會挑選最短路徑搬運指定物品。請問執行完所有任務以後你所需要耗費的最少體力總和是多少？

輸入

輸入的第一行包含三個正整數 n, m, Q 。接下來我們用 n 列(rows)每一列以 m 個字元來表示迷宮。迷宮內部標註 ‘.’ 的部份是空地，標記 ‘#’ 的部份是牆。迷宮最外圍一定都是牆壁。接下來有 Q 列分別代表 Q 項任務的起點和終點，每一列包含四個整數 x, y, z, w ，代表每一項任務從 (x, y) 出發，並且在 (z, w) 結束。注意到迷宮的編號方式以左上角為 (0, 0) ，右下角為 (n-1, m-1) 。你可以假設輸入的所有座標都會是空地的座標。 迷宮裡面不會有 2x2 的空地出現。 (edit: 11/16 10:17am)

10 10 6
##########
#......#.#
#####.#..#
#####...##
###.#.#.##
###.#.#..#
##...#..##
##.#..#.##
#...#....#
##########
1 1 1 1
3 6 1 3
3 6 6 3
2 8 2 5
2 5 2 8
7 4 6 2

輸出

請輸出依序執行完所有任務後所需要耗費的最小體力。

30

解題思路

因為題目保證"迷宮裡面不會有 2x2 的空地出現"所以可以將這個迷宮視為一個樹，而在一個樹狀結構中點到點的距離會是

點 a 到 LCA[1](a,b) 的距離 + 點 b 到 LCA(a,b) 的距離

而這兩者相加亦會等於

點 a 到 根的距離 + 點 B 到 根的距離 - LCA(a,b)到根的距離 * 2

所以說只要知道 a , b 和 LCA(a,b) 與根的相對深度就能求出答案了。

但由於本題詢問量很大，如果每次詢問都一個一個找時間複雜度為

O(q*(a+b))) q = 詢問數， a(b) = 各詢問中點 a(b) 到 LCA(a,b) 的距離

這樣會花費太多時間，所以改用離線 Tarjan 演算法配合並查集先找出所有點對點的 LCA ，之後只需要 O(1) 的時間就可以完成查詢。

但是本題範圍較大，建立 LCA 表記憶體會不夠用，所以改成先把所有查詢紀錄起來，之後再一邊遍歷節點一邊計算答案，遍歷結束後輸出答案即可。

  • 本題各測資點皆只有一筆測資，輸入量不小
  • 程式碼中 tarjan() 不需判斷是否被遍歷過是因為在建立的時候已經將多餘的情況給過濾掉了。

註解

  1. LCA = Lowest Common Ancestor = 最低共同祖先

參考資料

完整程式碼

正常版

AC (22ms, 3.6MB)
#include <stdio.h>
#define MAX 255
#define MAX2 62500

typedef struct
{
    int val[4], * top;
}Stack;

typedef struct
{
    int val, next;
}Query;

Stack list[MAX2];
Query qList[50005];
int map[MAX][MAX], parent[MAX2], query[MAX2], depth[MAX2],sum, len, qTop;
char input[MAX][MAX];

void dfs(int i, int j, int dep)
{
    int idx = ++len;
    parent[idx] = map[i][j] = idx;
    depth[idx] = dep;
    list[idx].top = list[idx].val;
    if (input[i + 1][j] == '.' && !map[i + 1][j])
        dfs(i + 1, j, dep + 1), * list[idx].top++ = map[i + 1][j];
    if (input[i - 1][j] == '.' && !map[i - 1][j])
        dfs(i - 1, j, dep + 1), * list[idx].top++ = map[i - 1][j];
    if (input[i][j + 1] == '.' && !map[i][j + 1])
        dfs(i, j + 1, dep + 1), * list[idx].top++ = map[i][j + 1];
    if (input[i][j - 1] == '.' && !map[i][j - 1])
        dfs(i, j - 1, dep + 1), * list[idx].top++ = map[i][j - 1];
}

inline void setDepth(int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (input[i][j] == '.')
            {
                dfs(i, j, 0);
                return;
            }
        }
    }
}

inline void addQuery(int from, int to)
{
    qTop++;
    qList[qTop].val = to;
    qList[qTop].next = query[from];
    query[from] = qTop;
}

int find(int i)
{
    return i == parent[i] ? i : (parent[i] = find(parent[i]));
}

void tarjan(int i)
{
    for (Query* j = &qList[query[i]]; j->val; j = &qList[j->next])
        sum += depth[i] + depth[j->val] - (depth[find(j->val)] << 1);
    for (int* j = list[i].val; j < list[i].top; j++)
    {
        tarjan(*j);
        parent[*j] = i;
    }
}

int main()
{
    int n, m, q, sX, sY, eX, eY, s, e;
    scanf(" %d %d %d", &n, &m, &q);
    getchar();
    for (int i = 0, idx = 0; i < n; i++)
        gets(input[i]);
    setDepth(n, m);
    for (int i = 0; i < q; i++)
    {
        scanf(" %d %d %d %d", &sX, &sY, &eX, &eY);
        s = map[sX][sY], e = map[eX][eY];
        if (s < e)
            addQuery(e, s);
        else
            addQuery(s, e);
    }
    tarjan(1);
    printf("%d\n", sum);
    return 0;
}

輸入優化版

AC (8ms, 4.3MB)
#include <stdio.h>
#define MAX 255
#define MAX2 62500
#define BUFSIZ 1048576

typedef struct
{
    int val[4], * top;
}Stack;

typedef struct
{
    int val, next;
}Query;

Stack list[MAX2];
Query qList[50005];
int map[MAX][MAX], parent[MAX2], query[MAX2], depth[MAX2], sum, len, qTop;
char input[MAX][MAX];

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readString(register unsigned char* dst)
{
    register char ch;
    while ((ch = readChar()) <= ' ')
        if (ch == EOF) return 0;
    *dst++ = ch;
    while ((ch = readChar()) > ' ')
        * dst++ = ch;
    return 1;
}

inline char readUInt(register unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

void dfs(int i, int j, int dep)
{
    int idx = ++len;
    parent[idx] = map[i][j] = idx;
    depth[idx] = dep;
    list[idx].top = list[idx].val;
    if (input[i + 1][j] == '.' && !map[i + 1][j])
        dfs(i + 1, j, dep + 1), * list[idx].top++ = map[i + 1][j];
    if (input[i - 1][j] == '.' && !map[i - 1][j])
        dfs(i - 1, j, dep + 1), * list[idx].top++ = map[i - 1][j];
    if (input[i][j + 1] == '.' && !map[i][j + 1])
        dfs(i, j + 1, dep + 1), * list[idx].top++ = map[i][j + 1];
    if (input[i][j - 1] == '.' && !map[i][j - 1])
        dfs(i, j - 1, dep + 1), * list[idx].top++ = map[i][j - 1];
}

inline void setDepth(int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (input[i][j] == '.')
            {
                dfs(i, j, 0);
                return;
            }
        }
    }
}

inline void addQuery(int from, int to)
{
    qTop++;
    qList[qTop].val = to;
    qList[qTop].next = query[from];
    query[from] = qTop;
}

int find(int i)
{
    return i == parent[i] ? i : (parent[i] = find(parent[i]));
}

void tarjan(int i)
{
    for (Query* j = &qList[query[i]]; j->val; j = &qList[j->next])
        sum += depth[i] + depth[j->val] - (depth[find(j->val)] << 1);
    for (int* j = list[i].val; j < list[i].top; j++)
    {
        tarjan(*j);
        parent[*j] = i;
    }
}

int main()
{
    int n, m, q, sX, sY, eX, eY, s, e;
    scanf(" %d %d %d", &n, &m, &q);
    for (int i = 0, idx = 0; i < n; i++)
        readString(input[i]);
    setDepth(n, m);
    for (int i = 0; i < q; i++)
    {
        readUInt(&sX), readUInt(&sY);
        readUInt(&eX), readUInt(&eY);
        s = map[sX][sY], e = map[eX][eY];
        if (s < e)
            addQuery(e, s);
        else
            addQuery(s, e);
    }
    tarjan(1);
    printf("%d\n", sum);
    return 0;
}