Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3561
Deliver Lunch

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Every day, MaiXiang Planet will send its spacecraft to deliver lunch to the 218 Planet. We can regard the universe as an n*m rectangle with n*m grids in it, each grid of the model represents a planet. Maixiang Planet is in grid (si,sj) and 218 Planet is in grid (ti, tj). Generally, each turn the delivery craft can only move one grid in one of the four directions (left, right, up and down) to another empty planet and it cannot go outside of the rectangle. Please note that both the Jump Equipments and the other crafts may occupy the planet and makes it unavailable for the delivery craft. The Jump Equipments established by Maixiang Restaurant can accelerate the delivery craft to the light speed so that the craft can move more than one grid. Here are the conditions of using the Jump Equipments:

  1. The Jump Equipments must be only one move away from the delivery craft in one of the four directions. In the case 1 in the Sample Input section, if the craft is located in (2, 2) then it can use the Jump Equipment in (1, 2), (2, 1), (2, 3) and (3, 2), but it cannot use the Jump Equipment in (0, 3).
  2. When the spacecraft is using jump equipment it can move to only one direction. That is if the Jump Equipment the craft want to use is on the right (left, up, down) side of the spacecraft, then the craft can only move to right (left, up, down) when it is using this Jump Equipment.
  3. An exit is required for the success of jumping. Any Jump Equipment in the direction of the jumping that we have mentioned in condition 2 can be used as an exit, including the entrance Jump Equipment itself, as long as the exit leads to an empty planet. In the case 1 in the Sample Input section, if the craft is located in (2, 0), and it is using the Jump Equipment in (2, 1), then it can jump to (2, 2) or (2, 4) as it like.
As the jumping in light speed, it takes only one turn no matter how many grids are passed by.

Besides, there is a pirate craft in the universe. Hence, the delivery craft should be piloted cautiously to avoid the attacks from the pirate craft, or else the pirate will take away the lunch. At beginning, the pirate craft is located in grid (pi, pj). It moves in four directions periodically in the ith row and jth column (left, right, up and down) and moves only one grid in every turn (it should be noticed that there is no Jump Equipments on the path of pirate craft). On initializing, the pirate craft is move to the up direction. It will keep its direction until it reaches the edge of the rectangle. On reaching the edge, it turns back and continues to move in the direction of the initial grid. Soon as it reaches the initial grid, it will turn to the direction of left and conducts similar actions as it does in the up direction. The sequence of the directions goes in the up-left-down-right way. If the delivery craft appears in the same column or row as the pirate craft, and there is no barrier (Jump Equipment) between them, the pirate will attacks on the delivery craft and take away the lunch. Please note that pirate cannot attack the craft at the beginning or the end of the delivery. Every turn the craft must take a move and the delivery will be claimed a failure when the delivery craft cannot move anymore.

Your job is to find out the minimum number of turns MaiXiang needed to finish delivering the lunch.


There are multiple test cases.
The first line of each case contains two integers n(1 ≤ n ≤ 40) and m(1 ≤ m ≤ 40), which is the size of the universe.
The second line contains four integers, MaiXiang Planet's position si, sj, and 218 Planet's position ti, tj.
Then there are n lines each containing m characters. In these characters, '.' means empty grid, 'P' means Pirate and 'J' means Jump Equipment.


For each test case, output one line with an integer which is the minimum number of turns MaiXiang needed to finish delivering the lunch. If it is impossible to finish deliver the lunch then output "Today we have no lunch!".

Sample Input

5 5
0 0 3 1
3 4
0 0 2 3
3 3
0 0 2 2

Sample Output


Author: FU, Yujun
Contest: ZOJ Monthly, December 2011
Submit    Status