leetcode_289

发表于   |   分类于

Game of Life

题目戳这

题意

给定一个n*m的矩阵，矩阵中的值为0或者1，0代表这个格子是死的，1代表这个格子是活的。然后给定一系列的规则，比如一个活格子的周围(八个方向)如果存在少于2个活格子，那么该活格子死亡等等，一共有四个规则。而且对于每个格子，判断周围的格子状态时要看其原始状态，不能是更新以后的。不能用额外空间，要在原矩阵中改动格子的状态。

解法

这个题目的难点在于不能用额外的空间，如果可以用额外的空间的话，那这道题目就不难了。我们怎么在记录原格子状态的情况下改变该格子的状态。

我们用两位二进制数来表示该格子的状态，00，01，10，11。分别表示为：

00：该格子原来是死的，更新后还是死的。

10：该格子原来是死的，更新后为活的。

01：该格子原来是活的，更新后为死的。

11：该格子原来是活的，更新后还是活的。

我们观察下，为什么这么表示。两位二进制的第一位，也就是低位，表示的是原状态；第二位，也就是高位，表示的是更新后的状态。所以10代表的就是原来是死的，更新后为活的。

那么这样的话，我们在判断某个格子的周围格子状态时，只看低位为0或者1即可。当更新完以后，我们将所有状态往右移动一位，只取高位，则得到了更新后棋盘的状态。

代码

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
class Solution(object):
    def getLiveCell(self,n,m,x,y,bd):
        nm = 0
        for i in range(max(x-1,0),min(x+2,n)):
            for j in range(max(y-1,0),min(y+2,m)):
                if i == x and j == y:
                    continue
                if bd[i][j] & 1 == 1:
                    # print i,j
                    nm += 1
        return nm
    
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        n = len(board)
        m = len(board[0])
        # print (n,m) 
        for i in range(n):
            for j in range(m):
                nm = self.getLiveCell(n,m,i,j,board)
                # print nm
                if board[i][j] == 1 and nm < 2:
                    board[i][j] = 1
                elif board[i][j] == 1 and (nm == 2 or nm == 3):
                    board[i][j] = 3
                elif board[i][j] == 1 and nm > 3:
                    board[i][j] = 1
                elif board[i][j] == 0 and nm == 3:
                    board[i][j] = 2
        
        for i in range(n):
            for j in range(m):
                # print board[i][j]
                board[i][j] >>= 1