CSES - Shared codeLink to this code:
https://cses.fi/paste/d1d89c648c96f7d6141b30/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class monsters {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n = scn.nextInt();
int m = scn.nextInt();
char[][] arr = new char[n][m];
for (int i = 0; i < n; ++i) {
arr[i] = scn.next().toCharArray();
}
solve(n, m, arr);
}
public static void solve(int n, int m, char[][] arr) {
Queue<Point> q = new LinkedList<>();
int[][] aux = new int[n][m];
Point start = null;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
char c = arr[i][j];
if (c == 'M') {
q.add(new Point(i, j, 0));
} else {
aux[i][j] = Integer.MAX_VALUE;
}
if (c == 'A') {
start = new Point(i, j, 0);
}
}
}
while (q.size() > 0) {
Point p = q.remove();
int x = p.x;
int y = p.y;
int d = p.d;
aux[x][y] = d;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (check(n, m, nx, ny) && d + 1 <= aux[nx][ny] && arr[nx][ny] != '#') {
q.add(new Point(nx, ny, d + 1));
}
}
}
boolean found = false;
q.add(start);
start.path = "";
boolean[][] visited = new boolean[n][m];
while (q.size() > 0) {
Point p = q.remove();
int x = p.x;
int y = p.y;
int d = p.d;
visited[x][y] = true;
if (end(n, m, x, y)) {
found = true;
out.println("YES");
out.println(p.path.length());
out.println(p.path);
break;
}
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (check(n, m, nx, ny) && !visited[nx][ny] && d + 1 < aux[nx][ny] && arr[nx][ny] != '#') {
Point np = new Point(nx, ny, d + 1);
np.path = p.path + dir[i];
q.add(np);
}
}
}
if (!found) {
out.println("NO");
}
out.flush();
}
public static boolean check(int n, int m, int i, int j) {
if (i >= 0 && i < n && j >= 0 && j < m) {
return true;
}
return false;
}
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
static char[] dir = { 'D', 'U', 'R', 'L' };
public static boolean end(int n, int m, int i, int j) {
if (i == n - 1 || i == 0 || j == 0 || j == m - 1) {
return true;
}
return false;
}
public static class Point {
int x;
int y;
int d;
String path;
Point(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
}
static FastScanner scn = new FastScanner();
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
long nextLong() {
return Long.parseLong(next());
}
}
}