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

int fun (vector < vector <char> > &grid)
{
    vector < vector <bool> > vis(grid.size(), vector <bool> (grid[0].size(), false));

    vector < vector <int> > dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    queue < pair <int,int> > q;
    vis[0][0] = true;
    q.push({0,0});
    int steps = 1;
    while (!q.empty())
    {
        int sz = q.size();
        while (sz--)
        {
             pair <int,int> cur = q.front();
            q.pop();
            int cur_x = cur.first;
            int cur_y = cur.second;
            for (int i = 0 ; i < 4 ; i++)
            {
                int new_x = cur_x + dir[i][0];
                int new_y = cur_y + dir[i][1];

                if (valid(new_x,new_y,grid,vis))
                {
                    if (grid[new_x][new_y] == 'X')
                        return steps;
                    vis[new_x][new_y] = true;
                    q.push({new_x,new_y});
                }

            }
        }
       steps++;

    }
    return -1;

}


int main() {
   vector < vector <char> > grid = { {'O', 'O', 'O', 'O'},
                                     {'D', 'O', 'D', 'O'},
                                     {'O', 'O', 'O', 'O'},
                                     {'X', 'D', 'D', 'O'}};

    cout << fun (grid);
}