Battleships in a Board (Leetcode

这道题是一道Facebook和Microsoft共同的面试题。直接想到用搜索，DFS。不同的是，是两艘船不能挨着(限定条件)。

先给出最优解，由于题目中说明输入一定合理 (ships不会挨着)。所以只需找船头。从左上往右下找。如果左边或上面不是船身('X')， cnt++；不愧是最优解，O(n*m) time, O(1) space.

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        if(board.empty() || board[0].empty()) return 0;
        int row = board.size(), col = board[0].size();
        
        int cnt = 0;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(board[i][j] == 'X' && (i==0 || board[i-1][j] != 'X') && (j==0 || board[i][j-1] != 'X')) cnt++;
            }
        }
        return cnt;
    }
};

下面是我的搜索解法，DFS/BFS approach (加了ships不挨着的check):

DFS:

public class Solution {
    
    private boolean dfs(char[][] board, int i, int j, boolean[][] visited){
        int row = board.length, col = board[0].length;
        visited[i][j] = true;
        int cnt = 0, candX = 0, candY = 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(int[] it : directions){
            int x = i+it[0], y = j+it[1];
            if(x < 0 || x >= row || y < 0 || y >= col || visited[x][y]) continue;
            if(board[x][y] == 'X'){
                cnt++;
                candX = x; candY = y;
            }
        }
        if(cnt >= 2) return false;
        else if(cnt == 1){
            if(!dfs(board, candX, candY, visited)) return false;
        }
        return true;
    }
    
    public int countBattleships(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0) return 0;
        int row = board.length, col = board[0].length;
        int cnt = 0;
        boolean[][] visited =  new boolean[row][col];
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(board[i][j] != 'X' || visited[i][j]) continue;
                if(dfs(board, i, j, visited)) cnt++;
            }
        }
        return cnt;
    }
}

BFS:

public int countBattleships(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0) return 0;
        int row = board.length, col = board[0].length;
        int cnt = 0;
        boolean[][] visited =  new boolean[row][col];
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        Queue<int[]> q = new LinkedList<>();
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(board[i][j] != 'X' || visited[i][j]) continue;
                q.offer(new int[]{i, j});
                boolean isValid = true;
                while(q.size() > 0){
                    int[] cur = q.poll();
                    visited[cur[0]][cur[1]] = true;
                    int num = 0, candX = 0, candY = 0;
                    for(int[] dir : directions){
                        int x = cur[0] + dir[0], y = cur[1] + dir[1];
                        if(x < 0 || x >= row || y < 0 || y >= col || visited[x][y]) continue;
                        if(board[x][y] == 'X'){
                            num++;
                            candX = x; candY = y;
                        }
                    }
                    if(num >= 2) isValid = false;
                    else if(num == 1){
                        q.offer(new int[]{candX, candY});
                    }
                }
                if(isValid) cnt++;
            }
        }
        return cnt;
    }