sc 31-40

P31 给你一个立着的棋盘，然后每一次落子都会因为重力掉到最低的没有棋子的那一格。如果vertical, horizontal, diagonal有三个同一选手的子（就是有一个三连），就算胜利。

要求写一个isvalid来检查这个棋盘是不是valid的（即没有悬空的子的情况。）

然后要求写一个nextMove。来输出下一子的位置。 nextMove要尽量保证你的对手不能赢

例子如下，0代表空着的位置，1代表1号选手下的位置，2代表2号选手下的位置。

| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 2 | 0 |
| 0 | 2 | 1 | 1 | 2 |
---------------------

思路：其实，tic-tac-toe的带重力加强版.valid就是每一列挨个检查有没有悬空子的情况。nextMove就是我把对手每个可能的下一步都判断一遍，如果那一步能赢，我就要堵住。由于带重力，所以每一列只可能有一个位置。还是很好检查的。nextP这个array代表了每一列能下的位置。我只写了判断vertical horizontal的，diagonal的一样的写法。懒得写了哈。

class Connect3(object):
    def __init__(self, grid):
        self.grid = grid
        self.nextP = [0]*len(grid[0])

    def isValid(self):
        """
        :rtype: Bool
        """
        for j in range(len(grid[0])):
            i = 0
            # for every column down to the first not 0 point
            while i<len(self.grid) and self.grid[i][j]==0:
                i += 1
            self.nextP[j] = i-1
            # then check if there is 0 in side.
            while i<len(self.grid):
                if grid[i][j]==0:
                    return False
                i += 1
        return True

    def nextMove(self, player):
        """
        :type player: Int
        :rtype: List[List[int]]
        """
        opponent = 1 if player==2 else 2
        res = []
        for i in range(len(self.nextP)):
            r, c = self.nextP[i], i
            if self.checkWin(r, c, opponent):
                res.append([r,c])
        return res

    def checkWin(self, i, j, player):
        """
        :type i: Int
        :type j: Int
        :type player: Int
        :rtype: Bool
        """
        # check vertical
        up, down = i+1, i-1
        count = 0
        while 0<=up<len(self.grid):
            if self.grid[up][j] == player:
                count += 1
            up += 1
        while 0<=down<len(self.grid):
            if self.grid[down][j] == player:
                count += 1
            down -= 1
        if count == 2:
            return True
        # check horizontal
        left, right = j-1, j+1
        count = 0
        while 0<=left<len(self.grid[0]):
            if self.grid[i][left] == player:
                count += 1
            left -= 1
        while 0<=right<len(self.grid[0]):
            if self.grid[i][right] == player:
                count += 1
            right += 1
        if count == 2:
            return True

grid = [[0,0,0],[0,1,0],[0,1,0]]
so = Connect3(grid)
an = so.isValid()
print an
print so.nextP
res = so.nextMove(2)
print res