SRM 707 DIV 2 500 Steps Construct

Problem with interesting constraints… hopefully figured this out during SRM this time.

using namespace std;

class StepsConstruct {
    int rows;
    int cols;
    char getD(char c) {
        if (c == 'R') return 'L';
        if (c == 'L') return 'R';
        if (c == 'U') return 'D';
        if (c == 'D') return 'U';
        return 'R';
    }
public:
    string construct(vector <string> board, int k) {
        if (board[0][0] == '#') return "";
        rows = (int)board.size(); cols = (int)board[0].size();
        set<pair<int,int>> visited;
        vector<string> paths;
        queue<pair<int, int>> q;
        queue<string> qp;
        q.push(make_pair(0, 0));
        qp.push("");
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;
            string curp = qp.front();
            qp.pop();
            
            int dx[] = {1, -1, 0, 0};
            int dy[] = {0, 0, 1, -1};
            char steps[] = {'D', 'U', 'R', 'L'};
            for (int i = 0; i < 4; ++i) {
                pair<int,int> cur = {x + dx[i], y + dy[i]};
                if(cur.first < 0 || cur.second < 0 || cur.first >= rows || cur.second >= cols)
                    continue;
                if(visited.count(cur))
                    continue;
                if (board[cur.first][cur.second] == '#') {
                    visited.insert(cur);
                    continue;
                }
                
                string p = curp + steps[i];
                if (cur.first == rows - 1 && cur.second == cols - 1) {
                    paths.push_back(p);
                    continue;
                }

                visited.insert(cur);
                qp.push(p);
                q.push(cur);
            }
        }
        
        int minsteps = INT_MAX;
        for (auto path : paths) {
            minsteps = std::min((int)path.size(), minsteps);
        }
        if (minsteps > k) return "";
        
        string c;
        for (auto path : paths) {
            int steps = (int)path.size();
            if (steps <= k && ((k - steps) % 2 == 0)) {
                int d = k - steps;
                string prefix = "";
                char c = path[0];
                for (int i = 0; i < d; ++i) {
                    prefix += c;
                    c = getD(c);
                }
                return prefix + path;
            }
        }
        return "";
    }
}