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.  
  14.     public PairInt(int first, int second) {
  15.         this.first = first;
  16.         this.second = second;
  17.     }
  18.  
  19. }
  20.  
  21. public class Main {
  22.     public static void main(String[] args) {
  23.  
  24.         Scanner scanner = new Scanner(System.in);
  25.  
  26.         int r = scanner.nextInt();
  27.         int c = scanner.nextInt();
  28.  
  29.         int[][] grid = new int[r][c];
  30.  
  31.         Queue<PairInt> queue = new LinkedList<>(); // we can also use ArrayDeque implementation but this is more common
  32.  
  33.         boolean[][] seen = new boolean[r][c];
  34.  
  35.         for(int i = 0; i < r; i++) {
  36.             for(int j = 0; j < c; j++) {
  37.  
  38.                 grid[i][j] = scanner.nextInt();
  39.  
  40.                 if(grid[i][j] == 2) {
  41.                     queue.offer(new PairInt(i, j));
  42.                     seen[i][j] = true;
  43.                 }
  44.             }
  45.         }
  46.  
  47.         int currLevel = 0;
  48.  
  49.         int[] dirs = {-1, 0, 1, 0, -1};
  50.  
  51.         while(!queue.isEmpty()) {
  52.  
  53.             int levelSize = queue.size();
  54.  
  55.             for(int i = 0; i < levelSize; i++) {
  56.  
  57.                 PairInt curr = queue.poll();
  58.  
  59.                 int currX = curr.first;
  60.                 int currY = curr.second;
  61.  
  62.                 for(int j = 0; j < 4; j++) {
  63.  
  64.                     int newX = currX + dirs[j];
  65.                     int newY = currY + dirs[j + 1];
  66.  
  67.                     if(newX >= 0 && newX < r && newY >= 0 && newY < c && !seen[newX][newY]) {
  68.                         if(grid[newX][newY] == 0) {
  69.                             queue.offer(new PairInt(newX, newY));
  70.                             seen[newX][newY] = true;
  71.                         } else if (grid[newX][newY] == 3) {
  72.                             System.out.println(currLevel + 1);
  73.                             return;
  74.                         }
  75.                      }
  76.                 }
  77.             }
  78.  
  79.             currLevel++;
  80.         }
  81.  
  82.     }
  83. }
  84.  
Success #stdin #stdout 0.18s 56584KB
comments (?)
stdin
copy 
5 3
2 2 0
2 0 3
0 0 0
2 0 3
2 2 3
stdout
copy 
1
https://ideone.com/uu6rtv
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!