当前位置：首页 > article >正文

每日一题 419. 棋盘上的战舰

article 2025/1/26 14:34:35

419. 棋盘上的战舰

简单

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        
        int ans = 0;
        for(int i=0;i<board.size();++i)
        {
            for(int j=0;j<board[0].size();++j)
            {
                if(board[i][j] == 'X')
                {
                    dfs(board,i,j);
                    ++ans;
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<char>> &board,int x,int y)
    {
        board[x][y] = 'a';
        int dx[4] = {1,0,-1,0};
        int dy[4] = {0,1,0,-1};
        for(int i = 0;i<4;++i)
        {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if(nx>=0 && nx < board.size() && ny >= 0 && ny < board[0].size() && board[nx][ny] == 'X')
            {
                dfs(board,nx,ny);
            }
        }
    }
};