## Tuesday, May 24, 2016

### Check if the given crossword puzzle is a valid puzzle

https://discuss.leetcode.com/topic/116/check-if-the-given-crossword-puzzle-is-a-valid-puzzle
A crossword puzzle is a valid puzzle if all the white columns of a grid are interconnected.
The question is to find out if a given grid of size mXn is a valid crossword puzzle.
You can move left and right and up and down only.

Consider 0 as white and black as 1

This is a valid crossword
00000
01000
01111
00001
This is an invalid crossword
00000
01010
01101
01000
This is an invalid crossword
00000
01000
01111
01000
0

Here is my implementation of the problem using Disjoint data structure. It could be implemented also with DFS or BFS

class DisjointSets  {
private int[] root;
private int[] rank;

public DisjointSets(int n) {
root = new int[n + 1];
for (int i = 1; i <= n; i++) {
root[i] = i;
}
rank = new int[n + 1];
}

int getRoot(int x) {
if (x != root[x]) {
root[x] = getRoot(root[x]);
}
return root[x];
}

int union(int x, int y) {
if  (rank[x]  == rank[y])  {
root[y]  =  root[x];
rank[x]++;
return root[x];
} else if (rank[x]  <  rank[y]) {
root[x]  =  root[y];
return root[y];
}
else {
root[y]  =  root[x];
return root[x];
}
}
}

boolean isValidPuzzle(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
DisjointSets ds = new DisjointSets(m * n);
int[] offset = new int[] {1, 1};
int root = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m ; j++) {
if (matrix[i][j] == 0) {
int current = i * m + j;
int newRoot = ds.getRoot(current);
for (int k = 0; k < 2; k++) {
int r = i;
int c = j;
if (k == 0)
c += offset[k];
else
r += offset[k];
if (r >= n ||  c >= m )
continue;
if (matrix[r][c] == 0) {
if (ds.getRoot(r * m + c) != ds.getRoot(current)) {
newRoot = ds.merge(current, r * m + c);
if (root != newRoot && root != -1){
return false;
}
root = newRoot;
}
}
}
if (root == -1)
root = newRoot;
else {
if (root != newRoot)
return false;
}
}
}
}
return true;
}
}