# 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
``````

• @icemountain Welcome to the new Discuss! Thanks for posting. Similar to Number of Islands, you have to verify there is only one single connected region where connectivity is defined as left, right, up, and down directions.

• In addtion to 1337c0d3r I can say that the only connected component should consist of 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;
}
``````

• @elmirap can't find your merge function? is it the same as the union function?

• @elmirap
By the way,
this test case fail
int[][] m = { {0,0,0,0,0,0}
,{0,1,1,0,0,0}
,{0,0,1,0,0,0}
,{0,0,1,0,0,0}
,{0,1,1,1,0,0}
,{0,0,0,0,0,0}
};
It returns true.

• the test pass, it should return true, because there is only one conncted component,which contains 0

• How about the puzzle only contains "1"?

• @elmirap
Your code indent does not show properly.

• @xidui yes, I didn't supposed that it is possible to have a matrix without zeros, so this test failes. I fixed it. Yes indent is strange.It doesn't look the same in my IDE. How to format it nere nicely?

``````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;
boolean hasNulls = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m ; j++) {
if (matrix[i][j] == 0) {
hasNulls = true;
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 || r <0 || c >= m || c < 0)
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;
}
}
}
}
if(!hasNulls)
return false;
return true;
}
``````

• @elmirap
Haha~ Your indent size looks like you are using golang~ I don't have an idea right now, every time I just do it manually here. May be you can set the indent preference in IDE, I think IDEA or similar products produced by Jetbrains can do that.

• @xidui My indent is 4 spaces, I use eclipse, when I copy paste the code, it doesn't appear the same way it is in th editor.

• @elmirap
The test case on
int[][] m = { {0,0,0,0,0,0}
,{0,1,1,1,0,0}
,{0,0,1,0,0,0}
,{0,0,1,0,0,0}
,{0,1,1,1,0,0}
,{0,0,0,0,0,0}
};
return false;
It is one island...

Besides, this is not a problem of finding the one island, it is to find only one path with no forks.
Chech the example case 3 in the question. It is invalid.
In other words, it is to find a path which is a "snake". :)

• @yubad2000 I don't understand the meaning of "interconnected" . From the examples, which are given by @icemountain I suggested that there is one connected component with 0. Maybe you could give me an example when , there is one connected component and white cells are not "interconnected". For the code above , seems that have a bug, will fix it

• @elmirap
:(
I am not sure about the problem either. But, I am feeling that you are right, it is to find one island consisting of all the 0s, not the 1s.
However, I ran you code.
This case
int[][] m =
{{0,0,0,0,0,0}
,{0,1,1,1,0,0}
,{0,0,1,0,0,0}
,{0,0,1,0,0,0}
,{0,1,1,1,0,0}
,{0,0,0,0,0,0}};
returns false, and it is one island of 0s. isn't it?

• I made an awful mistake with disjoint dataset. I forget that when I merge sets, I have to get the reprsentative, not the elements from the set and to change their root or rank. Cannot imagine how could my head produced this. I modified the algorithm and the disjoint set implementation, similar the way in leetcode. Thank you for pointing me out my issues.

``````class DisjointSets {
private int[] root;
private int[] rank;
public DisjointSets(int n) {
root = new int[n + 1];
rank = new int[n + 1];
for (int i = 1; i <= n; i++) {
root[i] = i;
rank[i] = 1;
}
}
int getRoot(int x) {
if (x != root[x]) {
root[x] = getRoot(root[x]);
}
return root[x];
}
boolean merge(int x, int y) {
int rX = getRoot(x);
int rY = getRoot(y);
if (rX != rY) {
if (rank[rX] == rank[rY]) {
root[rY] = rX;
rank[rX]++;
}
else if (rank[rX] < rank[rY])
root[rX] = rY;
else
root[rY] = rX;
return true;
}
else
return false;
}
}

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};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m ; j++) {
if (matrix[i][j] == 0)
count++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m ; j++) {
if (matrix[i][j] == 0) {
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 || r <0 || c >= m || c < 0)
continue;
if (matrix[r][c] == 0) {
if (ds.getRoot(r * m + c) != ds.getRoot(i * m + j)) {
if(ds.merge(i * m + j, r * m + c))
count--;
}
}
}
}
}
}
return count == 1;
}
``````

• @elmirap Your pasted code contains tabs, that's why the indent size is larger than 4 spaces. See if you can follow the instructions here and see if pasting code no longer insert tabs for you?

• @1337c0d3r, I used the instructions and you can see my new identation in the code above. Thank you

• @elmirap Awesome, glad that it worked for you :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.