學校課程/平行程式

批改娘 10086. Red/Blue Computation

contents

  1. 1. 題目描述
  2. 2. 輸入格式
  3. 3. 輸出格式
  4. 4. 範例輸入
  5. 5. 範例輸出
  6. 6. 備註
  7. 7. Solution

題目描述

模擬工作流程，在一個 $N \times N$ 的網格 (左邊界可以通到右邊界，上邊界可以通到下邊界) 上有三種狀態紅 $R$, 藍 $B$, 空格 $W$，每次模擬分成兩個步驟

  • 第一步，只有紅 $R$ 可移動，紅 $R$ 只能往右移動一格到空白 $W$ 的位置，否則仍在原處。
  • 第二步，只有藍 $B$ 可移動，藍 $B$ 只能往下移動一格到空白 $W$ 的位置，否則仍在原處。

請問模擬 $M$ 次後盤面為何？

輸入格式

輸入只有一組測資，第一行有兩個整數 $N, \; M$，分別為盤面大小以及模擬次數。接下來會有 $N$ 行，每一行上會有 $N$ 個字元。

  • $1 \le N, M \le 1000$

輸出格式

輸出 $N \times N$ 盤面。

範例輸入

1
2
3
4
5
4 1
RRWR
WWBW
BWRW
WWWW

範例輸出

1
2
3
4
RWRR
WWWW
WWBR
BWWW

備註






Solution

模擬工作流程，平行計算下一個狀態，利用兩個滾動數組的方式交替使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1024
#define C_WHITE 0
#define C_RED   1
#define C_BLUE  2
 
char g1[MAXN][MAXN], g2[MAXN][MAXN];
 
void moveRed(int n) {
    #pragma omp parallel for schedule(static)
    for (int i = 0; i < n; i++)
        memset(g2[i], C_WHITE, sizeof(char) * n);
    #pragma omp parallel for schedule(static)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g1[i][j] == C_BLUE) {
                g2[i][j] = C_BLUE;
            } else if (g1[i][j] == C_RED) {
                int next = j+1 == n ? 0 : j+1;
                if (g1[i][next] == C_WHITE)
                    g2[i][next] = C_RED;
                else
                    g2[i][j] = C_RED;
            }
        }
    }
}
void moveBlue(int n) {
    #pragma omp parallel for schedule(static)
    for (int i = 0; i < n; i++)
        memset(g1[i], C_WHITE, sizeof(char) * n);
    #pragma omp parallel for schedule(static)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g2[i][j] == C_RED) {
                g1[i][j] = C_RED;
            } else if (g2[i][j] == C_BLUE) {
                int next = i+1 == n ? 0 : i+1;
                if (g2[next][j] == C_WHITE)
                    g1[next][j] = C_BLUE;
                else
                    g1[i][j] = C_BLUE;
            }
        }
    }
}
static inline int toIndex(char c) {
    if (c == 'W')    return C_WHITE;
    if (c == 'R')    return C_RED;
    if (c == 'B')    return C_BLUE;
    fprintf(stderr, "[WARNING] %s %d\n", __FILE__, __LINE__);
}
static void printBoard(int n) {
    char color[4] = "WRB";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            putchar(color[g1[i][j]]);
        putchar('\n');
    }
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++) {
            scanf("%s", &g1[i]);
            for (int j = 0; j < n; j++)
                g1[i][j] = toIndex(g1[i][j]);
        }
 
        for (int it = 0; it < m; it++) {
            moveRed(n);
            moveBlue(n);
        }
        printBoard(n);
    }
    return 0;
}
/*
4 1
RRWR
WWBW
BWRW
WWWW
*/