Untitled
unknown
plain_text
a year ago
3.2 kB
8
Indexable
import java.io.*; import java.util.*; class Queue { public static int MAX = 10000000; private int[] A; private int front, rear; Queue() { A = new int[MAX]; front = 0; rear = -1; } boolean isFull() { if (rear - front == MAX - 1) { return true; } return false; } boolean isEmpty() { if (front > rear) { return true; } return false; } void enqueue(int a) { if (!isFull()) { rear++; A[rear] = a; } } int dequeue() { if(!isEmpty()) { front++; return A[front-1]; } return -1; } int peek() { if(!isEmpty()) { return A[front]; } return -1; } void reset() { front = 0; rear = -1; } } public class Solution { public static int N, M, res, startx, starty, endx, endy; public static int[][] map, visited; public static Queue queue = new Queue(); public static int[] dx = {-1, 0, 1, 0}; public static int[] dy = {0, 1, 0, -1}; public static boolean bfs(int h) { queue.enqueue(startx); queue.enqueue(starty); visited[startx][starty] = 1; while(!queue.isEmpty()) { int newx = queue.dequeue(); int newy = queue.dequeue(); if (newx == endx && newy == endy) { return true; } for (int k = 0; k < 4; k++) { int nexty = newy + dy[k]; for (int i = 0; i <= h; i++) { int nextx = newx + dx[k]*i; if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < M && visited[nextx][nexty] == 0 && map[nextx][nexty] != 0) { queue.enqueue(nextx); queue.enqueue(nexty); visited[nextx][nexty] = 1; } } } } return false; } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); res = -1; map = new int[N][M]; startx = N-1; starty = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { map[i][j] = sc.nextInt(); if (map[i][j] == 3) { endx = i; endy = j; } } } for (int h = 0; h < N; h++) { queue.reset(); visited = new int[N][M]; if (bfs(h)) { res = h; break; } } System.out.println(res); sc.close(); } }
Editor is loading...
Leave a Comment