Untitled

 avatar
unknown
plain_text
5 months ago
1.3 kB
4
Indexable
class Solution {
    static int dx[] = {1,-1,0,0};
	static int dy[] = {0,0,1,-1};
	public int minimumTime(int[][] grid) {
		int m = grid.length, n = grid[0].length;
		boolean[][] visited = new boolean[m][n];
		boolean flag = (grid[0][1] <= 1 || grid[1][0] <= 1 ? true : false);
		if(!flag)
			return -1;
		PriorityQueue<Point> pq = new PriorityQueue<>((a, b)->{
			return a.time - b.time;
		});
		pq.add(new Point(0, 0, 0));
		visited[0][0] = true;
		while(!pq.isEmpty()){
			Point p = pq.poll();
			for(int i = 0; i < 4; i++){
				int tempX = p.x + dx[i];
				int tempY = p.y + dy[i];
				if(tempX >= 0 && tempX < m && tempY >= 0 && tempY < n && !visited[tempX][tempY]){
					int temp = -1;
					if(grid[tempX][tempY] <= p.time + 1)
						temp = p.time + 1;
					else 
                        temp = grid[tempX][tempY] + (((grid[tempX][tempY] - p.time)&1) == 0 ? 1 : 0);
					if(tempX == m - 1 && tempY == n - 1)
						return temp;
                    pq.add(new Point(tempX, tempY, temp));
                    visited[tempX][tempY] = true;
				}
			}
		}
		return -1;
    }
	
	public static class Point{
		int x, y;
		int time;
		public Point(int x, int y, int time){
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}
Editor is loading...
Leave a Comment