G. Greasy Thief of The Village SOLUTION 2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest

Greasy Thief of The Village SOLUTION

Mr. Chanek is police in a village. His town can be represented as a grid G of size N×M, where Gij can be either “.” or “#”, which denotes a passable area and unpassable area (walls, houses, and others) respectively. The outside of the grid is assumed to be unpassable areas.
One day, a thief makes a commotion in the village, and Mr. Chanek is trying to apprehend him. Each second, both the thief and Mr. Chanek can move one square to eight possible directions (up, down, left, right, left-up, left-down, right-up, right-down) with the movement is assumed to happen instantly. As an example, assume Mr. Chanek current position is as follows:
Then Mr. Chanek can move to 5 directions, which is: left-up, left-down, down, right-down, and right.
Here is the chase scenario:
At second i exactly, the thief can move 1 square.
At second (i+0.5), Mr. Chanek can move 1 square.
Both Mr. Chanek and the thief can choose not to move at a second.
If the thief and Mr. Chanek move optimally, determine whether Mr. Chanek will apprehend the thief, or the thief can forever avoid Mr. Chanek. The thief is said to be caught by Mr. Chanek if they occupy the same square.
The first line contains two integers N and M (1≤N,M≤103), the number of rows and columns of the grid, respectively.
The next N lines each contains M characters. The j’th character on the i’th line denotes Gij (Gij∈{“C”,”M”,”.”, “#”}). There will be exactly one character ‘C’ and ‘M’ in G, representing Mr. Chanek’s and the thief’s initial position respectively.
It is guaranteed that there exist a way to visit every pair of non-‘#’ square in G.
Output “tertangkap” (without quotes, Indonesian for “captured”) if Mr. Chanek can apprehend the thief. Output “lolos” (without quotes, Indonesian for “evaded”) if the thief can avoid Mr. Chanek indefinitely.
5 5
4 7
here are the possible movements of the first example:
If the thief moves up:
Mr. Chanek moves left-down.
The thief must move down to avoid capture.
Mr. Chanek moves left.
Whether the thief moves up or down, Mr. Chanek will apprehend him in the next second.
If the thief moves down:
Mr. Chanek moves left-down.
Mr. Chanek will catch the thief if he moves up, left-up, or right (the first case). So the thief can only move down or right-down.
Whether the thief moves right or right-down, Mr. Chanek will move left-down and apprehend the thief the next second.
So, we can see that the thief cannot avoid Mr. Chanek forever.
For the second example, the thief can avoid Mr. Chanek by moving the square that maximizes the distance between him and Mr. Chanek.

Leave a Comment

two × one =