Problem

In the ROR game, you play on a team that competes to destroy the opposing team’s base first, making it advantageous to reach the enemy base as quickly as possible. Suppose you’re a team member and are located at position (row: 1, column: 1) on a 5x5 map, while the enemy base is at (row: 5, column: 5). The game map is comprised of cells that can either be passable or blocked by walls. Your character can move up, down, left, or right, and cannot move outside the boundaries of the map.

Given the state of the game map maps, represented as a 2D array where 1s are passable cells and 0s are walls, implement a function solution that returns the minimum number of cells your character must pass through to reach the enemy base located at the bottom-right corner of the map. If it’s impossible to reach the enemy base due to walls blocking the way, return -1.

Constraints

maps is an n x m 2D array, where both n and m are natural numbers between 1 and 100.
n and m could be the same or different, but the case where both n and m are 1 will not be provided as input.
The character starts at the top-left corner of the map, and the enemy base is at the bottom-right corner.
The map only contains 0s and 1s, where 0 indicates a wall and 1 indicates a passable cell.

Example

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

Explanation of Examples

Example 1:
- The character can reach the enemy base by traversing 11 cells, following a path that circumvents walls effectively.
Example 2:
- Walls block all possible paths to the enemy base, making it impossible to reach, thus the function returns -1.

How to Approach?

Step1: Initialize variables in loop

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    class Point {
        int x, y, count;
        
        Point(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;

        // Directions for moving right, left, down, up
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        Deque<Point> deque = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];

        // Start BFS from the top-left corner
        deque.offer(new Point(0, 0, 1));
        visited[0][0] = true;

        while (!deque.isEmpty()) {
            Point current = deque.poll();
            
            // Check if reached the bottom-right corner
            if (current.x == n - 1 && current.y == m - 1) {
                return current.count;
            }

            // Explore four possible movements
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                // Ensure the move is within boundaries, on a walkable path, and not visited
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    deque.offer(new Point(nx, ny, current.count + 1));
                }
            }
        }

        // If there is no path to the destination, return -1
        return -1;
    }
}