Algoogle

Algorithm for Programming Contest

PKU 2110 Mountain Walking

Category: PKU Tag: dijkstra

Mountain Walking

問題概要


N*Nの高さのテーブルが与えられる
左上から右下まで高低差が最小になるように移動したい
その最小値を求めよ

解法


予め下限を決めてから高さの最大を小さくするようにDijkstraする.
下限を0から開始地点(もしくは到着地点)のあいだ全て試す.

コード


(2110.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct S{
    int i, j, h;
    S(int i, int j, int h):i(i),j(j),h(h){}
    bool operator<(const S &s) const{ return h > s.h;}
};

const int di[] = {-1,1,0,0};
const int dj[] = {0,0,-1,1};
int N, ans;
int field[128][128];
int low[128][128];

inline bool in(int i, int j){ return i >= 0 && j >= 0 && i < N && j < N;}

#include <iostream>

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            scanf("%d", &field[i][j]);
    ans = 128;
    for(int t = min(field[0][0], field[N-1][N-1]); t >= 0; t--){
        priority_queue<S> que;
        que.push(S(0,0,field[0][0]));
        memset(low, -1, sizeof(low));
        while(!que.empty()){
            S s = que.top(); que.pop();
            if(low[s.i][s.j] >= 0) continue;
            low[s.i][s.j] = s.h;
            for(int d = 0; d < 4; d++){
                int ni = s.i + di[d], nj = s.j + dj[d];
                if(in(ni,nj) && field[ni][nj] >= t)
                    que.push(S(ni,nj,max(s.h, field[ni][nj])));
            }
        }
        if(low[N-1][N-1] >= 0) ans = min(ans, low[N-1][N-1]-t);
    }
    printf("%d\n", ans);
    return 0;
}

Comments