C++で2Dボード上の戦艦の数を数える方法

問題概要

2次元のボードが与えられ、その中に何隻の戦艦（バトルシップ）が存在するかを数えることを考えます。戦艦は記号「X」で表され、空きマスは「.」で表されます。この問題では以下のルールが保証されています。

• 与えられるボードは有効であり、戦艦または空きマスのみで構成されています。
• 戦艦は水平方向または垂直方向にのみ配置されます。つまり、戦艦の形状は必ず 1xN（1行N列）または Nx1（N行1列）のいずれかであり、Nは任意のサイズを取れます。
• 2つの戦艦の間には、少なくとも1つの水平方向または垂直方向の空きマスが存在します。つまり、戦艦同士が隣接することはありません。

例として、以下のようなボードが与えられた場合を考えてみましょう。

この場合、戦艦は2隻存在するため、出力は 2 となります。

解法のアプローチ

この問題は、各マスを一度だけ走査するシンプルな方法で解くことができます。ポイントは、「戦艦の先頭（左端または上端）のマスだけをカウント対象にする」という発想です。具体的な手順は以下の通りです。

• カウンター ans を 0 で初期化し、行数を n、列数を m とします。
• 各行 i、各列 j について以下を判定します。
  • board[i][j] が「.」であれば、次の反復へ進みます。
  • i > 0 かつ board[i - 1][j] が「X」であれば、現在のマスは縦向き戦艦の続きなので、次の反復へ進みます。
  • j > 0 かつ board[i][j - 1] が「X」であれば、現在のマスは横向き戦艦の続きなので、次の反復へ進みます。
  • いずれにも該当しない場合、そのマスは新しい戦艦の始まりであるため、ans を1増やします。
• 最後に ans を返します。

この手法により、追加のメモリを使用せず、ボードを変更することもなく、O(n×m) の時間計算量で戦艦の数を求めることができます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int countBattleships(vector<vector<char>>& board) {
        int ans = 0;
        int n = board.size();
        int m = board[0].size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == '.')continue;
                if(i > 0 && board[i - 1][j] == 'X')continue;
                if(j > 0 && board[i][j - 1] == 'X')continue;
                ans++;
            }
        }
        return ans;
    }
};
main(){
    vector<vector<char>> v = {{'X','.','.','X'},{'.','.','.','X'},{'.','.','.','X'}};
    Solution ob;
    cout << (ob.countBattleships(v));
}

入力

[["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]

出力

2

まとめ

本記事では、2次元ボード上に配置された戦艦の数を数える問題を取り上げました。戦艦が水平・垂直方向にのみ配置され、互いに隣接しないという制約を活かすことで、各マスの上側と左側を確認するだけで戦艦の始点を特定でき、追加メモリ不要の効率的な実装が可能になります。時間計算量は O(n×m)、空間計算量は O(1) と非常にシンプルで実用的な解法です。