# APCS 20221023 題解

## 第一題：巴士站牌 [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=i428)
* 此題只需邊輸入邊用abs取相鄰兩站之間的距離，然後找出最大值和最小值即可(Example 1)
* 一開始我看成要找出每個站之間的距離才用以下的辦法(用pair <int, int> p[] 存座標) (Example 2)
* #還以為第一題難度什麼時候(進步)那麼快
:::spoiler Example 1

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

int main() {
  int n, x, y, px, py, Max = -INT_MAX, Min = INT_MAX;
  cin >> n >> px >> py;
  for(int i=0; i<n-1; i++){
    cin >> x >> y;
    int dis = abs(x - px) + abs(y - py);
    Max = max(Max, dis);
    Min = min(Min, dis);
    px = x, py = y;
  }
  cout << Max << ' ' << Min;
}

:::
:::spoiler Example 2

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

int main() {
  pair <int, int> p[10000];
  vector <int> save;
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> p[i].first >> p[i].second;
  }
  for(int i=0; i<n-1; i++){
    save.push_back(abs(p[i].first - p[i+1].first) + abs(p[i].second - p[i+1].second));
  }
  cout << *max_element(save.begin(), save.end()) << ' ' << *min_element(save.begin(), save.end());
}

:::

## 第二題：運貨站 [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=j123)
* now[] 用來記錄每一列當前的長度
:::spoiler Example

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

int now[35];
int r, c, n, place, ans1 = 0, ans2 = 0; //ans1:進倉庫的格子數 ans2:進倉庫貨物數量
char box;

void A(int x){
  int Max = -1;
  for(int i=x; i<=x+3; i++) Max = max(Max, now[i]);
  if(Max + 1 < c){
    ans1 += 4;
    ans2++;
    for(int i=x; i<=x+3; i++) now[i] = Max + 1;
  }
}
void B(int x){
  if(now[x] + 3 < c) {
    ans1 += 3;
    ans2++;
    now[x] += 3;
  }
}
void C(int x){
  int Max = max(now[x], now[x+1]);
  if(Max + 2 < c){
    ans1 += 4;
    ans2++;
    for(int i=x; i<=x+1; i++) now[i] = Max + 2;
  }
}
void D(int x){
  if(now[x] + 1 < c && now[x+1] + 3 < c) {
    ans1 += 4;
    ans2++;
    if(now[x] + 1 >= now[x+1] + 3 ){
      now[x]++;
      now[x+1] = now[x];
    }
    else{
      now[x+1] += 3;
      now[x] = now[x+1];
    }
  }
}
void E(int x){
  if(now[x] + 1 < c && now[x+1] + 2 < c && now[x+2] + 2 < c) {
    ans1 += 5;
    ans2++;
    if(now[x] + 1 >= now[x+1] + 2 && now[x] + 1 >= now[x+2] + 2){
      now[x]++;
      now[x+1] = now[x];
      now[x+2] = now[x];
    }
    else if(now[x+1] + 2 >= now[x] + 1 && now[x+1] + 2 >= now[x+2] + 2){
      now[x+1] += 2;
      now[x] = now[x+1];
      now[x+2] = now[x+1];
    }
    else{
      now[x+2] += 2;
      now[x] = now[x+2];
      now[x+1] = now[x+2];
    }
  }
}
int main() {
  memset(now, -1, sizeof(now));
  cin >> r >> c >> n;
  for(int i=0; i<n; i++){
    cin >> box >> place;
    if(box == 'A') A(place);
    else if(box == 'B') B(place);
    else if(box == 'C') C(place);
    else if(box == 'D') D(place);
    else if(box == 'E') E(place);
  }
  cout << r*c - ans1 << ' ' << n - ans2;
}

:::
## 第三題：石窟探險[（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=j124)
* 直接用題目已經跑完整個樹的節點來做DFS (Example 1)
* * 先整理題目用stack做一個樹，再做DFS遍歷 (較為複雜) (Example 2)
:::spoiler Example 1

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

vector <ll> v;
ll n, now = 0, ans = 0;

ll DFS(){
  ll next, t = v[now++];
  if(t){
    for(int i=0; i<2 + (t%2) ? 1 : 0; i++){
      next = DFS();
      if(next) ans += abs(t - next);
    }
    return t;
  }
  else return 0;
}

int main() {
  while(cin >> n) v.push_back(n);
  DFS();
  cout << ans;
}

:::
:::spoiler Example 2

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

ll a, root = 0, ans = 0;
stack <ll> pre;
vector <ll> v[100005];

bool check(){
  if(pre.top() % 2 && v[pre.top()].size() == 3) return true;
  else if(pre.top() % 2 == 0 && v[pre.top()].size() == 2) return true;
  else return false;
}

void dfs(ll x){
  for(int i=0; i<v[x].size(); i++){
    if(v[x][i] != 0){
      ans += abs(x - v[x][i]);
      dfs(v[x][i]);
    }
  }
}

int main() {
  cin >> a;
  root = a;
  pre.push(a);
  while(cin >> a){
    v[pre.top()].push_back(a);
    if(a != 0){
      pre.push(a);
    }
    else{
      while(check()){
        pre.pop();
        if(pre.size() == 0) break;
      }
    }
  }
  dfs(root);
  cout << ans;
}

:::

## 第四題： 蓋步道[（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=j125)
* 二分搜高度
* 用BFS來驗證是否能到終點以及到終點的最短距離
:::spoiler Example

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

int n, arr[350][350] , bfs[350][350];
int ans1 = 0, ans2 = 0;

int BFS(int x){
  int sx = 1, sy = 1, Max = -1;
  queue <pair<int, int>> q;
  q.push({sx, sy});
  while(q.size()){
    int a = q.front().first;
    int b = q.front().second;
    q.pop();
    if(bfs[a+1][b] == 0 && abs(arr[a+1][b] - arr[a][b]) <= x){
      Max = max(Max, abs(arr[a+1][b] - arr[a][b]));
      q.push({a+1, b});
      bfs[a+1][b] = bfs[a][b] + 1;
    }
    if(bfs[a][b+1] == 0 && abs(arr[a][b+1] - arr[a][b]) <= x){
      Max = max(Max, abs(arr[a][b+1] - arr[a][b]));
      q.push({a, b+1});
      bfs[a][b+1] = bfs[a][b] + 1;
    }
    if(bfs[a-1][b] == 0 && abs(arr[a-1][b] - arr[a][b]) <= x){
      Max = max(Max, abs(arr[a-1][b] - arr[a][b]));
      q.push({a-1, b});
      bfs[a-1][b] = bfs[a][b] + 1;
    }
    if(bfs[a][b-1] == 0 && abs(arr[a][b-1] - arr[a][b]) <= x){
      Max = max(Max, abs(arr[a][b-1] - arr[a][b]));
      q.push({a, b-1});
      bfs[a][b-1] = bfs[a][b] + 1;
    }
  }
  if(bfs[n][n] != 0) {
    ans1 = Max;
    ans2 = bfs[n][n] - 1;
    return 1;
  }
  else return 0;
}

void reset(){
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      bfs[i][j] = 0;
    }
  }
}

int main() {
  cin >> n;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      cin >> arr[i][j];
    }
  }
  int L = 0, R = 1000000;
  while(L < R - 1){
    memset(bfs, -1, sizeof(bfs));
    reset();
    bfs[1][1] = 1;
    int M = (L + R) / 2;
    if(BFS(M) == 0) L = M;
    else R = M;
  }
  cout << ans1 << '\n' << ans2;
}

:::