solution for CF VK Cup 2017, round 1, problem C

cf_vk17_1_c.cpp

// solution for CF VK Cup 2017, round 1, problem C
// http://codeforces.com/contest/769/problem/C
// The idea:
// Front step) we go greedy until it is possible to go back from the current cell
// This check is done by the help of shortest distance matrix d 
// Back step) Find the lexigocraphically optimal backward path following distance matrix d
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
typedef long double ldouble;

const string c = "DLRU";
int x[] = {1, 0, 0, -1};
int y[] = {0, -1, 1, 0};

int n, m, K;
vector<string> field;

bool possible(int i, int j) {
    if (i >= 0 && i < n && j >=0 && j < m) {
        return field[i][j] != '*';
    }
    return false;
}

vector< vector<int> > d;
void bfs(int i, int j) {
    d[i][j] = 0;
    queue< pair<int,int> > q;
    q.push( make_pair(i, j) );
    while (!q.empty()) { 
        auto cur = q.front(); q.pop();
        i = cur.first; j = cur.second;
        int v = d[i][j];
        for (int k = 0; k < 4; ++k)
            if (possible(i + x[k], j + y[k]) && d[i + x[k]][j + y[k]] == numeric_limits<int>::max()) {
                d[i+x[k]][j+y[k]] = v+1;
                q.push( make_pair(i+x[k], j+y[k]) );
            }

    }
}

stringstream ss;

void findFrontPath(int& i, int& j, int& l) {
    while (K - l > d[i][j]) {
        for (int k = 0; k < 4; ++k)
            if (possible(i + x[k], j + y[k])) {
                i += x[k]; j += y[k];
                ss << c[k];
                ++l;
                break;
            }
    }
}

void findBackPath(int& i, int& j, int l) {
    while (l < K) {
        for (int k = 0; k < 4; ++k) {
            if (possible(i + x[k], j + y[k]) && d[i][j] >  d[i + x[k]][j + y[k]]) {
                i += x[k];
                j += y[k];
                ss << c[k];
                ++l;
                break;
            }
        }
    }
}

int main(int, char**) {
    std::ios::sync_with_stdio(false);

    cin >> n >> m >> K;
    int i0, j0;
    field.resize(n);
    d.resize(n, vector<int>(m, numeric_limits<int>::max()));
    for (int i = 0; i < n; ++i) {
        cin >> field[i];
        for (int j = 0; j < m; ++j) {
            if (field[i][j] == 'X') {
                i0 = i; j0 = j;
            }
        }
    }

    // check for the case when there is no choice
    int p = 0;
    for (int k = 0; k < 4; ++k) 
        if (possible(i0 + x[k], j0 + y[k]))
            ++p;    
    if (p == 0) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }    

    bfs(i0, j0);
    
    int l = 0;
    int i = i0, j = j0;
    findFrontPath(i, j, l);
    findBackPath(i, j, l);
    if (i == i0 && j == j0) {
        cout << ss.str();
    } else
        cout << "IMPOSSIBLE";
    cout << endl;
    return 0;
}