Problem

Given a 2D array of black and white pixels, find the shortest path from the top left corner of the array to the bottom right corner.
Input: [[0,0,0,1],
        [0,1,0,0],
        [1,0,0,0]]
Output: 6

Solution

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int shortestPath(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dist(m, vector<int>(n, -1));
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    dist[0][0] = 0;
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        int x = curr.first;
        int y = curr.second;
        if (x == m - 1 && y == n - 1) {
            return dist[x][y];
        }
        if (x > 0 && grid[x - 1][y] == 0 && dist[x - 1][y] == -1) {
            q.push(make_pair(x - 1, y)); dist[x - 1][y] = dist[x][y] + 1;
        }
        if (x < m - 1 && grid[x + 1][y] == 0 && dist[x + 1][y] == -1) {
            q.push(make_pair(x + 1, y));
            dist[x + 1][y] = dist[x][y] + 1;
        }
        if (y > 0 && grid[x][y - 1] == 0 && dist[x][y - 1] == -1) {
            q.push(make_pair(x, y - 1));
            dist[x][y - 1] = dist[x][y] + 1;
        }
        if (y < n - 1 && grid[x][y + 1] == 0 && dist[x][y + 1] == -1) {
            q.push(make_pair(x, y + 1));
            dist[x][y + 1] = dist[x][y] + 1;
        }
    }
    return -1;
}

int main() {
    vector<vector<int>> grid = {{0, 0, 0, 1},
                                {0, 1, 0, 0},
                                {1, 0, 0, 0}};
    cout << shortestPath(grid) << endl;
    return 0;
}