24h購物| | PChome| 登入
2012-10-31 12:29:28| 人氣1,103| 回應0 | 上一篇 | 下一篇

[ZJ][LCA] b237. CSAPC'09 迷宮任務

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

內容 ：

在一个 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)

輸出說明 ：

请输出依序执行完所有任务后所需要耗费的最小体力。

範例輸入 ：help 

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

提示 ：

测试资料说明

占总分至少 30% 的测试资料中满足 5<= n, m <=30

占总分至少 40% 的测试资料中满足 0 <= Q <= 500

对于所有的测试资料，满足 5<= n, m <=250, 0 <= Q <= 50000 ，并且答案一定不会超过 2147483647 。

出處 ：

CSAPC'09, Problem Setter 黃上恩 (管理：tmt514)

由題目藉由兩個條件, 右手定則會經過所有的點, 且摸過所有的點旁邊的牆壁, 由此可知是個樹狀圖,
因此我們可以去利用 LCA 找到最鄰近的共同祖先找到最短路徑。

補充一下, LCA 是利用中序探訪, 找到中間深度最小的祖先。

#include <stdio.h>
#include <vector>
#define maxN 65536
using namespace std;
typedef struct {
    int nd, dp;
} ELE;
vector<int> g[maxN];
int lidx[maxN], tidx, M;
ELE tree[maxN<<2], stk[maxN<<1];
void dfs(int nd, int dep, int p) {
    if(!lidx[nd])
        lidx[nd] = tidx;
    stk[tidx].nd = nd, stk[tidx++].dp = dep;
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(*it == p)    continue;
        dfs(*it, dep+1, nd);
        stk[tidx].nd = nd, stk[tidx++].dp = dep;
    }
}
void setTree(int n) {
    for(M = 1; M < n+1; M <<= 1);
    for(int i = 2*M-1; i > 0; i--) {
        if(i >= M)
            tree[i] = stk[i-M];
        else {
            if(tree[i<<1].dp < tree[i<<1|1].dp)
                tree[i] = tree[i<<1];
            else
                tree[i] = tree[i<<1|1];
        }
    }
}
ELE query(int s, int t) {
    static int i;
    ELE ans;
    ans.dp = 0xfffff;
    for(s = s+M-1, t = t+M+1; (s^t) != 1;) {
        if(~s&1) {
            if(ans.dp > tree[s^1].dp)
                ans = tree[s^1];
        }
        if(t&1) {
            if(ans.dp > tree[t^1].dp)
                ans = tree[t^1];
        }
        s >>= 1, t >>= 1;
    }
    return ans;
}
int main() {
    int n, m, q, x, i, j;
    int x1, y1, x2, y2;
    char mg[255][255] = {};
    int gn[255][255] = {};
    while(scanf("%d %d %d", &n, &m, &q) == 3) {
        int size = 0;
        for(i = 0; i < n; i++) {
            scanf("%s", mg[i]);
            for(j = 0; j < m; j++) {
                if(mg[i][j] == '.')
                    gn[i][j] = ++size;
            }
        }
        for(i = 0; i < n; i++) {
            for(j = 0; j < m; j++) {
                if(mg[i][j] != '.')
                    continue;
                if(mg[i+1][j] == '.')
                    g[gn[i][j]].push_back(gn[i+1][j]);
                if(mg[i-1][j] == '.')
                    g[gn[i][j]].push_back(gn[i-1][j]);
                if(mg[i][j+1] == '.')
                    g[gn[i][j]].push_back(gn[i][j+1]);
                if(mg[i][j-1] == '.')
                    g[gn[i][j]].push_back(gn[i][j-1]);
            }
        }
        tidx = 0;
        dfs(1, 0, -1);
        setTree(tidx);
        ELE ans;
        int sum = 0;
        while(q--) {
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            i = lidx[gn[x1][y1]], j = lidx[gn[x2][y2]];
            if(i > j)
                x = i, i = j, j = x;
            ans = query(i, j);
            sum += -2*stk[lidx[ans.nd]].dp+stk[i].dp+stk[j].dp;
        }
        printf("%d\n", sum);
        for(i = 0; i <= size; i++)
            g[i].clear();
    }
    return 0;
}

我要檢舉
#b237#CSAPC'09#迷宮任務
台長： Morris

您可能對以下文章有興趣

人氣(1,103) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ITSA] 18th 總解答
此分類上一篇:[ZJ][dp] b220. 5. 蛋糕師傅的煩惱

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文