122 lines
2.5 KiB
Java
122 lines
2.5 KiB
Java
package chelper;
|
|
|
|
import java.util.Arrays;
|
|
import java.util.LinkedList;
|
|
import java.util.Queue;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
|
|
public class C {
|
|
char[] dirsOrderLabels = {'D', 'L', 'R', 'U'};
|
|
int[][] dirsOrder = {
|
|
{1, 0}, //D
|
|
{0, -1}, //L
|
|
{0, 1}, //R
|
|
{-1, 0}, //U
|
|
};
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
int n = in.nextInt();
|
|
int m = in.nextInt();
|
|
int k = in.nextInt();
|
|
|
|
int startX = -1;
|
|
int startY = -1;
|
|
|
|
boolean[][] map = new boolean[n][m];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
String s = in.nextLine();
|
|
for (int j = 0; j < m; j++) {
|
|
map[i][j] = s.charAt(j) != '*';
|
|
if (s.charAt(j) == 'X') {
|
|
startX = i;
|
|
startY = j;
|
|
}
|
|
}
|
|
}
|
|
|
|
int[][] distances = new int[n][m];
|
|
for (int i = 0; i < n; i++) {
|
|
Arrays.fill(distances[i], Integer.MAX_VALUE);
|
|
}
|
|
|
|
Queue<int[]> queue = new LinkedList<>();
|
|
queue.add(new int[]{startX, startY});
|
|
distances[startX][startY] = 0;
|
|
|
|
while (!queue.isEmpty()) {
|
|
int[] posAr = queue.poll();
|
|
int x = posAr[0];
|
|
int y = posAr[1];
|
|
|
|
for (int[] dir : dirsOrder) {
|
|
int xx = x + dir[0];
|
|
int yy = y + dir[1];
|
|
|
|
if (xx < 0 || xx >= n || yy < 0 || yy >= m) {
|
|
continue;
|
|
}
|
|
|
|
if (!map[xx][yy]) {
|
|
continue;
|
|
}
|
|
|
|
if (distances[xx][yy] <= distances[x][y] + 1) {
|
|
continue;
|
|
}
|
|
|
|
distances[xx][yy] = distances[x][y] + 1;
|
|
queue.add(new int[]{xx, yy});
|
|
}
|
|
}
|
|
|
|
StringBuilder answer = new StringBuilder();
|
|
|
|
int x = startX;
|
|
int y = startY;
|
|
int timeLeft = k;
|
|
|
|
while (timeLeft >= distances[x][y] && timeLeft > 0) {
|
|
boolean ok = false;
|
|
for (int i = 0; i < 4; i++) {
|
|
int[] dir = dirsOrder[i];
|
|
int xx = x + dir[0];
|
|
int yy = y + dir[1];
|
|
|
|
if (xx < 0 || xx >= n || yy < 0 || yy >= m) {
|
|
continue;
|
|
}
|
|
|
|
if (!map[xx][yy]) {
|
|
continue;
|
|
}
|
|
|
|
if (timeLeft == distances[x][y] && distances[xx][yy] >= distances[x][y]) {
|
|
continue;
|
|
}
|
|
|
|
ok = true;
|
|
x = xx;
|
|
y = yy;
|
|
timeLeft--;
|
|
answer.append(dirsOrderLabels[i]);
|
|
break;
|
|
}
|
|
|
|
if (!ok) {
|
|
out.println("IMPOSSIBLE");
|
|
return;
|
|
}
|
|
}
|
|
|
|
if (timeLeft != 0 || x != startX || y != startY) {
|
|
out.println("IMPOSSIBLE");
|
|
return;
|
|
}
|
|
|
|
out.println(answer);
|
|
}
|
|
}
|