battleships in a board

fishercoder1534 · fishercoder1534 · commit 45deeb020fdd · 2016-10-19T09:37:39.000-07:00
diff --git a/MEDIUM/src/medium/BattleshipsinaBoard.java b/MEDIUM/src/medium/BattleshipsinaBoard.java
@@ -0,0 +1,61 @@
+package medium;
+
+public class BattleshipsinaBoard {
+    
+    /**Then I turned to Discuss and found this solution from the contributor of this problem: https://discuss.leetcode.com/topic/62970/simple-java-solution,
+     * basically, it only counts the top-left one while ignoring all other parts of one battleship.*/
+    public int countBattleships_no_modify_original_input(char[][] board) {
+        if(board == null || board.length == 0) return 0;
+        int count = 0, m = board.length, n = board[0].length;
+        for(int i = 0; i < m; i++){
+            for(int j = 0; j < n; j++){
+                if(board[i][j] == '.') continue;//if it can pass this line, then board[i][j] must be 'X'
+                if(j > 0 && board[i][j-1] == 'X') continue;//then we check if its left is 'X'
+                if(i > 0 && board[i-1][j] == 'X') continue;//also check if its top is 'X'
+                count++;
+            }
+        }
+        return count;
+    }
+
+    /**My original solution, actually modified the input. I just undo it at the end.*/
+    public int countBattleships(char[][] board) {
+        if(board == null || board.length == 0) return 0;
+        int result = 0, m = board.length, n = board[0].length;
+        for(int i = 0; i < m; i++){
+            for(int j = 0; j < n; j++){
+                if(board[i][j] == 'X'){
+                    result++;
+                    dfs(board, i, j, m, n);
+                }
+            }
+        }
+        
+        for(int i = 0; i < m; i++){
+            for(int j = 0; j < n; j++){
+                if(board[i][j] == '#') board[i][j] = 'X';
+            }
+        }
+        return result;
+    }
+    
+    private void dfs(char[][] board, int x, int y, int m, int n){
+        if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'X') return;
+        if(board[x][y] == 'X') board[x][y] = '#';
+        dfs(board, x+1, y, m, n);
+        dfs(board, x, y+1, m, n);
+        dfs(board, x-1, y, m, n);
+        dfs(board, x, y-1, m, n);
+    }
+    
+    public static void main(String...strings){
+        char[][] board = new char[][]{
+            {'X', '.', '.', 'X'},
+            {'.', '.', '.', 'X'},
+            {'.', '.', '.', 'X'},
+        };
+        
+        BattleshipsinaBoard test = new BattleshipsinaBoard();
+        System.out.println(test.countBattleships(board));
+    }
+}
diff --git a/README.md b/README.md
@@ -1,6 +1,7 @@
 # fishercoderLeetcode
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
+|419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../../blob/master/MEDIUM/src/medium/BattleshipsinaBoard.java) | | | Medium| DFS
 |415|[Add Strings](https://leetcode.com/problems/add-strings/)|[Solution](../../blob/master/EASY/src/easy/AddStrings.java)| O(n)|O(1) | Easy|
 |412|[Fizz Buzz](https://leetcode.com/problems/fizz-buzz/)|[Solution](../../blob/master/EASY/src/easy/FizzBuzz.java)| O(n)|O(1) | Easy|
 |398|[Random Pick Index](https://leetcode.com/problems/random-pick-index/)|[Solution](../../blob/master/MEDIUM/src/medium/RandomPickIndex.java) | | | Medium| Reservoir Sampling
