50047. Game of Cell

難度：4.5/5 Used Time: 13:28

if很慢，能少用就儘量少用。這題一個if都不能用。

學到的東西： (1) 與其

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[] = {1, 0, -1, 1, -1, 1, 0, -1};

int is_valid(int i, int j){
    return ...
}

int count(int grid[50][50], int i, int j){
    for(int k = 0; k < 8; k++){
        if(is_valid(i + dx[k], j + dy[k])){
            cnt += ...
        }
    }
}
不如直接往右下shift一格，就不用檢查邊界，可以省時間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[] = {1, 0, -1, 1, -1, 1, 0, -1};

int ext_grid[52][52] = 0;
for(int i = 0; i < 50; i++) for(int j = 0; j < 50; j++){
    ext_grid[i + 1][j + 1] = grid[i][j];
}

int cnt = 0;
for(int i = 1; i <= 50; i++) for(int j = 1; j <= 50; j++){
    for(int k = 0; k < 8; k++){
        cnt += ext_grid[i + dx[k]][j + dy[k]]...
    }
}

(2)與其

1
2
3
4
5
6
7
8
9
10
11
12
13
if(ext_grid[i][j] == DEAD){
    if(cnt == 3) temp_grid[i][j] = HEALTHY;
    else temp_grid[i][j] = DEAD;
}
else if(ext_grid[i][j] == DYING){
    if(cnt == 2) temp_grid[i][j] = HEALTHY;
    else temp_grid[i][j] = DYING;
}
else if(ext_grid[i][j] == HEALTHY){
    if(cnt < 2) temp_grid[i][j] = DEAD;
    else if(cnt > 3) temp_grid[i][j] = DYING;
    else temp_grid[i][j] = HEALTHY;
}
可以直接
1
2
3
4
5
6
7
const int change[3][9] = {
    {0, 0, 0, 2, 0, 0, 0, 0, 0},
    {1, 1, 2, 1, 1, 1, 1, 1, 1},
    {0, 0, 2, 2, 1, 1, 1, 1, 1}
};

temp_grid[i][j] = change[ext_grid[i][j]][count_around(ext_grid, i, j)];
達到更快速的查詢。

(3)因為要計算的healthy cell為2，其他可能出現的cell是0或1，若要計算2出現了幾次（這題用if會TLE），

1
2
3
4
int cnt = 0;
for(int k = 0; k < 8; k++){
    if(grid[i + dx[k]][j + dy[k]] == 2) cnt++;
}
可以直接：
1
2
3
int cnt = 0;
for(int k = 0; k < 8; k++)
    cnt += grid[i + dx[k]][j + dy[k]] / 2;

Ver 1 code (TLE 70%)

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
#include <string.h>
 
#define DEAD 0
#define DYING 1
#define HEALTHY 2
 
const int dx[] = {1, 1, 1, 0, 0, -1, -1, -1}, dy[] = {1, 0, -1, 1, -1, 1, 0, -1};
 
static inline int count_around(int grid[52][52], int i, int j){
    int cnt = 0;
    for(int k = 0; k < 8; k++){
        int now_x = i + dx[k], now_y = j + dy[k];
        if(grid[now_x][now_y] == HEALTHY) cnt++;
    }
    return cnt;
}
 
void game_of_cell(int grid[50][50], int outcome[50][50], int N){
    int ext_grid[52][52]; memset(ext_grid, 0, sizeof(ext_grid));
    int temp_grid[52][52];
 
    for(int i = 0; i < 50; i++) for(int j = 0; j < 50; j++){
        ext_grid[i + 1][j + 1] = grid[i][j];
    }
 
    while(N--){
        for(int i = 1; i <= 50; i++) for(int j = 1; j <= 50; j++){
            int cnt = count_around(ext_grid, i, j);
            if(ext_grid[i][j] == DEAD){
                if(cnt == 3) temp_grid[i][j] = HEALTHY;
                else temp_grid[i][j] = DEAD;
            }
            else if(ext_grid[i][j] == DYING){
                if(cnt == 2) temp_grid[i][j] = HEALTHY;
                else temp_grid[i][j] = DYING;
            }
            else if(ext_grid[i][j] == HEALTHY){
                if(cnt < 2) temp_grid[i][j] = DEAD;
                else if(cnt > 3) temp_grid[i][j] = DYING;
                else temp_grid[i][j] = HEALTHY;
            }
        }
 
        for(int i = 1; i <=  50; i++) for(int j = 1; j <= 50; j++){
            ext_grid[i][j] = temp_grid[i][j];
        }
    }
 
    for(int i = 0; i < 50; i++) for(int j = 0; j < 50; j++){
        outcome[i][j] = ext_grid[i + 1][j + 1];
    }
 
}

Ver 6 Code (AC)

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
#include <string.h>
 
const int dx[] = {1, 1, 1, 0, 0, -1, -1, -1}, dy[] = {1, 0, -1, 1, -1, 1, 0, -1};
const int change[3][9] = {
    {0, 0, 0, 2, 0, 0, 0, 0, 0},
    {1, 1, 2, 1, 1, 1, 1, 1, 1},
    {0, 0, 2, 2, 1, 1, 1, 1, 1}
};
 
static inline int count_around(int grid[52][52], int i, int j){
    int cnt = 0;
    for(int k = 0; k < 8; k++)
        cnt += grid[i + dx[k]][j + dy[k]] / 2;
    return cnt;
}
 
void game_of_cell(int grid[50][50], int outcome[50][50], int N){
    int ext_grid[52][52] = {0};
    int temp_grid[52][52] = {0};
 
    for(int i = 0; i < 50; i++) for(int j = 0; j < 50; j++){
        ext_grid[i + 1][j + 1] = grid[i][j];
    }
 
    while(N--){
        for(int i = 1; i <= 50; i++) for(int j = 1; j <= 50; j++){
            temp_grid[i][j] = change[ext_grid[i][j]][count_around(ext_grid, i, j)];
        }
 
        for(int i = 1; i <= 50; i++) for(int j = 1; j <= 50; j++){
            ext_grid[i][j] = temp_grid[i][j];
        }
    }
 
    for(int i = 0; i < 50; i++) for(int j = 0; j < 50; j++){
        outcome[i][j] = ext_grid[i + 1][j + 1];
    }
}
Coding > Solutions > Judge Girl > 2016
#2d-array#implementation#optimization
50047. Game of Cell
https://aaronlin1229.github.io/judgegirl_50047/
Author
Akizumi
Posted on
July 17, 2023
Licensed under