There is a square area of size N*N, where h[i][j] represents the elevation at the grid location with coordinates (i, j).
The engineering team wants to lay a pathway from the top-left corner (1, 1) to the area's bottom-right corner (N, N). The pathway can be seen as a route within the area that moves up, down, left, or right from the top-left corner to the bottom-right corner.
Considering the safety of pedestrians on the pathway, it is important to pay attention to the elevation difference between each step of the path. The goal is to establish a pathway with the minimum possible maximum elevation difference between any two consecutive steps.
Please output the minimum value of the maximum elevation difference for the proposed path, as well as the length of the shortest path under that maximum elevation difference condition.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains a number N (1 ≤ N ≤ 300), representing the size of the area. The following N lines each contain N positive integers, where each integer h[i][j] (1 ≤ h[i][j] ≤ 10^6 ) represents the elevation at that specific location. | Output two lines:
The first line should output the minimum value of the maximum height difference in the paving plan. The second line should output the shortest path length from the top-left to the bottom-right corner under that maximum height difference. |
| 4 9 4 3 2 5 9 8 10 3 3 2 8 6 3 3 4 | 4 6 |
Thought Process
Use BFS to traverse the map. First, declare a two-dimensional array where all elements are initially set to 99999. After running BFS, the value at array[N-1][N-1] will be the answer.
When running BFS, if a point is determined to be walkable, first check if the array value at that position is higher than the current height difference. If it is, store the current position as the starting point for the next iteration.
Sample Code－ZeroJudge J125: Building Roads
#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