Untitled

 avatar
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