LeetCode419. Battleships in a Board

题意

给一个二维地图，统计图中战舰的数量，图中“X”表示战舰，“.”表示空地。

  1. 给的图一定是一个合法的地图
  2. 战舰的长度不固定，可以是1XN（1行N列）或者NX1（N行1列）
  3. 两个战舰间在水平或者垂直方向上至少有一个间隔

要求不申请空间

合法地图

X..X
…X
…X

两艘战舰

不合法地图

…X
XXXX
…X

思路

给一个合法地图，不需要判断合不合法！
给一个合法地图，不需要判断合不合法！
给一个合法地图，不需要判断合不合法！

因为船的方向只有垂直和水平，所以假定船头是朝上或者朝左，既只要统计船头数量即可。
若一个点是船头，则该点是“X”，且左边为“.”或者上边是“.”

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int countBattleships(char[][] board) {
        int ans = 0;
        for(int i = 0;i<board.length;i++)
            for(int j = 0;j<board[i].length;j++){
                if(board[i][j]=='X' 
                && (i==0||board[i-1][j]=='.') 
                && (j==0||board[i][j-1]=='.'))
                    ans++;
            }
        return ans;
    }
}

留言

2017-02-01
⬆︎TOP