j125: 4. 蓋步道

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;
}

相關文章

分享此文：