#include #include #include using namespace std; char matrix[4][4] = {0}; int nx[] = {1, 0, -1, 0}; int ny[] = {0, 1, 0, -1}; char smb[] = {'R', 'D', 'L', 'U'}; bool used[4][4] = {0}; int mind = 0; vector path; bool dfs(int i, int j) { if(path.size() > mind && i == 3 && j == 3) { for (int s = 0; s < path.size(); ++s) { cout << path[s]; } path.clear(); cout << endl; return 1; } for(int m = 0; m < 4; ++m) { if (i + ny[m] < 0 || i + ny[m] > 3 || j + nx[m] < 0 || j + nx[m] > 3 || matrix[i + ny[m]][j + nx[m]] == '#') continue; path.push_back(smb[m]); matrix[i + ny[m]][j + nx[m]] = '#'; if (dfs(i + ny[m], j + nx[m])) { return 1; } matrix[i + ny[m]][j + nx[m]] = '.'; path.pop_back(); } return 0; } int main() { freopen("input.txt", "r", stdin); //freopen("nsp.in", "r", stdin); //freopen("nsp.out", "w", stdout); char symb; for(;;) { for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { cin >> matrix[i][j]; } } int dp[4][4] = {0}; for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j) dp[i][j] = 1000; dp[0][0] = 0; dp[3][3] = 1111; for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { if (i > 0 && matrix[i - 1][j] != '#') dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1); if (j > 0 && matrix[i][j - 1] != '#') dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1); } } if (dp[3][3] == 1111 ) { cout << -1 << endl; } mind = dp[3][3]; matrix[0][0] = '#'; if (dfs(0, 0) == 0) { cout << -1 << endl; } if (cin >> symb) { cin >> symb >> symb >> symb; } else { break; } } return 0; }