Knight Match Play#3787
There are two knight teams, they have and knights respectively. The knights are numbered from to and to in their own team. They are trapped in an W \times H grid puzzle. The puzzle only has four exits which are the four corners of the puzzle. The knight can only move up, down, left, or right, and the time to move from one grid to the adjacent one is fixed. They can form a "fight partner" if two knights satisfy the following conditions:
The two knights come from different teams.
Both of them can arrive at one of the exits.
The least time needed to arrive at one of the exits is the same.
So how many "fight partners" can they form?
For this action, the leader gives the following directives:
Each team renumbers the knights with their least time needed to get out of the puzzle. So the one who uses the least time will get the ID and the one who uses the most time will get the ID or . If some of them use the same time, then the one whose original ID is lower will get a lower ID.
The chosen knights from the same team should have continuous IDs.
Form "fight partners" according to the IDs one by one. That is to say the one with the lowest ID should form with the one with the lowest ID in another team, and so on.
There are several test cases. The input of every test case is described as below.
First line, there are four integers , , , (0 < N, M < 300, 10 < W, H < 50).
Then there are lines, each line with characters indicating the puzzle. A character of '.' indicates the grid is empty, and every empty grid could contain infinitely many knights. A character of '#' means the grid has a barrier and no knight can step into it. The four corners are empty.
Then there are N+M lines, each line with a pair of integers (, ) (0 \le x < H, 0 \le y < W) indicating the knight is in the th line and th column originally.
The input will finish with the end of the file.
An integer indicating the maximal number of "fight partners" they can form.
Example 1