Polish version    English version  
  History of OI -> II OI 1994/1995


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
Stage III - results
Stage I - results
Problems
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: KPK
Author: Piotr Chrz±stowski-Wachtel
The Right-Turn Drivers' Club

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.

Task

Write a program that:
  • reads from the text file KPK.IN data on a rectangular network of squares (i.e. the number of rows n, the number of columns m and the state of each square), and next the coordinates of two different squares A and B;
  • decides whether there exists a route without left turns from A to B.
    If not, the program writes one word NIE ("no") in the text file KPK.OUT.
    If so, the program finds one of the shortest routes without left turns and writes it in the file KPK.OUT.
    If at least one of the squares A, B is not free, then the answer is NIE.

Input

In the first line of the file KPK.IN there are two integers separated by a single space: the number of rows n and the number of columns m. In each of the following n lines of the file there is a description of the corresponding row of the map. Such a description has a form of one word of length m consisting of digits 0 and 1. The digit 0 means that the corresponding square is free, and the digit 1 that it is blocked.

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.

Output

The following should be written in the file KPK.OUT:
  • either one word NIE, if there exist no route without left turns from A to B or at least one of the squares A, B is blocked.
  • or a description of one of the routes with no left turns from A to B having the minimal length; in that case one should write the length of the route d in the first line, and in each of the following d lines - two coordinates of the successive square of the route, separated by a single space.

Examples

For the following file KPK.IN:
8 9
010011101
011010101
000000000
111010101
101000100
111010101
000000000
101011111
2 6
1 3
in 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 8
in 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.




Print friendly version