首先想到的是DFS方法，如下
class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
vs = []
h = len(board)
v = len(board[0])
ans = 0
if h is None:
return 0
def dfs(x,y):
for dx,dy in zip((1,0,-1,0),(0,1,0,-1)):
nx = x+dx
ny = y+dy
if 0<=nx<h and 0<=ny<v:
if (nx, ny) not in vs and board[nx][ny] == 'X':
vs.append((nx,ny))
dfs(nx,ny)
for i in range(0,h):
for j in range(0,v):
if (i,j) not in vs and board[i][j] == 'X':
ans += 1
vs.append((i,j))
dfs(i,j)
return ans
然而，超时了。想了想，有些地方重复了两次，完全没必要，我们只要保证X的左边和上面没有X就OK，
所以换成下面的：
class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
v = len(board)
h = len(board[0])
ans = 0
if v is None:
return 0
for i in range(0,v):
for j in range(0,h):
if i == 0 and j == 0 and board[i][j] == 'X':
ans += 1
if i == 0 and j>=1:
if board[0][j] == 'X' and board[0][j-1] == '.':
ans += 1
if j == 0 and i>=1:
if board[i][0] == 'X' and board[i-1][0] == '.':
ans += 1
if i >=1 and j >=1:
if board[i][j] == 'X' and board[i-1][j] == '.' and board[i][j-1] =='.':
ans +=1
return ans
AC
主要学习了一下深度优先搜索，这个好久没看过了，有些细节记不太清了
