🔗 UVA-10443 Rock, Scissors, Paper

tags: `模擬(Simulation)`

C++ 範例程式碼已於 UVA、瘋狂程設(CPE) 上測試通過。
Python 範例程式碼僅可通過 瘋狂程設(CPE) 上的測資。

題意

給定一個大小為 $r \times c$ $r \times c$ 的地圖，地圖上的每個格子上有 R、S、P 三種字元，分別代表 Rock、Scissors、Paper。每天，每個格子上的字元會根據周圍四個格子的字元變化，變化規則如下：
- 如果周圍有 Rock，且自己是 Scissors，則自己變成 Rock
- 如果周圍有 Scissors，且自己是 Paper，則自己變成 Scissors
- 如果周圍有 Paper，且自己是 Rock，則自己變成 Paper
給定一個整數 $n$ 代表天數，請求出 $n$ 天後的地圖。

思路：模擬(Simulation)

用一個二維陣列 $mp$ 來存放地圖上的字元，用一個二維陣列 $tmp$ 來存放每天變化後的地圖，直接模擬每天的變化即可。
由於一個格子可能會同時被其他格子影響、和影響其他格子，因此需要先將每天變化後的地圖存放在 $tmp$ 中，等到處理完今天所有格子的變化後，再將 $tmp$ 複製到 $mp$ 中。
時間複雜度： $O(n \cdot r \cdot c)$ ，對於每次詢問。
空間複雜度： $O(r \cdot c)$ 。

Python 範例程式碼僅能通過 瘋狂程設(CPE) 上的測資，在 UVA 上會 TLE

T = int(input())

for tc in range(T):
	r, c, n = map(int, input().split())
	mp = [list(input()) for _ in range(r)] # map
	tmp = [[-1 for _ in range(c)] for _ in range(r)] # temp map
	for d in range(n): # days
		for i in range(r):
			for j in range(c):
				tmp[i][j] = mp[i][j]
		for i in range(r):
			for j in range(c):
				for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
					if x < 0 or x >= r or y < 0 or y >= c:
						continue
					if mp[x][y] == "R" and mp[i][j] == "S":
						tmp[i][j] = "R"
					if mp[x][y] == "S" and mp[i][j] == "P":
						tmp[i][j] = "S"
					if mp[x][y] == "P" and mp[i][j] == "R":
						tmp[i][j] = "P"
		for i in range(r): # update
			for j in range(c):
				mp[i][j] = tmp[i][j]
	for row in mp:
		print("".join(row))
	if tc < T - 1:
		print()

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
#define endl '\n'

char mp[N][N], tmp[N][N];

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int t, r, c, n;
	cin >> t;
	int DIR[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	while (t--) {
		cin >> r >> c >> n;
		for (int i = 0; i < r; ++i) {
			for (int j = 0; j < c; ++j) {
				cin >> mp[i][j];
			}
		}
		while (n--) { // each day
			for (int i = 0; i < r; ++i) { // copy
				for (int j = 0; j < c; ++j) {
					tmp[i][j] = mp[i][j];
				}
			}
			for (int i = 0; i < r; ++i) {
				for (int j = 0; j < c; ++j) {
					for (int k = 0; k < 4; ++k) {
						int x = i + DIR[k][0], y = j + DIR[k][1];
						if (x < 0 || x >= r || y < 0 || y >= c) continue; // out of range
						if (mp[x][y] == 'R' && mp[i][j] == 'S') tmp[i][j] = 'R';
						if (mp[x][y] == 'S' && mp[i][j] == 'P') tmp[i][j] = 'S';
						if (mp[x][y] == 'P' && mp[i][j] == 'R') tmp[i][j] = 'P';
					}
				}
			}
			for (int i = 0; i < r; ++i) { // update
				for (int j = 0; j < c; ++j) {
					mp[i][j] = tmp[i][j];
				}
			}
		}
		for (int i = 0; i < r; ++i) { // output
			for (int j = 0; j < c; ++j) {
				cout << mp[i][j];
			}
			cout << endl;
		}
		if (t) cout << endl;
	}
	return 0;
}