Knight JumpsProblem code: KNIGHT1 |
There is a rectangular N x M grid of cells. Each cell is either a valid cell or an invalid cell. There is a chess knight at a valid cell. He wants to travel to a particular destination cell, by making a series of jumps.
The knight jumps like any other chess knight - he can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The complete move therefore looks like the letter 'L'. The knight can jump over both valid and invalid cells, but he cannot land in an invalid cell.
Find the minimum number of jumps required to be made, for the knight to go from the initial to the destination cell.
Input
The first line contains two integers N and M, separated by a space. The next N lines contain M characters each. Each of these M characters is one of the following:
1. '.', representing a valid cell,
2. '#', representing an invalid cell,
3. 'S', representing the initial valid cell the knight is located at,
4. 'D', representing the destination valid cell.
Output
The output contains one integer, giving the minimum number of jumps required. The output number is -1, if the destination cell cannot be reached from the initial cell.
Example
Input: 4 5 .#.S# .#... #D#.. ....# Output: 4
Explanation: The knight is located at (0,3) initially. He can make the following series of four jumps to land in the destination cell, which is (2,1).
(0,3) -> (2,4) -> (1,2) -> (0,0) -> (2,1).
| Author: | admin |
| Date Added: | 14-08-2009 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, C, C99 strict, CAML, CLPS, CPP 4.0.0-8, CS2, D, FORT, HASK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
range of n and m
range of n and m
How can I submit my solution?
How can I submit my solution?