fork download
copy 
  1. // Microsoft OA 51 LPA
  2. // Find min distance between 2 and 3 in a grid with multiple 2 0 and 3
  3. // Multisource BFS 
  4.  
  5. import java.util.LinkedList;
  6. import java.util.Queue;
  7. import java.util.Scanner;
  8.  
  9. class PairInt {
  10.  
  11.     int first;
  12.     int second;
  13. 	int parentX;
  14. 	int parentY;
  15.  
  16.     public PairInt(int first, int second, int parentX, int parentY) {
  17.         this.first = first;
  18.         this.second = second;
  19.         this.parentX = parentX;
  20.         this.parentY = parentY;
  21.     }
  22.  
  23. }
  24.  
  25. public class Main {
  26.     public static void main(String[] args) {
  27.  
  28.         Scanner scanner = new Scanner(System.in);
  29.  
  30.         int r = scanner.nextInt();
  31.         int c = scanner.nextInt();
  32.  
  33.         int[][] grid = new int[r][c];
  34.  
  35.         Queue<PairInt> queue = new LinkedList<>(); // we can also use ArrayDeque implementation but this is more common
  36.  
  37.         boolean[][] seen = new boolean[r][c];
  38.  
  39.         for(int i = 0; i < r; i++) {
  40.             for(int j = 0; j < c; j++) {
  41.  
  42.                 grid[i][j] = scanner.nextInt();
  43.  
  44.                 if(grid[i][j] == 2) {
  45.                     queue.offer(new PairInt(i, j, i, j));
  46.                     seen[i][j] = true;
  47.                 }
  48.             }
  49.         }
  50.  
  51.         int currLevel = 0;
  52.  
  53.         int[] dirs = {-1, 0, 1, 0, -1};
  54.  
  55.         while(!queue.isEmpty()) {
  56.  
  57.             int levelSize = queue.size();
  58.  
  59.             for(int i = 0; i < levelSize; i++) {
  60.  
  61.                 PairInt curr = queue.poll();
  62.  
  63.                 int currX = curr.first;
  64.                 int currY = curr.second;
  65.  
  66.                 for(int j = 0; j < 4; j++) {
  67.  
  68.                     int newX = currX + dirs[j];
  69.                     int newY = currY + dirs[j + 1];
  70.  
  71.                     if(newX >= 0 && newX < r && newY >= 0 && newY < c && !seen[newX][newY]) {
  72.                         if(grid[newX][newY] == 0) {
  73.                             queue.offer(new PairInt(newX, newY, curr.parentX, curr.parentY));
  74.                             seen[newX][newY] = true;
  75.                         } else if (grid[newX][newY] == 3) {
  76.                             System.out.println("Min. Distance: " + (currLevel + 1));
  77.                             System.out.println("(O indexed) From (" + curr.parentX + ", " + curr.parentY + ") to (" + newX + ", " + newY + ")");
  78.                             return;
  79.                         }
  80.                      }
  81.                 }
  82.             }
  83.  
  84.             currLevel++;
  85.         }
  86.  
  87.     }
  88. }
Success #stdin #stdout 0.2s 61172KB
comments (?)
stdin
copy 
5 3
2 2 0
2 0 3
0 0 0
2 0 3
2 2 3
stdout
copy 
Min. Distance: 1
(O indexed) From (4, 1) to (4, 2)
https://ideone.com/yi6a7q
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!