APCS 109/10 實作題第二題 題解

2020-10-21 17:11:01 by Akira

題目敘述

有個 \(R \times C\) 的矩陣,每格有個整數代表該區域的人數,如果是 -1 的話則代表該區域不能住人。每天過後每格會向其上下左右四個相鄰格子遷移其 \(K\) 分之一的人口(無條件捨去),如果該方向相鄰格子不存在或無法住人則跳過。問 \(M\) 天後所有可住人格子的最小值及最大值。

\[ \begin{bmatrix} 77 & 69 & 23 \\ -1 & 82 & 50 \end{bmatrix} \]

以上圖為例,若 \(K=4\),則一天後矩陣會變成:

\[ \begin{bmatrix} 75 & 62 & 42 \\ -1 & 71 & 51 \end{bmatrix} \]

輸入格式

第一行有四個整數 \(R, C, K, M\)
接下來有 \(R\) 行 每行 \(C\) 個整數 \(A_{i,j}\) 代表各區域的人數

\(1 \le R, C, M \le 50\) ; \(4 \le K \le 50\) ; \(-1 \le A_{i,j}\)
保證過程中所有區域人數都少於 \(2^{31}\) 且至少有一個可住人的區域

輸出格式

印出兩行分別為 \(M\) 天後人數最少與人數最多的可住人區域的人數

範例輸入

2 3 4 1
77 69 23
-1 82 50

範例輸出

42
75

子任務

  1. 20% : \(R = 1, M = 1\)
  2. 30% : \(R = 1\)
  3. 50% : 無限制

題解

影片

C++ 參考解答

#include <iostream>
using namespace std;

int A[52][52], B[52][52];

void f(int d, int &x, int &y) {
  if (y >= 0) {
    x -= d;
    y += d;
  }
}

int main() {
  int R, C, K, M;
  cin >> R >> C >> K >> M;
  for (int i = 0; i <= R + 1; i++) {
    for (int j = 0; j <= C + 1; j++) {
      A[i][j] = -1;
    }
  }
  for (int i = 1; i <= R; i++) {
    for (int j = 1; j <= C; j++) {
      cin >> A[i][j];
    }
  }
  for (; M > 0; M--) {
    for (int i = 0; i <= R + 1; i++) {
      for (int j = 0; j <= C + 1; j++) {
        B[i][j] = A[i][j];
      }
    }
    for (int i = 1; i <= R; i++) {
      for (int j = 1; j <= C; j++) {
        if (A[i][j] < 0) continue;
        int d = B[i][j] / K;
        f(d, A[i][j], A[i - 1][j]);
        f(d, A[i][j], A[i + 1][j]);
        f(d, A[i][j], A[i][j - 1]);
        f(d, A[i][j], A[i][j + 1]);
      }
    }
  }
  int mi = -1, ma = -1;
  for (int i = 1; i <= R; i++) {
    for (int j = 1; j <= C; j++) {
      if (A[i][j] >= 0) {
        if (mi < 0 || A[i][j] < mi) mi = A[i][j];
        if (ma < 0 || A[i][j] > ma) ma = A[i][j];
      }
    }
  }
  cout << mi << endl;
  cout << ma << endl;
  return 0;
}

[題解] [APCS] [APCS 109/10]