Fast Ascending Number Search
InterviewTime limit1sMemory limit512 MB
Find the fewest moves on a 5 x 5 grid to visit cells 1 through 6 in order from a start cell, avoiding -1 cells.
- Level
Medium4 of 10
- Topics
- BFS, Matrix, Shortest path
- Solved
- No attempts yet
Problem
A 5 x 5 board is given. The board is made of 1 x 1 square cells. Each cell contains one of -1, 0, 1, 2, 3, 4, 5, 6. A cell is written as (r, c), where r is the row number and c is the column number. Row numbers start at 0 at the top and increase by 1 going down. Column numbers start at 0 at the left and increase by 1 going right. So the top left cell is (0, 0) and the bottom right cell is (4, 4). A student cannot move onto a cell containing -1, but can move onto a cell containing 0, 1, 2, 3, 4, 5, or 6.
A student is at position (r, c). In one move, the student can step one cell up, down, left, or right. Starting at (r, c), the student wants to visit the cells containing 1, 2, 3, 4, 5, and 6 in that order. The board has exactly one cell for each of 1 through 6. The cells containing 1 through 6 can be visited more than once. When moving from the cell with i to the cell with i + 1 (1 ≤ i ≤ 5), the student may pass through cells with other numbers. Likewise, when moving from (r, c) to the cell with 1, the student may pass through cells with other numbers.
Print the minimum number of moves needed to visit the cells containing 1, 2, 3, 4, 5, and 6 in order, starting from (r, c).
Input
The first line through the fifth line give the numbers on the board, row by row. The j-th number on the i-th line is the number in row (i - 1), column (j - 1) of the board.
The next line gives the student's current position r and c, separated by a space.
Output
Print the minimum number of moves needed to visit the cells containing 1, 2, 3, 4, 5, and 6 in order, starting from (r, c). If the student cannot visit them in that order, print -1.
Constraints
0 ≤ r, c ≤ 4
The cell (r, c) contains 0.
Each of the numbers 1, 2, 3, 4, 5, and 6 appears in exactly one cell.