II Olympiad in Informatics 1994/1995
|
Task: KPK
|
Author: Piotr Chrz±stowski-Wachtel
|
II stage contest |
We are given a rectangular city map comprising n × m squares (1 <= n <= 100 and 1 <= m <= 100). The rows of squares of the map are numbered successively from top to bottom by numbers from 1 to n, and the columns from left to right successively from 1 to m. Each square is either free or blocked. Vehicular traffic is allowed only on free squares. From each free square one may move to a free square adjacent to it (i.e. a square that shares a side with it), however one is not allowed to turn back, i.e. to go back to a square X immediately after moving from X to an adjacent square Y.
The Right-Turn Drivers' Club ordered a computer program, which for any two different squares A and B decides whether it is possible to drive from A to B without turning left, and if so, the program finds such a route with the minimal length. The length of a route is the number of all its squares. The squares A and B are also considered squares of the route from A to B.
Next, in one line, there are two coordinates of the square A, separated by a single space: the row number not greater than n and the column number not greater than m. In the following line there are two coordinates of the square B, written the same way.
The data in the file KPK.IN are written correctly and your program need not verify that.
8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 1 3in the file KPK.OUT one should write:
NIE
For the file KPK.IN:
8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 3 8in the file KPK.OUT one should write:
12 2 6 3 6 4 6 5 6 5 5 5 4 4 4 3 4 3 5 3 6 3 7 3 8
Your program should look for the file KPK.IN in the current directory and create the file KPK.OUT also in the current directory. The source file containing the program written by you should be named KPK.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file KPK.EXE.