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

子任務

20% : \(R = 1, M = 1\)
30% : \(R = 1\)
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]

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