419. Battleships in a Board

leetcode medium

#csharp#leetcode#matrix#medium#string

Task

Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).

Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]

Output: 2

C# solution

matched/original

public class Solution {
    public int CountBattleships(char[][] board) {
        int m = board.Length;
        int n = board[0].Length;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountBattleships(char[][] board) {
        int m = board.size();
        int n = board[0].size();
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int CountBattleships(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

JavaScript solution

matched/original

function countBattleships(board) {
    let m = board.length, n = board[0].length;
    let count = 0;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'X') {
                if ((i === 0 || board[i - 1][j] === '.') && (j === 0 || board[i][j - 1] === '.')) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

Python solution

matched/original

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

Go solution

matched/original

package main

func countBattleships(board [][]byte) int {
    m, n := len(board), len(board[0])
    count := 0
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'X' {
                if (i == 0 || board[i-1][j] == '.') && (j == 0 || board[i][j-1] == '.') {
                    count++
                }
            }
        }
    }
    
    return count
}

Explanation

Algorithm

Пройдите по каждой клетке матрицы.

Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров.

Верните итоговый счетчик.

😎