2022.11.30 PM 04:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=j125 出題者 : 2022年10月APCS 標籤 : bfs、二分搜、最短路 難易度 : 5
解題想法 : 題目要求了兩個輸出值, 第一項 : 每條路高度差的最小值 第二項 : 滿足第一項的最佳解所花的路徑長 因此實作上應先計算出第一項得出最佳解後,再去計算當此條路為最佳解時,最短的路徑長度。 第一項的實作方式是使用二分搜+bfs,二分搜要搜什麼呢?要搜的是高度差,每次走訪會有兩種情形 : 1. 在不超過此高度差的情況下,無法出現一條從(0,0) ~ (n-1,n-1) 的路徑。 2. 在不超過此高度差的情況下,可以有至少一條路徑從(0,0) ~ (n-1,n-1)。 不難發現當高度差為m時若成功的出現至少一條路,則比m大的高度差也必能成功(高度差允許的更寬鬆),反之,當高度差為m時失敗了,則比m更小的高度差也不可能成功,依照範例測資的話,實作上可能會像下表: 高度差 1 2 3 4 5 6 7 8 9 10 是否成功 X X X O O O O O O O 會發現第一個滿足條件的是4,因此高度差最小值為4。 再來只要再走一次bfs,並規定高度差為4,即可算出當滿足最小高度差時所需要的路徑長。 ※注意 : 每次二分搜之前要把上一次儲存的資訊全部清空,包括最後一次算路徑長的bfs之前都要清(筆者實作上定義了一個clean()的函式)
//C++ language
#include<iostream>
#include<queue> //queue
#include<tuple> //tuple
#include<cstring> //memset()
#define int long long
using namespace std;
int min_high=1e9,n;
int area[305][305]={0};
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool inrange(int x,int y){
return x>=0 && x<n && y>=0 && y<n;
}
queue<tuple<int,int,int>>q;
int visited[305][305]={0};
int bfs(int m){
q.push({0,0,0});
visited[0][0]=1;
while(!q.empty()){
int x=get<0>(q.front());
int y=get<1>(q.front());
int step=get<2>(q.front());
visited[x][y]=1;
q.pop();
if(x==n-1 && y==n-1){
return step; //true
}
for(int i=0;i<4;i++){
int newx=x+dir[i][0];
int newy=y+dir[i][1];
if(inrange(newx,newy) && !visited[newx][newy]){
int high=abs(area[x][y]-area[newx][newy]);
if(high<=m){
visited[newx][newy]=1;
q.push({newx,newy,step+1});
}
}
}
}
return -1; //false
}
void init(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>area[i][j];
}
}
}
void clean(){
while(!q.empty())q.pop();
memset(visited,0,sizeof(visited));
}
signed main()
{
init();
int L=0,R=1e7,ans=1e9;
while(R-L>1){
int m=L+(R-L)/2;
clean();
int step=bfs(m);
if(step!=-1){
R=m;
}
else L=m;
}
clean();
cout<<R<<"\n"<<bfs(R)<<"\n";
return 0;
}
