Validate the maze java spoj

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Main { static class Point { public int row; public int col; public Point(int row, int col) { this.row = row; this.col = col; } } public static int rowMatrix = 0; public static int colMatrix = 0; public static boolean isValid(int row, int col, String[]matrix) { return row >= 0 && row < rowMatrix && col >= 0 && col < colMatrix && matrix[row].charAt(col) == '.'; } public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk = new StringTokenizer(br.readLine()); int tc = Integer.parseInt(tk.nextToken()); for(int i = 0; i < tc; i ++) { tk = new StringTokenizer(br.readLine()); int m = Integer.parseInt(tk.nextToken()); int n = Integer.parseInt(tk.nextToken()); rowMatrix = m; colMatrix = n; /* // Read input like this will lead to TLE!!! char[][] matrix = new char[m][n]; for(int j = 0;j< m; j ++) { int value = 0; int run = 0; while((value = br.read()) != 10){ // 10 is endLine matrix[j][run] = (char)value; run++; } }*/ // This one otherwise is OK! String[] matrix = new String[m]; for(int j = 0; j < m; j ++) { matrix[j] = br.readLine(); } int cnt = 0; //List contains 2 coordinate of matrix entries ArrayList<Integer> coordinate = new ArrayList<>(); for(int j = 0; j < m; j ++) { for(int k = 0; k < n; k ++) { if((j == 0 || j == m-1 || k == 0 || k == n-1) && matrix[j].charAt(k) == '.') { cnt++; coordinate.add(j); coordinate.add(k); } } } if(cnt == 2) { int ra = coordinate.get(0); int ca = coordinate.get(1); int rowDes = coordinate.get(2); int colDes = coordinate.get(3); boolean[][]visited = new boolean[m][n]; visited[ra][ca] = true; Queue<Point> q = new LinkedList<>(); q.add(new Point(ra,ca)); int[] dx = {-1,1,0,0}; int[] dy = {0,0,-1,1}; whileLoop: while(!q.isEmpty()) { Point v = q.poll(); int headr = v.row; int headc = v.col; for(int j = 0; j < 4; j ++) { int tempr = headr + dx[j]; int tempc = headc + dy[j]; if(isValid(tempr, tempc, matrix) && !visited[tempr][tempc]) { visited[tempr][tempc] = true; if(tempr == rowDes && tempc == colDes) { break whileLoop; } q.add(new Point(tempr, tempc)); } } } if(visited[rowDes][colDes]) System.out.println("valid"); else System.out.println("invalid"); } else { System.out.println("invalid"); } } br.close(); } }

Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.