CSES - Monsters

Video Solution

By David Zhou

Explanation

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 $NM$ time because each location will be visited a constant amount of times.

Implementation

Time Complexity: $\mathcal{O}(NM)$

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 {