|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +publicclassBattleshipsinaBoard { |
| 4 | + |
| 5 | +/**Then I turned to Discuss and found this solution from the contributor of this problem: https://discuss.leetcode.com/topic/62970/simple-java-solution, |
| 6 | + * basically, it only counts the top-left one while ignoring all other parts of one battleship.*/ |
| 7 | +publicintcountBattleships_no_modify_original_input(char[][]board) { |
| 8 | +if(board ==null ||board.length ==0)return0; |
| 9 | +intcount =0,m =board.length,n =board[0].length; |
| 10 | +for(inti =0;i <m;i++){ |
| 11 | +for(intj =0;j <n;j++){ |
| 12 | +if(board[i][j] =='.')continue;//if it can pass this line, then board[i][j] must be 'X' |
| 13 | +if(j >0 &&board[i][j-1] =='X')continue;//then we check if its left is 'X' |
| 14 | +if(i >0 &&board[i-1][j] =='X')continue;//also check if its top is 'X' |
| 15 | +count++; |
| 16 | + } |
| 17 | + } |
| 18 | +returncount; |
| 19 | + } |
| 20 | + |
| 21 | +/**My original solution, actually modified the input. I just undo it at the end.*/ |
| 22 | +publicintcountBattleships(char[][]board) { |
| 23 | +if(board ==null ||board.length ==0)return0; |
| 24 | +intresult =0,m =board.length,n =board[0].length; |
| 25 | +for(inti =0;i <m;i++){ |
| 26 | +for(intj =0;j <n;j++){ |
| 27 | +if(board[i][j] =='X'){ |
| 28 | +result++; |
| 29 | +dfs(board,i,j,m,n); |
| 30 | + } |
| 31 | + } |
| 32 | + } |
| 33 | + |
| 34 | +for(inti =0;i <m;i++){ |
| 35 | +for(intj =0;j <n;j++){ |
| 36 | +if(board[i][j] =='#')board[i][j] ='X'; |
| 37 | + } |
| 38 | + } |
| 39 | +returnresult; |
| 40 | + } |
| 41 | + |
| 42 | +privatevoiddfs(char[][]board,intx,inty,intm,intn){ |
| 43 | +if(x <0 ||x >=m ||y <0 ||y >=n ||board[x][y] !='X')return; |
| 44 | +if(board[x][y] =='X')board[x][y] ='#'; |
| 45 | +dfs(board,x+1,y,m,n); |
| 46 | +dfs(board,x,y+1,m,n); |
| 47 | +dfs(board,x-1,y,m,n); |
| 48 | +dfs(board,x,y-1,m,n); |
| 49 | + } |
| 50 | + |
| 51 | +publicstaticvoidmain(String...strings){ |
| 52 | +char[][]board =newchar[][]{ |
| 53 | + {'X','.','.','X'}, |
| 54 | + {'.','.','.','X'}, |
| 55 | + {'.','.','.','X'}, |
| 56 | + }; |
| 57 | + |
| 58 | +BattleshipsinaBoardtest =newBattleshipsinaBoard(); |
| 59 | +System.out.println(test.countBattleships(board)); |
| 60 | + } |
| 61 | +} |