leetcode：419. 甲板上的战舰_leetcode419

题目来源

• leetcode

题目描述

题目解析

• 麻了麻了，你说 “ 每个单元格可以是一艘战舰 ” ，你不如说 “ 一艘战舰可以占一个或多个单元格 ”。。。
• 终于看明白题目了，x是战舰，题目求的是战舰群的数目，并且战舰群只能横向或纵向一字排列，十字形、丁字型、L字型的都不是战舰群

相似的题目：

• leetcode：463. 岛屿的周长

dfs

class Solution {
  
    void dfs(vector<vector<char>>& board, int i, int j){
        if(i < 0 || i >= board.size() || j < 0 || j >= board[i].size() || board[i][j] == '.') 
            return;
        board[i][j] = '.';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j+1);
        dfs(board, i, j-1);
    }
public:
    int countBattleships(vector<vector<char>>& board) {
        int res = 0;
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if(board[i][j] == 'X'){
                    ++res;
                    dfs(board, i, j);
                }
            }
        }
        
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

因为，每一艘战舰要么是竖着的，要么是横着的，而且两艘不同的战舰之间至少包含一个空格，也就是说每艘战舰的起点的上方和左方都不会是 ‘X’，所以，我们只需要统计起点即可。

class Solution {
    
public:
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();

        int ans = 0;

        // 一次扫描
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 起点为X，左边不为X，上边不为X
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X')) {
                    ans++;
                }
            }
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return 0;
        int res = 0, m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X' && !visited[i][j]) {
                    ++res;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    while (!q.empty()) {
                        auto t = q.front(); q.pop();
                        visited[t.first][t.second] = true;
                        for (auto dir : dirs) {
                            int x = t.first + dir[0], y = t.second + dir[1];
                            if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || board[x][y] == '.') continue;
                            q.push({x, y});
                        }
                    }
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28