class Solution {
public:

    bool valid (int r , int c , vector<vector<int>>& grid)
    {
        return r >= 0 && r < grid.size() && c >=0 && c < grid[0].size() && grid[r][c] != 1;
    }

    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {

        int rows = grid.size();
        if (!rows) return -1;
        int cols = grid[0].size();
        if (!cols) return -1;

        pair <int , int> src = {0,0};
        pair <int , int> dist = {rows - 1, cols - 1};

        if (grid[src.first][src.second] == 1 || grid[dist.first][dist.second] == 1 ) return -1;
        vector < vector <int> > dir = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
        queue <pair <int,int> > q;
       vector < vector <bool> > vis (rows, vector <bool> (cols, false));
        int res = 1;
        q.push(src);
        vis[src.first][src.second] = true;
        while (!q.empty())
        {
            int sz = q.size();

            for (int i =  0 ; i < sz ; i++)
            {
                pair <int , int> cur = q.front();
                q.pop();

                if (cur == dist)
                    return res;

                int cur_r = cur.first;
                int cur_c = cur.second;



                for (int d = 0 ; d < dir.size(); d ++)
                {
                    int n_r = cur_r + dir[d][0];
                    int n_c = cur_c + dir[d][1];

                    if (valid(n_r , n_c , grid) && !vis[n_r][n_c])
                    {
                        q.push({n_r,n_c});
                        vis[n_r][n_c] = true;
                    }
                }
            }
            res++;
        }
        return -1;
    }
};

class Solution {
public:
    bool valid (int r , int c , vector<vector<int>>& grid)
    {
        return r >= 0 && r < grid.size() && c >=0 && c < grid[0].size() ;
    }
    int shortestPath(vector<vector<int>>& grid, int k) {

        int rows = grid.size();
        if (!rows) return -1;
        int cols = grid[0].size();
        if (!cols) return -1;

       // pair <int , int> src = {{0,0},k};
        pair <int , int> dist = {rows - 1, cols - 1};

       // if (grid[src.first][src.second] == 1 || grid[dist.first][dist.second] == 1 ) return -1;

        vector < vector <int> > dir = {{1,0},{-1,0},{0,1},{0,-1}};

        queue < pair < pair <int,int> , int > > q;

        vector<vector<vector<int>>> vis(rows, vector<vector<int>>(cols, vector<int>(k+1,0)));

        int res = 0;
        q.push({{0,0},k});

        vis[0][0][k] = true;
        while (!q.empty())
        {
            int sz = q.size();

            for (int i =  0 ; i < sz ; i++)
            {
                pair < pair <int,int> , int > cur = q.front();
                q.pop();

                int cur_r = cur.first.first;
                int cur_c = cur.first.second;
                int cur_k = cur.second;

                pair <int , int> cur_point = {cur_r, cur_c};

                if (cur_point == dist)
                    return res;

                for (int d = 0 ; d < dir.size(); d ++)
                {
                    int n_r = cur_r + dir[d][0];
                    int n_c = cur_c + dir[d][1];

                    if (valid(n_r , n_c , grid)  )
                    {
                        if ( grid[n_r][n_c] == 1 && cur_k && !vis[n_r][n_c][cur_k -1])
                        {
                            q.push({{n_r,n_c},cur_k - 1});
                            vis[n_r][n_c][cur_k - 1] = true;

                        }

                        else if (grid[n_r][n_c] == 0 && !vis[n_r][n_c][cur_k])
                        {
                            q.push({{n_r,n_c},cur_k});
                            vis[n_r][n_c][cur_k ] = true;

                        }



                    }
                }
            }
            res++;
        }
        return -1;

    }
};