# APCS 2022 10月 實作題

## 第一題 巴士站牌
#### 題目: [https://zerojudge.tw/ShowProblem?problemid=i428](https://zerojudge.tw/ShowProblem?problemid=i428)

#### 解題關鍵: 迴圈、abs()

#### 程式碼

#include<bits/stdc++.h>
using namespace std;

int n, Min = 999999, Max = -1;
vector<pair<int, int> > road;

int main(){
    //輸入
    cin>>n;
    road.resize(n);
    for(int i=0; i<n; i++){
        int x, y;
        cin>>x>>y;
        road[i] = {x, y};
    }
    
    for(int i=1; i<n; i++){
        int l = abs(road[i].first - road[i-1].first) + abs(road[i].second - road[i-1].second);
        Min = min(Min, l);
        Max = max(Max, l);
    }
    cout<<Max<<' '<<Min<<'\n';
}

## 第二題
#### 題目: [https://zerojudge.tw/ShowProblem?problemid=j123](https://zerojudge.tw/ShowProblem?problemid=j123)

#### 題解: 待補
#### 程式碼

## 第三題 石窟探險
##### 題目: [https://zerojudge.tw/ShowProblem?problemid=j124](https://zerojudge.tw/ShowProblem?problemid=j124)

#### 題解關鍵: *奇數 -> 3個子節點, 偶數 -> 2個子節點* 、遞迴

#### 程式碼

#include<bits/stdc++.h>
using namespace std;

int inx = 0;
string str;
vector<int> node;
long long sum;

void build(int n){  // n = 父節點
  if(n%2==0){
    for(int i=1; i<=2; i++){
      int nm = node[inx];
      inx++;
      if(nm == 0) continue;
      sum += abs(n - nm);
      build(nm);
    }
  }else{
    for(int i=1; i<=3; i++){
      int nm = node[inx];
      inx++;
      if(nm == 0) continue;
      sum += abs(n - nm);
      build(nm);
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  getline(cin, str);
  stringstream ss;
  ss<<str;
  while(ss>>str){
    node.push_back(stoi(str));
  }
  inx = 1;
  build(node[0]);
  cout<<sum<<'\n';
}

## 第四題 蓋步道
#### 題目: [https://zerojudge.tw/ShowProblem?problemid=j125](https://zerojudge.tw/ShowProblem?problemid=j125)

#### 題解1: BFS + 二分搜
使用二分搜嘗試每種高度h，再用BFS找嘗試h是否可行。

#### 程式碼

#include<bits/stdc++.h>
using namespace std;

int n, ans; // n:長與寬
int g[305][305]; //圖
int dx[4] = {0, 0, 1, -1}; //x方向 
int dy[4] = {1, -1, 0, 0}; //y方向

// 走訪
bool bfs(int h){
    queue<vector<int>> qu;
    qu.push({1, 1, 0});
    bool vis[305][305] = {0};
    
    while(!qu.empty()){
        int x = qu.front()[0], y = qu.front()[1], dis = qu.front()[2];
        qu.pop();
        vis[x][y] = true;
        
        if(x == n && y == n){
            ans = dis;
            return true;
        }
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(1<=nx && nx<=n && 1<=ny && ny<=n && vis[nx][ny] == false){
                if(abs(g[x][y] - g[nx][ny]) <= h){
                    vis[nx][ny] = true;
                    qu.push({nx, ny, dis+1});
                } 
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    //輸入
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>g[i][j];
        }
    }
    
    //r值是最小高度
    int l = -1, r = 1e6;
	
    // 二分搜
    while(r-l > 1){
        int mid = (r+l)/2;
        if(bfs(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }

    cout<<r<<'\n'<<ans<<'\n';
    return 0;
}

###### tags: `APCS`