ZOJ Problem Set - 3561
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:
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.
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!".
5 5 0 0 3 1 ...J. ..J.. .J.J. ..J.. ....P 3 4 0 0 2 3 ..J. .P.. ..J. 3 3 0 0 2 2 ..J .P. ...
3 4 4
Author: FU, Yujun
Contest: ZOJ Monthly, December 2011