APCS 20230604 題解

第一題：路徑偵測 （題目敘述）

• 解法1 : 用內積 & 外積決定方向
• 解法2 : 用很多個if暴力解

Example1

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

int main() {
  // vec 為向量，dot為內積，cross為外積的z項
  int n, x[105] = {0}, y[105] = {0}, vec_x[105], vec_y[105];
  int l = 0, r = 0, turn = 0;
  cin >> n;
  for(int i=1; i<=n; i++) cin >> x[i] >> y[i];
  for(int i=1; i<=n; i++) {
    vec_x[i] = x[i] - x[i-1];
    vec_y[i] = y[i] - y[i-1];
  } 
  
  for(int i=1; i<n; i++){
    int dot = vec_x[i]*vec_x[i+1] + vec_y[i]*vec_y[i+1];
    if(dot < 0) turn++;
    else if(dot == 0){
      int cross = vec_x[i]*vec_y[i+1] - vec_x[i+1]*vec_y[i];
      if(cross > 0) l++;
      else r++;
    }
  }
  cout << l << ' ' << r << ' ' << turn;
}

Example2

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

int main() {
  int n, pre_x, pre_y, x, y, l = 0, r = 0, turn = 0;
  int dir = 4;//1北 2南 3西 4東
  cin >> n >> pre_x >> pre_y;
  for(int i=1; i<n; i++){
    cin >> x >> y;
    // del_x & del_y 為坐標變化量
    int del_x = x - pre_x, del_y = y - pre_y;
    //原本朝北
    if(dir == 1){
      //x變化為正，右轉向東
      if(del_x > 0){
        r++, dir = 4;
      }
      //x變化為負，左轉向西
      else if(del_x < 0){
        l++, dir = 3;
      }
      //y變化為負，迴轉向南
      else if(del_y < 0){
        turn++, dir = 2; 
      }
      //y變化為正，繼續直行
    }
      
    //原本朝南
    else if(dir == 2){
      //x變化為負，右轉向西
      if(del_x < 0){
        r++, dir = 3;
      }
      //x變化為正，左轉向東
      else if(del_x > 0){
        l++, dir = 4;
      }
      //y變化為正，迴轉向北
      else if(del_y > 0){
        turn++, dir = 1; 
      }
      //y變化為負，繼續直行
    }

    //原本朝西
    else if(dir == 3){
      //y變化為正，右轉向北
      if(del_y > 0){
        r++, dir = 1;
      }
      //y變化為負，左轉向南
      else if(del_y < 0){
        l++, dir = 2;
      }
      //x變化為正，迴轉向東
      else if(del_x > 0){
        turn++, dir = 4; 
      }
      //x變化為負，繼續直行
    }
      
    //原本朝東
    else if(dir == 4){
      //y變化為負，右轉向南
      if(del_y < 0){
        r++, dir = 2;
      }
      //y變化為正，左轉向北
      else if(del_y > 0){
        l++, dir = 1;
      }
      //x變化為負，迴轉向西
      else if(del_x < 0){
        turn++, dir = 3; 
      }
      //x變化為正，繼續直行
    }
    pre_x = x, pre_y = y;
  }
  cout << l << ' ' << r << ' ' << turn;
}

第二題：特殊位置 （題目敘述）

• 加總以arr[i][j]為中心(令值為num）
• 從(i-num ~ i+num）和(j-num ~ j+num）檢查距離是否 <= num

Example

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

int main() {
  int n, m, arr[100][100], ans[100][100];
  int x[10005] = {0}, y[10005] = {0}, cnt = 0;
  cin >> n >> m;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin >> arr[i][j];
      ans[i][j] = 0;
    }
  }
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      int num = arr[i][j];
      for(int a=num*(-1); a<=num; a++){
        for(int b=num*(-1); b<=num; b++){
          if(i+a >= 0 && i+a < n && j+b >=0 && j+b < m){
            if(abs(a) + abs(b) <= num){
              ans[i][j] += arr[i+a][j+b];
            }
          }
        }
      }
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(arr[i][j] == ans[i][j] % 10){
        x[cnt] = i, y[cnt] = j;
        cnt++;
      }
    }
  }
  cout << cnt << '\n';
  for(int i=0; i<cnt; i++){
    cout << x[i] << ' ' << y[i] << '\n';
  }
}

第三題：磁軌移動序列 （題目敘述）

• 我還沒寫

Example

第四題：開啟寶盒 （題目敘述）

• 我還沒寫

Example