|Online Judge||Problem Set||Authors||Online Contests||User|
A construction firm, which you work for, has signed a contract to complete construction of attraction called “Switchback”. The building site is a rectangle which is split into NxM squares (1 ≤ N, M ≤ 50), N rows down, M columns across. The square in the north-west corner of the building site is (1, 1), while the square in the south-east corner is (N, M).
By the moment of signing the contract the following work has already been done at the attraction building site. First, a mast was built in each of the squares. The height of the mast in the square (i, j) is Hij (1 ≤ Hij ≤ 100, natural). Second, construction of a launching complex was started at the top of the mast with coordinates (a, b), where 1 ≤ a ≤ N, 1 ≤ b ≤ M.
The idea of the attraction is the following. A small carriage with passengers moves from one square to another adjacent square, square by square. It starts moving from the square with the launching complex and moves until it stops. It moves on rails built on tops of masts according to the following rules:
The number of squares visited by the carriage during its trip is called attraction length. If the carriage visits a square more than once than each of the visits counts. The first square of the path does not count.
The construction firm has to build rails on tops of the masts. As the only programmer in the firm, you need to write a program which can find the longest possible path according to the rules above. It is guaranteed that this path exists and its length is greater than zero.
The first line of the input contains values N, M, a, b. The next N lines contain values Hi,j, M values per line. The numbers in the input file’s lines are separated by one or more spaces.
The output contains several lines. The first line contains an attraction length k. Next k lines contain coordinates of squares and describe the longest path.
5 5 1 1 10 8 6 3 4 9 7 6 5 8 4 5 5 2 1 2 3 5 7 8 1 4 3 3 2
14 2 1 2 2 1 2 1 3 2 3 3 3 3 2 3 1 4 1 4 2 5 2 5 3 5 4 5 5
Northeastern Europe 2004, Western Subregion
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator