## LeetCode——419. Battleships in a Board 原

守恒的猫

Given an 2D board, count how many battleships are in it. The battleships are represented with `'X'`s, empty slots are represented with `'.'`s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape `1xN` (1 row, N columns) or `Nx1` (N rows, 1 column), where N can be of any size.
• At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

```X..X
...X
...X```

In the above board there are 2 battleships.

Invalid Example:

```...X
XXXX
...X```

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

Subscribe to see which companies asked this question.

• 给定的板子是有效的，只包含战舰和空白槽位。
• 战舰只能水平或者竖直放置。
• 战舰的尺寸可能不同。
• 两艘战舰之间在水平方向或者竖直方向至少包含一个空间—不会存在相邻的战舰。

class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
found_set = set()
ans = 0
row_len = len(board)
col_len = len(board[0] if row_len else [])
def dfs(x, y):
for movex, movey in zip((1,0,-1,0),(0,1,0,-1)):
nx, ny = x + movex, y + movey
if 0 <= nx < row_len and 0 <= ny < col_len:
if (nx,ny) not in found_set and board[nx][ny] == 'X':
dfs(nx,ny)

for x in xrange(row_len):
for y in xrange(col_len):
if board[x][y] == 'X' and (x,y) not in found_set:
ans += 1
dfs(x,y)
return ans

A掉

### 守恒的猫

2018/01/04
0
0
HDU 6138 Fleet of the Eternal Throne 后缀数组+字典树

Fleet of the Eternal Throne Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 461 Accepted Submission(s): 141 Problem Descrip......

ProLightsfxjh
2017/08/19
0
0
nomasp 博客导读：Lisp/Emacs、Algorithm、Android

nomasp
2015/09/17
0
0

Java Battleships是一个双人网络游戏。它包括的舰船有驱逐舰，扫雷艇和鱼雷船。每种舰船有不同的武器，运动方式，装甲和雷达。你必须在C:BATTLESHIPS下运行server.bat，再运行gui.bat。...

2009/07/21
2.4K
0
[LeetCode] Word Search

★ 题目 https://leetcode.com/problems/word-search/ Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially ad......

u013553529
2018/01/10
0
0

js算法总结

33分钟前
1
0

40分钟前
1
0

MySQL事实上使用不同的存储引擎也是有很大区别的，下面猿友们可以了解一下。 一、存储引擎的比较 注：上面提到的B树索引并没有指出是B-Tree和B+Tree索引，但是B-树和B+树的定义是有区别的。 ...

Java爬坑之路
44分钟前
1
0
mysql group by 和 Order By 执行顺序

1.在写统计的时候，我们会用到统计首单，这样里面设计到排序。写子查询的方式当然可以实现， 但是我们有时候，需要创建视图，视图不支持带子查询的。 加了排序后会返回，排序后的哪个第一条数...

kuchawyz
48分钟前
2
0
Spring Boot 2.X 如何添加拦截器？

1
0