Leetcode 419 - Battleships in a Board（dfs）

题意

给一个格点图，其中’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; } };