Untitled
unknown
plain_text
2 years ago
2.7 kB
3
Indexable
import java.util.Scanner; public class Solution { public static int[] dx = {-1,0,1,0}; public static int[] dy = {0,1,0,-1}; public static class Queue{ public int arr[]; public int front,rear; public int size; public Queue (int capacity){ rear = -1; front = -1; size = 0; arr = new int[capacity]; } public boolean isEmpty(){ return size == 0; } public boolean isFull(){ return size == arr.length; } public boolean enqueue(int item){ if(!isFull()){ rear++; arr[rear] = item; size++; return true; } return false; } public int dequeue(){ int value = -1; if(!isEmpty()){ front++; value = arr[front]; size--; return value; } return value; } public void Show(){ for(int i =front+1;i<=rear;i++){ System.out.println(arr[i]+" "); } } } public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int Testcase = sc.nextInt(); for (int t = 1; t <= Testcase; t++) { int N = sc.nextInt(); int M = sc.nextInt(); int[][] arr = new int[N][M]; int rowStart = sc.nextInt()-1; int colStart = sc.nextInt()-1; int rowEnd = 0; int colEnd = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { arr[i][j] = sc.nextInt(); if(arr[i][j] == 2 ){ rowEnd = i; colEnd = j; } } } Queue q1 = new Queue(50000000); Queue q2 = new Queue(50000000); boolean[][] visit = new boolean[N][M]; int result = bfs(rowStart,colStart,rowEnd, colEnd, arr,visit,arr, q1, q2, N, M); System.out.println("Case #" + t); if(result == -1){ System.out.println("-1 -1" ); } else{ System.out.println(result + " " + result); } } } private static int bfs(int rowStart, int colStart, int rowEnd,int colEnd,int[][] arr, boolean[][] visit, int[][] step, Queue q1,Queue q2, int N,int M) { q1.enqueue(rowStart); q2.enqueue(colStart); visit[rowStart][colStart] = true; while (!q1.isEmpty() && !q2.isEmpty()) { int curR = q1.dequeue(); int curC = q2.dequeue(); if(visit[rowEnd-1][colEnd] && visit[rowEnd][colEnd+1] && visit[rowEnd+1][colEnd] && visit[rowEnd][colEnd-1]){ return step[curR][curC]; } for(int i =0;i<4;i++){ int nextR = curR + dx[i]; int nextC = curC + dy[i]; if(nextC>=0 && nextC<M && nextR>=0 && nextR<N && !visit[nextR][nextC] && arr[nextR][nextC]==1){ visit[nextR][nextC] = true; step[nextR][nextC] = step[curR][curC] + 1; q1.enqueue(nextR); q2.enqueue(nextC); } } } return -1; } }
Editor is loading...