Given a squared sized grid of size in which each cell has a lowercase letter. Denote the character in the the row and in the th column as G[i][j].

You can perform one operation as many times as you like: Swap two column adjacent characters in the same row G[i][j] and G[i][j+1] for all valid i,j;

Is it possible to rearrange the grid such that the following condition is true?

G[i][j]<=G[i][2]<=….<=G[i]N] for 1<=i <=N

G[1][j]<=G[2][j]<=….<=G[N][j] for 1<=j<=N

In other words, is it possible to rearrange the grid such that every row and every column is lexicographically sorted?

**Solution :**

This is fairly easy to resolve.We can approach this problem by first sorting the rows, which implies the first condition is taken care of.Next we need to check if columns are sorted, if they are sorted the even second condition is true.

Below is the scala code for the same.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
object GridChallenge { def main(args: Array[String]): Unit = { val sc = new java.util.Scanner (System.in); var T = sc.nextLine().toInt var result:Array[String] = new Array[String](T) for(k<-0 to T-1) { var N = sc.nextLine().toInt result(k) = "YES" var array = Array.ofDim[Char](N,N) for (i <-0 to N-1) { //Sort the row while reading it array(i)=sc.nextLine().toCharArray().sorted } for(i<-0 to N-2) for(j<-0 to N-1) {//since we have sorted the row, we need to only check if columns are sorted if(array(i)(j) > array(i+1)(j)) result(k) = "NO" } } for(k<-0 to T-1) { println(result(k)) } } } |