Leetcode 419 - Battleships in a Board(dfs)

    xiaoxiao2021-03-25  21

    题意

    给一个格点图,其中’X’代表当前位置有战舰,’.’代表当前位置为空位。

    其中,战舰只能横着放或者竖着放,并且长度为N(N为任意值)。并且,相邻两个战舰之间必须相隔一个格子。

    求:所以的战舰数目。

    思路

    算法1

    dfs,时间复杂度 O(mn) ,空间复杂度 O(mn)

    其实就和求连通块一样(四个方向),因为题目保证了数据的合法性,所以我们直接dfs求连通块的数目就好。

    代码偷了个懒用set存的是,所以时间复杂度会增加一个 log

    算法2

    好厉害的一个思路。

    时间复杂度 O(mn) ,空间复杂度 O(1)

    对于每个战舰,我们可以选用一个特征点(因为战舰都是横着或者竖着的),比如我们用战舰头来代表我们的战舰。

    所以,我们只需要统计一下战舰头有多少个就好。

    如果战舰是竖着放的:那么战舰头的上面一定是边界或者空地。

    如果战舰是横着放的:那么战舰头的左边一定是边界或者空地。

    所以我们去统计一下就好。

    代码

    dfs

    int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, -1, 1}; class Solution { private: int m, n; set<pair<int, int>> vis; public: void dfs(int i, int j, vector<vector<char>>& a) { if (i < 0 || i >= m || j < 0 || j >= n || vis.count(make_pair(i, j)) || a[i][j] == '.') return; vis.insert(make_pair(i, j)); for (int k = 0; k < 4; k++) dfs(i + dx[k], j + dy[k], a); } int countBattleships(vector<vector<char>>& board) { int cnt = 0; this->m = board.size(); if (m) { this->n = board[0].size(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'X' && !vis.count(make_pair(i, j))) cnt++; dfs(i, j, board); } } } return cnt; } };

    找头部算法

    class Solution { public: int countBattleships(vector<vector<char>>& a) { int m = a.size(), cnt = 0; if (m) { int n = a[0].size(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 'X' && (!i || a[i - 1][j] == '.') && (!j || a[i][j - 1] == '.')) cnt++; } } } return cnt; } };
    转载请注明原文地址: https://ju.6miu.com/read-50288.html

    最新回复(0)