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 or outside the board.
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 (≤ 1000) and M (≤ 1000), 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.
Read full article from Knight Jumps | CodeChef
No comments:
Post a Comment