Battleships in a Board

传统的BFS方法没有什么太多讲的， 这里要求O(1)和不改变矩阵，则我们只能观察题目的要求有什么特殊的地方，这里可以发现每艘军舰是横的或竖的，这意味着军舰边界的两个点外围横竖都是没有X的，所以我们可以只统计位于末尾的X点来算军舰数

class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        n = len(board)
        if not n:
            return 0

        result = 0
        for i in xrange(n):
            for j in xrange(len(board[0])):
                if board[i][j] == 'X' and (i == 0 or board[i - 1][j] == '.') and (j == 0 or board[i][j - 1] == '.'):
                    result += 1
        return result