CSES - Monsters

Abstract

We want to find if A can reach the edge of the maze without being touched by monsters by BFS. If possible, retrace and print its path.

Solution

Because the monsters move optimally, if a monster can reach a location in the maze before A, then A may never move to that spot. Thus, for A to enter a spot, the distance from that location to A must be less than the distance from that location to the nearest monster. Knowing this, we may BFS to find all locations that are visitable by A. This will run in $N^2$ time because each location will be visited a constant amount of times.

While conducting the bfs, store the previous location of every location ("from" array in code below). This way, once A reaches the edge, we can retrace A's path, following the path of previous locations and storing the direction traveled.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int, int>
#define mn 1005
using namespace std;

Copy
import java.io.*;
import java.util.*;

public class monsters {
	public static int[] dX = {1, -1, 0, 0};
	public static int[] dY = {0, 0, 1, -1};
	public static String dirs = "DURL";
	public static int N, M;

	public static void main(String[] args) throws IOException {