Hit.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Hit {
 
    static int arr[][], N;
 
    public static void main(String args[]) throws Exception {
        BufferedReader ob = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(ob.readLine());
        arr = new int[N][N];
        int arrCopy[][] = new int[N][N];
        String inps[];
        for (int i = 0; i < N; i++) {
            inps = ob.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(inps[j]);
            }
        }
        //copying
        for (int i = 0; i < N; i++) {
            System.arraycopy(arr[i], 0, arrCopy[i], 0, N);
        }
        //checking first row
        boolean case1, case2;
        case1 = case2 = false;
        for (int i = 0; i < N; i++) {
            if (arr[0][i] == 1) {
                if (rowPath(0, i)) {
                    case1 = true;
                    break;
                }
            }
        }
        //pasting
        for (int i = 0; i < N; i++) {
            System.arraycopy(arrCopy[i], 0, arr[i], 0, N);
        }
        //checking first column
        for (int i = 0; i < N; i++) {
            if (arr[i][0] == 2) {
                if (columnPath(i, 0)) {
                    case2 = true;
                    break;
                }
            }
        }
        if (case1 && case2) {
            System.out.println("AMBIGUOUS");
        } else if (case1) {
            System.out.println("1");
        } else if (case2) {
            System.out.println("2");
        } else {
            System.out.println("0");
        }
    }
 
    static boolean rowPath(int r, int c) {
        if (arr[r][c] == 0 || arr[r][c] == 2) {
            return false;
        }
        if (r == N - 1) {
            return true;
        }
        boolean r1, r2, r3;
        arr[r][c]=0;
        r1 = r3 = false;
        if (c > 0) {
            r1 = rowPath(r + 1, c - 1);
            if (!r1) {
                arr[r + 1][c - 1] = 0;
            }
        }
        r2 = rowPath(r + 1, c);
        if (!r2) {
            arr[r + 1][c] = 0;
        }
        if (c < N - 1) {
            r3 = rowPath(r + 1, c + 1);
            if (!r3) {
                arr[r + 1][c + 1] = 0;
            }
        }
        return r1 || r2 || r3;
    }
 
    static boolean columnPath(int r, int c) {
        if (arr[r][c] == 0 || arr[r][c] == 1) {
            return false;
        }
        if (c == N - 1) {
            return true;
        }
        if (arr[r][c] == 2) {
            boolean r1, r2, r3;
            arr[r][c]=0;
            r1 = r3 = false;
            if (r > 0) {
                r1 = columnPath(r - 1, c + 1);
                if (!r1) {
                    arr[r - 1][c + 1] = 0;
                }
            }
            r2 = columnPath(r, c + 1);
            if (!r2) {
                arr[r][c + 1] = 0;
            }
            if (r < N - 1) {
                r3 = columnPath(r + 1, c + 1);
                if (!r3) {
                    arr[r + 1][c + 1] = 0;
                }
            }
            return r1 || r2 || r3;
        }
        return false;
    }
}