ZeroJudge J125: 蓋步道

有一個大小為 N×N 的方形區域，h[i][j] 代表位於座標 (i, j) 的格子該處的海拔高度。

工程團隊想要從該區域的左上角 (1, 1) 鋪設一條步道到右下角 (N, N)，鋪設的步道可以視為在該區域內上下左右四個方向從左上角走到右下角的一條路徑。

考量到行人在步道上行走的安全，必須要注意步道每一步之間的高低落差，並希望可以建立出一個最大高度差最小的步道鋪設方案。

請輸出該鋪設方案最大高度差的最小值和在該最大高度差的前提下步道的最短路徑長度。

範例測資

範例輸入範例輸出
第一行為一個數字 N (1 ≤ N ≤ 300)，代表該區域的大小。接下來有 N 行，第 i 行有 N 個正整數，每一個正整數 h[i][j] (1 ≤ h[i][j] ≤ 106) 代表該位置的海拔高度。輸出兩行，第一行輸出鋪設方案中最大高度差的最小值，第二行輸出在該最大高度差下從左上走到右下的最短路徑長度。
4
9 4 3 2
5 9 8 10
3 3 2 8
6 3 3 4		4
6
ZeroJudge J125 範例測資

解題思路

使用 BFS 來跑地圖，先宣告一個二維陣列裡面都是預設 99999，陣列的[N-1][N-1] 在跑完 BFS 之後就會是答案。

在跑 BFS 時，如果判斷到一個點可以繼續走，則先判斷該位置的陣列值是否比現在的高度差還要高，如果是的話就將跑到的位置存到下一次的起點。

範例程式碼－ZeroJudge J125: 蓋步道

#include <iostream>
#include <vector>
using namespace std;

int N, road[500][500] = {}, loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, height[500][500] = {}, step = 0;

void BFS(const vector<pair<int, int>>start, const int count) {
    if (start.size() == 0) return;
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++) {
        const int y = start[i].first, x = start[i].second;
        if (y == N-1 && x == N-1) step = count;
        for (int j = 0; j<4; j++) {
            const int yy = y + loc[j][0], xx = x + loc[j][1];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                const int calc = abs(road[y][x] - road[yy][xx]);
                if (max(height[y][x], calc) < height[yy][xx]) {
                    height[yy][xx] = max(height[y][x], calc);
                    newStart.push_back(make_pair(yy, xx));
                }
            }
        }
    }
    BFS(newStart, count+1);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i<N; i++) {
        for (int j = 0; j<N; j++) {
            cin >> road[i][j];
            height[i][j] = 99999999;
        }
    }
    height[0][0] = 0;
    vector<pair<int, int>>start;
    start.push_back(make_pair(0, 0));
    BFS(start, 0);
    cout << height[N-1][N-1] << "\n" << step << "\n";
}

//ZeroJudge J125
//Dr. SeanXD
標籤

相關文章

發佈留言