人口遷移

解題想法

1. 函式和變數設定

在此題目解釋前,我們要先做好前置作業,即函式和變數的設定,以下是對此題目所設定的變數和函式:

1. 變數

int r, c, k, m, ans_min = INT_MAX, ans_max = INT_MIN;
int upd[55][55], now[55][55];
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

以上三行各代表這些變數:

  1. 題目敘述變數 ( r,c,k,mr, c, k, m )、最小答案最大答案
  2. 兩個大小為 55×5555 \times 55 的二維陣列,代表更新值目前狀態
  3. 一個大小為 4×24 \times 2 的二維陣列,代表移動變化量
補充

我們利用 dir[4][2] 來代表移動變化量,主要目的是使我們能簡易地閱讀程式碼,以便快速偵錯:

for (int i = 0; i < 4; i++) {
	int new_x = pre_x + dir[i][0], new_y = pre_y + dir[i][1];
}

2. 函式

bool in_range(int x, int y, int tarx, int tary) {
	return x >= 1 && x <= tarx && y >= 1 && y <= tary;
}

以上函式 in_range() ,主要功用為簡化程式碼,讓複雜的檢測程式簡化為統一的函式。其函式主要回傳一個由四個 AND 判斷式組成的布林值,只要其中一個不成立,則全部不成立。

2. 模擬

此題最重要的一環就是模擬,以程式來模擬人口移動,因此我們可以將此題目分成三個步驟:

  1. 計算人口移動。
  2. 將人口值預先放置。
  3. 更新人口 / 清除預先值。

以下為示意圖:

alt text alt text alt text

這三個步驟可以由一個 while 迴圈來表示:

while (m--) {
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (now[i][j] == -1) continue;
            for (int p = 0; p < 4; p++) {
                int new_x = i + dir[p][0], new_y = j + dir[p][1];
                if (in_range(new_x, new_y, r, c) && now[new_x][new_y] != -1) {
                    upd[new_x][new_y] += now[i][j] / k;
                    upd[i][j] -= now[i][j] / k;
                }
            }
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            now[i][j] += upd[i][j];
            upd[i][j] = 0;
        }
    }
}
注意

題目敘述中有提到,值為 1-1 的土地需要跳過,務必記住哦!

3. 計算答案

題目要求我們輸出模擬完後的最大值和最小值,因此可以將先前設定的 ans_minINT_MAXans_maxINT_MIN ,最後再找出答案:

for (int i = 1; i <= r; i++) {
    for (int j = 1; j <= c; j++) {
        if (now[i][j] != -1) {
            ans_min = min(ans_min, now[i][j]);
            ans_max = max(ans_max, now[i][j]);
        }
    }
}

範例程式

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

int r, c, k, m, ans_min = INT_MAX, ans_max = INT_MIN;
int upd[55][55], now[55][55];
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

bool in_range(int x, int y, int tarx, int tary) {
    return x >= 1 && x <= tarx && y >= 1 && y <= tary;
}

int main() {
    memset(upd, 0, sizeof(upd));
    cin >> r >> c >> k >> m;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> now[i][j];
        }
    }
    while (m--) {
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                if (now[i][j] == -1) continue;
                for (int p = 0; p < 4; p++) {
                    int new_x = i + dir[p][0], new_y = j + dir[p][1];
                    if (in_range(new_x, new_y, r, c) && now[new_x][new_y] != -1) {
                        upd[new_x][new_y] += now[i][j] / k;
                        upd[i][j] -= now[i][j] / k;
                    }
                }
            }
        }
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                now[i][j] += upd[i][j];
                upd[i][j] = 0;
            }
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (now[i][j] != -1) {
                ans_min = min(ans_min, now[i][j]);
                ans_max = max(ans_max, now[i][j]);
            }
        }
    }
    cout << ans_min << '\n' << ans_max << '\n';
    return 0;
}