# Black Shapes

Given **N x M** character matrix **A** of `O's` and `X's`, where `O` = `white`, `X` = `black`.\
\
Return the number of black shapes. A black shape consists of one or more adjacent `X's` (diagonals not included)

\
\
**Input Format:**

```
    The First and only argument is a N x M character matrix.
```

**Output Format:**

```
    Return a single integer denoting number of black shapes.
```

**Constraints:**

```
    1 <= N,M <= 1000
    A[i][j] = 'X' or 'O'
```

**Example:**

```
Input 1:
    A = [ OOOXOOO
          OOXXOXO
          OXOOOXO  ]
Output 1:
    3
Explanation:
    3 shapes are  :
    (i)    X
         X X
    (ii)
          X
    (iii)
          X
          X
```

**Note:** we are looking for connected shapes here.

```
XXX
XXX
XXX
```

is just **one** single connected black shape.

```java
public class Solution {
    public int black(String[] A) {
        int m = A.length, n = A[0].length();
        boolean visited[][] = new boolean[m][n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i].charAt(j) == 'X' && !visited[i][j]) {
                    DFS(A, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void DFS(String[] A, boolean[][] visited, int x, int y) {
        if (x >= 0 && x < A.length && y >= 0 && y < A[x].length() && !visited[x][y] && A[x].charAt(y) == 'X') {
            visited[x][y] = true;
            DFS(A, visited, x + 1, y);
            DFS(A, visited, x - 1, y);
            DFS(A, visited, x, y + 1);
            DFS(A, visited, x, y - 1);
        }
    }
}
```
