本文介绍: 力扣、染色、方格

模拟 + 染色

  • 思路:
    • 可以复制一个表格,然后根据规则两层循环模拟出结果,但是空间复杂度太高;
    • 可以复用原有数组,对其进行染色标记;
      • 最终状态是活的标记值 > 1,还原标记值时可以使用规则 val > 0
      • 之前是活的现在是死的,标记成 -1,统计活细胞时可以使用规则 abs(val) = 1
    • 根据规则归纳:
      • R1:如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡,状态由 live 变成 die,用 -1 标记;(原状态是 live,需要被统计成活细胞)
      • R2:如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活,状态没有发生变化;
      • R3:如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡,状态由 live 变成 die,用 -1 标记;(原状态是 live,需要被统计成活细胞)
      • R4:如果死细胞周围正好有三个活细胞,则该位置死细胞复活,状态由 die 变成 live,用 2 标记;(最终状态是 live)
    • 进行两次两重循环遍历:
      • 第一次进行染色;
      • 第二次染色还原;
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int row = board.size();
        if (0 == row) {
            return;
        }
        int column = board[0].size();
        if (0 == column) {
            return;
        }

        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < column; ++c) {
                int live = 0;
                // statistics neighbors
                
                if (r > 0 && c > 0) {
                    // direct NW
                    if (std::abs(board[r - 1][c - 1]) == 1) {
                        live++;
                    }
                }
                if (r > 0) {
                    // direct N
                    if (std::abs(board[r - 1][c]) == 1) {
                        live++;
                    }                    
                }
                if (c > 0) {
                    // direct W
                    if (std::abs(board[r][c -1]) == 1) {
                        live++;
                    }
                }
                if (r + 1 < row) {
                    if (c > 0) {
                        // direct SW
                        if (std::abs(board[r + 1][c - 1]) == 1) {
                            live++;
                        }
                    }

                    // direct S
                    if (std::abs(board[r + 1][c]) == 1) {
                        live++;
                    }
                }
                if (c + 1 < column) {
                    // direct E
                    if (std::abs(board[r][c + 1]) == 1) {
                        live++;
                    }
                    if (r > 0) {
                        // direct NE
                        if (std::abs(board[r - 1][c + 1]) == 1) {
                            live++;
                        }
                    }
                    // direct SE
                    if (r + 1 < row) {
                        // direct NE
                        if (std::abs(board[r + 1][c + 1]) == 1) {
                            live++;
                        }
                    }
                }


                // rule 1 & 3
                if (board[r][c] == 1 && (live < 2 || live > 3)) {
                    // mark live -> die
                    board[r][c] = -1;
                }
                // rule 4
                if (board[r][c] == 0 && live ==  3) {
                    // mark die -> live
                    board[r][c] = 2;
                }
            }
        }

        // recover
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < column; ++c) {
                if (board[r][c] > 0) {
                    board[r][c] = 1;
                } else {
                    board[r][c] = 0;
                }
            }
        }
    }
};
  • 统计活细胞数量的逻辑比较朴素,可以进一步归纳美化;

原文地址:https://blog.csdn.net/N_BenBird/article/details/135541029

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_55230.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注