Created
March 27, 2019 11:09
-
-
Save prampcontent/b10cb25b274e09680eaae5875960c7ee to your computer and use it in GitHub Desktop.
ShortestCellPath-Java
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.*; | |
| import java.util.*; | |
| class Solution { | |
| static int shortestCellPath(int[][] grid, int sr, int sc, int tr, int tc) { | |
| int[] dr = {-1, 0, 1, 0}; | |
| int[] dc = {0, -1, 0, 1}; | |
| int row = grid.length; | |
| int col = grid[0].length; | |
| Queue<int[]> q = new LinkedList<>(); // a queue of an array including r, c, length | |
| int[] st = new int[]{sr, sc, 0}; | |
| q.add(st); | |
| // mark as seen | |
| grid[sr][sc] = -1; | |
| while (!q.isEmpty()) { | |
| int[] cur = q.poll(); | |
| if (cur[0] == tr && cur[1] == tc) { | |
| return cur[2]; | |
| } | |
| for (int i = 0; i < 4; i++) { | |
| int r = cur[0] + dr[i]; | |
| int c = cur[1] + dc[i]; | |
| int len = cur[2] + 1; | |
| if (isValid(r, c, row, col) && grid[r][c] == 1) { | |
| q.add(new int[]{r, c, len}); | |
| grid[r][c] = - 1; | |
| } | |
| } | |
| } | |
| return -1; | |
| } | |
| private static boolean isValid(int x, int y, int numRow, int numCol) { | |
| return x >= 0 && x < numRow && y >= 0 && y < numCol; | |
| } | |
| public static void main(String[] args) { | |
| int[][] grid = { | |
| {1,1,1,1}, | |
| {0,0,0,1}, | |
| {1,1,1,1} | |
| }; | |
| int sr = 0, sc = 0, tr = 2, tc = 0; | |
| int shortestPath = shortestCellPath(grid, sr, sc, tr, tc); | |
| System.out.println(shortestPath); | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment