Peanut has recently been addicted to this new soft drink and can't resist drinking it every lunch during December Training. However, as it usually always is, Peanut is released late for lunch and has no time to finish the soft drink! As a result, he is faced with a choice: to either throw the soft drink away, or to smuggle it into PL6. Of course, why the heck would anyone throw such an awesome soft drink away? Forced by his dire circumstances, Peanut reluctantly decides to attempt to smuggle his soft drink into PL6.
In order to do so, Peanut has to bring the soft drink from the entrance of COM1 to PL6. However, there is a problem. Steven has been patrolling the COM1 building in order to prevent people from soft drinks into COM1. In fact, in order to do so efficiently, Steven has used his superior engineering skills to build several devices for him to catch the offenders.
One of the devices that Steven has built is a pair of laser-firing eyes. If there is an unobstructed exactly horizontal or vertical path from Steven to Peanut, he will see Peanut with the soft drink and use his super duper power lasers to fire at Peanut's soft drink, vaporising his soft drink and turning his efforts into nothing. Also, after years of training, Steven has learnt how to teleport from position to position in COM1 in order to effectively catch people with soft drinks.
The COM1 building is represented by a grid of size H x W. Each pixel on the grid can be either a '.' or 'X', where an '.' refers to an empty spot and an 'X' indicates an obstacle neither Peanut nor Steven's super duper lasers can pass through. The COM1 entrance is also represented by an 'S' on the grid and PL6 is represented by a 'T' on the grid. Peanut starts at the pixel 'S' and ends at the pixel 'T'.
Peanut takes 1 unit of time to traverse each grid square on the grid and will start at the 'S' square at time = 0. He also can only travel horizontally or vertically. Throughout Peanut's journey to PL6, Steven will also teleport into N different positions. At time = 0, Steven will start at (0, 0), ie the top left corner of the grid. Each teleportation move i will involve Steven teleporting from his original position into (Xi, Yi) at time Ti.
Given the grid representation of COM1 and all of Steven's N teleportation moves, determine the earliest time at which Peanut can reach PL6 without his drink being vaporised by Steven's super duper lasers. If this is not possible and Peanut's drink is doomed for its inevitable state change, output -1.
will always be unique and Ti
≤ 1 000 000 000.
Subtask 1 (19%): 1 ≤ H, W ≤ 100. N = 1.
Subtask 2 (27%): 1 ≤ H, W ≤ 100. 1 ≤ N ≤ 20.
Subtask 3 (54%): 1 ≤ H, W ≤ 500. 1 ≤ N ≤ 50.
Subtask 4 (0%): As per sample testcases.
The first line of input will contain two integers, H
The next H
lines will contain W
characters each, representing the grid map of COM1.
The following line will contain one integer, N
The next N
lines will contain three integers each, with the i
th line containing Xi
The output should contain one integer, the earliest time at which Peanut can reach PL6, or -1 if this is not possible.
Sample Input 1
1 0 2
Sample Output 1
Explanation for Sample 1
At time = 0, Peanut is at (0, 1) where the start point is and Steven is at (0, 0). Steven will then fire his super duper lasers rightward towards Peanut and vaporise his soft drink. As you can see, there is no way to avoid this fate.
Sample Input 2
1 0 0
0 3 3
Sample Output 2
Explanation for Sample 2
From time 0 to 2, Peanut cannot move from 'S' as Steven will get him from position (1, 0) if he moves downwards. At time 3, Peanut dodges downwards to (1, 2) when Steven teleports to (0, 3). After that, Peanut is free from Steven's lasers and travels the shortest path to PL6, 2 more steps down and 2 more steps left, which allows him to reach at 3 + 2 + 2 = time 7.