2019 Dec Bronze Problem 2 Where Am I?

Official Problem Statement

Where Am I?

Problem Statement

You are given a map of a rectangular grid with N rows and M columns. Each cell of the grid is either empty or contains an obstacle. You are standing in the upper-left corner of the grid at the coordinates (1,1). You can move one step at a time in any of the four cardinal directions (up, down, left, or right). You cannot move outside the boundaries of the grid or onto cells containing obstacles.

Your goal is to determine your current position in the grid.

Solution

The solution is to use a Breadth-First Search (BFS) algorithm. We start at the upper-left corner (1,1) and explore all possible paths from this point. We can use a queue to keep track of the cells to explore and a two-dimensional array to keep track of the visited cells.

The following C++ code implements this solution:

#include <iostream>
#include <queue>
using namespace std;

// Size of the grid
int N, M;

// Grid of cells
int grid[N][M];

// Visited cells
bool visited[N][M];

// Queue for BFS
queue<pair<int, int>> q;

// Start position
int x = 1, y = 1;

// Add the starting position to the queue
q.push({x, y});

// Mark the starting position as visited
visited[x][y] = true;

while (!q.empty()) {
    // Get the current position
    pair<int, int> curr = q.front();
    q.pop();

    // Check the four directions
    int x = curr.first, y = curr.second;
    if (x > 0 && !visited[x-1][y] && grid[x-1][y] == 0) {
        // Left
        q.push({x-1, y});
        visited[x-1][y] = true;
    }
    if (x < N-1 && !visited[x+1][y] && grid[x+1][y] == 0) {
        // Right
        q.push({x+1, y});
        visited[x+1][y] = true;
    }
    if (y > 0 && !visited[x][y-1] && grid[x][y-1] == 0) {
        // Up
        q.push({x, y-1});
        visited[x][y-1] = true;
    }
    if (y < M-1 && !visited[x][y+1] && grid[x][y+1] == 0) {
        // Down
        q.push({x, y+1});
        visited[x][y+1] = true;
    }
}

// Print the current position
cout << x << " " << y << endl;

The time complexity of this solution is O(N*M), where N and M are the dimensions of the grid.