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)

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

    Return a single integer denoting number of black shapes.

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

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.

Solution:

BFS + union find

Time: O(E + V)

public class Solution {
    static class UF {
        private int count;
        private int[] parent;
        private int[] size;
        
        public UF(int n) {
            count = 0;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i ++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        public int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            if (size[rootX] <= size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
            count --;
        }
        
        public int count() {
            return this.count;
        }
        
        public void incrementCount() {
            this.count ++;
        }
    }
    
    static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        public int index(int n) {
            return x * n + y;
        }
        
        public boolean valid(int m, int n) {
            return x >= 0 && x < m && y >= 0 && y < n;
        }
        
        @Override
        public int hashCode() {
            int hash = 17;
            hash += this.x * 31;
            hash += this.y * 31;
            return hash;
        }
        
        @Override
        public boolean equals(Object o) {
            Node n = (Node) o;
            return n.x == x && n.y == y;
        }
    }
    
    public int black(String[] A) {
        int m = A.length;
        int n = A[0].length();
        Queue<Node> queue = new ArrayDeque<>();
        Set<Node> visited = new HashSet<>();
        UF blk = new UF(m * n);
        int[] dx = new int[]{-1,0,1,0};
        int[] dy = new int[]{0,1,0,-1};
        for (int i = 0; i < m; i ++) {
            String s = A[i];
            for (int j = 0; j < n; j ++) {
                char c = s.charAt(j);
                if (c == 'X') {
                    blk.incrementCount();
                    queue.offer(new Node(i, j));
                }
            }
        }
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (visited.add(node)) {
                for (int i = 0; i < 4; i ++) {
                    Node next = new Node(node.x + dx[i], node.y + dy[i]);
                    if (next.valid(m, n) && A[next.x].charAt(next.y) == 'X') {
                        blk.union(node.index(n), next.index(n));
                        queue.offer(next);
                    }
                }
            }
        }
        return blk.count();
    }
}