Check if the given crossword puzzle is a valid puzzle


  • 0
    I

    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

    @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.


  • 0

    In addtion to 1337c0d3r I can say that the only connected component should consist of 0


  • 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;
    		}
    

  • 0

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


  • 0

    @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.


  • 0

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


  • 0

    How about the puzzle only contains "1"?


  • 0

    @elmirap
    Your code indent does not show properly.


  • 0

    @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;
    }
    

  • 0

    @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.


  • 0

    @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.


  • 0

    @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". :)


  • 0

    @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


  • 0

    @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?


  • 0

    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;
    }
    

  • 0

    @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?


  • 0

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


  • 0

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


Log in to reply
 

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