【LeetCode: 289. 生命游戏 + BFS】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- - ⚡ BFS
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
- 💬 共勉

🚩 题目链接

289. 生命游戏

⛲ 题目描述

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：
在这里插入图片描述

输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
示例 2：

在这里插入图片描述

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 为 0 或 1

🌟 求解思路&实现代码&运行结果

⚡ BFS

🥦 求解思路

通过BFS挨个遍历判断每个位置，最后根据题目给定的规则更新答案。需要注意的是，因为该题目是同步更新，就意味着我们在更新完当前的位置后，如果直接更新当前的位置，那么会对最终的答案有影响。为了解决这个问题，我们可以复制一个同样大小的数组作为bfs遍历过程中的数组，将最终的答案直接更新到原数组中就可以解决该问题。
有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = { 0, 1, -1 };
        int m = board.length;
        int n = board[0].length;
        int[][] copyBoard = new int[m][n];
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int cnt = 0;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);
                            if ((r < m && r >= 0) && (c < n && c >= 0) && (copyBoard[r][c] == 1)) {
                                cnt += 1;
                            }
                        }
                    }
                }
                // 规则 1 2 3
                if ((copyBoard[row][col] == 1) && (cnt < 2 || cnt > 3)) {
                    board[row][col] = 0;
                }
                // 规则 4
                if (copyBoard[row][col] == 0 && cnt == 3) {
                    board[row][col] = 1;
                }
            }
        }
    }
}