Untitled

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

using namespace std;

int shortestPath(vector<vector<int>>& grid, pair<int, int> start) {
    vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    queue<pair<pair<int, int>, int>> q;
    q.push({start, 0});
    vector<pair<int, int>> visited;
    
    while (!q.empty()) {
        auto front = q.front();
        q.pop();
        int x = front.first.first;
        int y = front.first.second;
        int dist = front.second;
        
        if (grid[x][y] == 0) {
            return dist;
        }
        
        for (auto dir : directions) {
            int nx = x + dir.first;
            int ny = y + dir.second;
            if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()) {
                if (find(visited.begin(), visited.end(), make_pair(nx, ny)) == visited.end()) {
                    visited.push_back({nx, ny});
                    q.push({{nx, ny}, dist + 1});
                }
            }
        }
    }
    
    return -1; // Cannot reach ground level
}

int minDiggingNeeded(vector<vector<int>>& grid) {
    pair<int, int> start;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == 2) {
                start = {i, j};
                break;
            }
        }
    }
    
    int minDigging = INT_MAX;
    minDigging = min(minDigging, shortestPath(grid, start));
    
    return minDigging;
}

int main() {
    vector<vector<int>> grid = {
        {1, 1, 1, 1, 1},
        {1, 1, 1, 0, 1},
        {0, 1, 0, 0, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 1, 1, 1},
        {1, 1, 2, 1, 0},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {0, 1, 1, 1, 1},
        {1, 1, 0, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1}
    };

    int minDigging = minDiggingNeeded(grid);
    cout << minDigging << endl;
    
    return 0;
}