419. Battleships in a Board

淡淡的烟草味﹌ 2022-05-23 02:50 105阅读 0赞

/\*

Given an 2D board, count how many battleships are in it. The battleships are represented with `'X'`s, empty slots are represented with `'.'`s. You may assume the following rules:

*  You receive a valid board, made of only battleships or empty slots.
 *  Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape `1xN` (1 row, N columns) or `Nx1` (N rows, 1 column), where N can be of any size.
 *  At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

**Example:**

X..X
    ...X
    ...X

In the above board there are 2 battleships.

**Invalid Example:**

...X
    XXXX
    ...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

**Follow up:**  
Could you do it in **one-pass**, using only **O(1) extra memory** and **without modifying** the value of the board?

\*/

/\*

思路：先对于等于X的数组上下左右进行查询，是否存在两个方向都存在X。如果是就return 0；

然后开始进行遍历查询，查询每一个数组元素等于X，如等于X，查询他的下方跟右方，如果存在，就将他们置为“.”

\*/

class Solution \{  
    public int countBattleships(char\[\]\[\] board) \{  
        int count = 0;  
        int rowLength = board.length-1;  
        int colLength = board\[0\].length-1;  
        for(int i=0; i<=rowLength; i++) \{//判断是否有效  
            for(int j=0; j<=colLength; j++) \{  
                if(board\[i\]\[j\]=='X') \{  
                    if((i-1)>=0 && (j-1)>=0) \{//比较上左  
                        if(board\[i-1\]\[j\]=='X' && board\[i\]\[j-1\]=='X')  
                            return 0;  
                    \}  
                    if((i-1)>=0 && (j+1)<colLength) \{//比较上右  
                        if(board\[i-1\]\[j\]=='X' && board\[i\]\[j+1\]=='X')  
                            return 0;  
                    \}  
                    if((i+1)<rowLength && (j-1)>=0) \{//比较下左  
                        if(board\[i+1\]\[j\]=='X' && board\[i\]\[j-1\]=='X')\{  
                             
                            return 0;  
                        \}  
                    \}  
                    if((i+1)<=rowLength && (j+1)<=colLength) \{//比较下右  
                        if(board\[i+1\]\[j\]=='X' && board\[i\]\[j+1\]=='X')  
                            return 0;  
                    \}  
                \}  
            \}  
        \}  
          
        for(int i=0; i<=rowLength; i++) \{  
            for(int j=0; j<=colLength; j++) \{  
                if(board\[i\]\[j\]=='X') \{  
                    count++;  
                    board\[i\]\[j\] = '.';  
                    if((i+1)<=rowLength) //查找下面是否存在  
                        if(board\[i+1\]\[j\]=='X')  
                            for(int n=i+1;n<=rowLength && board\[n\]\[j\]=='X'; n++)  
                                board\[n\]\[j\] = '.';                 
                    if((j+1)<=colLength)//查找右面是否存在  
                        if(board\[i\]\[j+1\]=='X')  
                            for(int m=j+1; m<=colLength && board\[i\]\[m\]=='X'; m++)  
                                board\[i\]\[m\] = '.';  
                \}  
            \}  
        \}  
        return count;  
    \}  
\}