Monday, 17 August 2015

Crazy Matrix

Standard
Praveen went crazy yesterday and created an arbitrary matrix consisting of 0, 1 or 2. There was no rule observed in forming this matrix. But then he made up some rules himself.
If there are adjacent 1's, they are said to be connected. Similarly, if there are adjacent 2's, they are said to be connected. Here adjacent means all the surrounding positions along with the diagonal positions.
Now given a matrix of 0, 1 or 2, do your computation according to the following rules:
  1. If there is a path from any position in top row to any position in bottom row consisting only of 1, then print 1.
  2. If there is a path from any position in first column to any position in last column consisting only of 2, then print 2.
  3. If both Rule 1 & Rule 2 are true, print AMBIGUOUS.
  4. If none of Rule 1, Rule 2 or Rule 3 satisfies, print 0.
Input format
First line of input contains a positive integer N, the size of matrix. Then N line follows, each containing N integers which are either 0, 1 or 2.
Output format
Print a single line containing the output according to the rule mentioned. Clearly, the output can only be 0, 1, 2 or AMBIGUOUS.
Input constraint
1 <= N <= 100
Example
4
0 0 0 0
2 0 1 0
0 2 1 2
0 1 2 0
Here the output is 2, as there is a connected path of 2 from first column to last column.

Sample Input
3
0 0 1
0 1 2
2 2 1
Sample Output
AMBIGUOUS
Explanation
In the sample input, there is a connected path of 1 from first row to last row, and there is a connected path of 2 from first column to last column as well. So, the result is 'AMBIGUOUS'.

Time Limit: 2 sec(s) for all input files combined.
Memory Limit: 256 MB
Source Limit: 1024 KB 
 
Code : 
 
/* IMPORTANT: class must not be public. */


import java.util.Scanner;



class TestClass {
    static int visited[][];
    static int N;
    static int[][] matrix;
    public static void main(String args[] ) throws Exception {
       
         Scanner sc = new Scanner(System.in);
         N = sc.nextInt();
         matrix = new int[N][N];
         visited = new int[N][N];
        
         for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        
      
       boolean one = false;
       boolean two = false;
       
        //Reset the visted matrix
        for(int i = 0; i < N; i++) {
            for (int j = 0 ; j < N ; j++) {               
                visited[i][j] = 0;
            }
        }
        for (int i = 0; i < N; i++) {
            if(matrix[0][i] == 1) {
                one = connectedOne(matrix, 0, i);
                if(one) {
                    //System.out.println("Two chain found");
                    break;
                }
            }
        }
       
        // Reset the visited matrix
        for(int i = 0; i < N; i++) {
            for (int j = 0 ; j < N ; j++) {               
                visited[i][j] = 0;
            }
        }
       
        for (int i = 0; i < N; i++) {
            if(matrix[i][0] == 2) {
                two = connectedTwo(matrix, i, 0);
                if(two) {
                    //System.out.println("Two chain found");       
                    break;
                }
            }
        }
       
        if(one && two) {
            System.out.println("AMBIGUOUS");
        } else if(one) {
            System.out.println("1");
        } else if(two) {
            System.out.println("2");
        } else {
            System.out.println("0");
        }
    }
   
    static boolean connectedOne(int[][] matrix, int x, int y) {
        if(isSafe(matrix, x, y) && x == (N - 1)) {
            if(matrix[x][y] == 1) {
                return true;
            } else {
                return false;
            }
               
        }   
       
        if(isSafe(matrix, x, y) == true && matrix[x][y] == 1) {   
           
            visited[x][y] = 1;
            if(connectedOne(matrix , x, y+1) == true) {
                return true;
            }
            if(connectedOne(matrix , x+1, y) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x+1, y+1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x-1, y) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x-1, y+1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x-1, y-1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x, y-1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x+1, y-1) == true) {
                return true;
            }
           
            return false;
           
        }
       
        return false;
       
    }
   
    static boolean connectedTwo(int[][] matrix, int x, int y) {
       
        if(isSafe(matrix, x, y) && y == (N - 1) ) {
            if(matrix[x][y] == 2) {
                return true;
            } else {
                return false;
            }
        }
       
       
       
        if(isSafe(matrix, x, y) == true && matrix[x][y] == 2) {
           
            visited[x][y] = 1;
           
            if(connectedTwo(matrix , x, y+1) == true) {
                return true;
            }
            if(connectedTwo(matrix , x+1, y) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x+1, y+1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x-1, y) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x-1, y+1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x-1, y-1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x, y-1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x+1, y-1) == true) {
                return true;
            }
           
            return false;
           
        }
       
        return false;       
    }
   
     private static boolean isSafe(int[][] matrix, int x, int y) {
           
            if(x < matrix[0].length && x >= 0 && y < matrix[0].length && y >= 0
                     && visited[x][y] == 0) {
                return true;
            }
            return false;       
        }
}
 

0 comments:

Post a Comment