O(N*M) memory and without changing the board. This works when received the invalid board also.


  • 0
    Z

    This code will take the invalid boards and the code will not modify the board. But it will take O(n * m) space for visited array to track the visited nodes and also O(n * m) space in worst case for dfs if the entire board is filled with 'X'. Time complexity is also O(n * m). Here 'n' is the number of rows and 'm' is the number cells in each row.

    public://O(N*M) memory and without changing the board. This works when received the invalid board also.
    	int countBattleships(vector<vector<char>>& board) {
    		int nr = board.size();
    		if (!nr) return 0;
    		int nc = board[0].size();
    		vector<vector<char>>visited = board;
    		int count = 0;
    		for (int r = 0; r < nr; ++r) {
    			for (int c = 0; c < nc; ++c) {
    				visited[r][c] = '0';//not visited
    			}
    		}
    		for (int r = 0; r < nr; ++r) {
    			for (int c = 0; c < nc; ++c) {
    				if (board[r][c] == '.') {
    					visited[r][c] = '1';
    					continue;
    				}
    				if (board[r][c] == 'X' && visited[r][c] == '0') {
    					bool res = true;
    					visited[r][c] = '1';
    					dfs(board, r, c, res, visited);
    					if (res)
    						count++;
    				}
    			}
    		}
    		return count;
    	}
    private:
    	void dfs(vector<vector<char>>&board, int r, int c, bool &res, vector<vector<char>>&visited) {
    			if (valid(r + 1, c + 1, board) && board[r][c + 1] == 'X' && board[r + 1][c] == 'X' ||
    				valid(r + 1, c - 1, board) && board[r + 1][c] == 'X' && board[r][c - 1] == 'X' || 
    				valid(r - 1,c + 1, board) && board[r - 1][c] == 'X' && board[r][c + 1] == 'X' ||
    				valid(r - 1,c - 1, board) && board[r-1][c] == 'X' && board[r][c-1] == 'X')
    				res = false;
    			if (valid(r - 1, c, board ) && board[r - 1][c] == 'X' && visited[r - 1][c] != '1') { visited[r - 1][c] = '1'; dfs(board, r - 1, c, res, visited); }
    			if (valid(r + 1, c, board) && board[r + 1][c] == 'X' && visited[r + 1][c] != '1') { visited[r + 1][c] = '1'; dfs(board, r + 1, c, res, visited);  }
    			if (valid(r, c - 1, board) && board[r][c - 1] == 'X' && visited[r][c -1 ] != '1') { visited[r][c - 1] = '1'; dfs(board, r, c - 1, res, visited);  }
    			if (valid(r, c + 1, board) && board[r][c + 1] == 'X' && visited[r][c + 1] != '1') { visited[r][c + 1] = '1'; dfs(board, r, c + 1, res, visited); }
    	}
    	bool valid(int r, int c, vector<vector<char>>&board) {
    		return (r >= 0 && r < board.size() && c >= 0 && c < board[0].size());
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.