Сложность: medium
Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).
Пример:
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2
👨💻 Алгоритм:
1⃣Пройдите по каждой клетке матрицы.
2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров.
3⃣Верните итоговый счетчик.
😎 Решение:
def countBattleships(board):
m, n = len(board), len(board[0])
count = 0
for i in range(m):
for j in range(n):
if board[i][j] == 'X':
if (i == 0 or board[i - 1][j] == '.') and (j == 0 or board[i][j - 1] == '.'):
count += 1
return count
Ставь 👍 и забирай 📚 Базу знаний