j125 - 4. 蓋步道
題目描述
題目要求在一個 $n \times n$ 的網格中，從左上角 $(1, 1)$ 到右下角 $(n, n)$ 鋪設一條步道，使得步道上的最大高度差最小，並在最小高度差的前提下，找到最短路徑長度。步道只能沿著上下左右四個方向移動。
解題思路
本題可以將網格視為一個圖，每個格子是一個節點，相鄰格子之間存在邊，邊的權重是兩個格子高度的絕對差。題目要求找到一條從起點到終點的路徑，使得該路徑上的最大邊權最小，並且路徑長度最短。
解題思路是使用二分搜來確定最大高度差的最小值。對於每個二分搜的 mid 值，使用廣度優先搜尋 (BFS) 來判斷是否存在一條路徑，使得路徑上的最大高度差不超過 mid。如果存在這樣的路徑，則說明最大高度差的最小值可能更小，更新右界；否則，說明最大高度差的最小值可能更大，更新左界。
找到最大高度差的最小值後，再次使用 BFS 找到在該高度差限制下的最短路徑長度。
複雜度分析
- 時間複雜度: O(n^2 * log(max_height) + n^4)，其中 n 是網格的大小，max_height 是網格中最大高度。二分搜的複雜度是 O(log(max_height))，每次二分搜需要進行一次 BFS，BFS 的複雜度是 O(n^4) (最壞情況下需要遍歷所有節點和邊)。
- 空間複雜度: O(n^2)，主要用於存儲圖的鄰接表和 BFS 的隊列。
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[100001],ma,ans;
bool has[100001];
vector <pair <ll,ll>> te[100001];//go v
bool ok(ll m){
if(te[n*n-1][0].second>m&&te[n*n-1][1].second>m)return 0;
memset(has,0,sizeof(has));
queue <pair <ll,ll>> q;
q.push({0,0});
while(!q.empty()){
ll tp=q.front().first,dis=q.front().second;
q.pop();
if(has[tp])continue;
has[tp]=1;
if(tp==n*n-1){
ans=dis;
break;
}
for(int i=0;i<te[tp].size();++i){
if(te[tp][i].second>m||has[te[tp][i].first])continue;
q.push({te[tp][i].first,dis+1});
}
}
if(!has[n*n-1])return 0;
return 1;
}
ll BS(ll l,ll r){
for(;l<=r;){
ll mid=(l+r)/2;
ok(mid)?r=mid-1:l=mid+1;
}
return l;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
if(n==1){
cout << "0\n0";
return 0;
}
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
cin >> a[i*n+j];
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
ll v=i*n+j;
ma=max(ma,a[v]);
if((v+1)%n)te[v].push_back({v+1,abs(a[v]-a[v+1])});
if((v-1+n)%n!=n-1)te[v].push_back({v-1,abs(a[v]-a[v-1])});
if(v+n<n*n)te[v].push_back({v+n,abs(a[v]-a[v+n])});
if(v-n>=0)te[v].push_back({v-n,abs(a[v]-a[v-n])});
}
}
ll ac=BS(0,ma);
ok(ac);
cout << ac << "\n" << ans;
}