CCC '10 J5 - Knight Hop

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2010 Stage 1, Junior #5

Below is an 8 \times 8 chessboard on which we will designate square locations using the ordered pairs as indicated. For example, notice that piece A is at position (2, 2) and piece B is at position (4, 3).

A knight is a special game piece that can leap over other pieces, moving in the "L" pattern. Specifically, in the diagram below, K represents the knight's starting position and the numbers 1 through 8 represent possible places the knight may move to.

Your program will read the starting location of the knight and output the smallest number of jumps or moves needed to arrive at a location specified in the second input.

Input Specification

Your program will read four integers, where each integer is in the range 1 \dots 8. The first two integers represent the starting position of the knight. The second two integers represent the final position of the knight.

Output Specification

Your program should output the minimum (non-negative integer) number of moves required to move the knight from the starting position to the final position. Note that the knight is not allowed to move off the board during the sequence of moves.

Sample Input 1

2 1
3 3

Output for Sample Input 1

1

Sample Input 2

4 2
7 5

Output for Sample Input 2

2

Comments


  • 1
    delara3838  commented on Feb. 9, 2019, 11:29 a.m.

    What does IR mean and why do i get it when i submit


  • 0
    349081547  commented on Jan. 4, 2019, 10:43 a.m.

    Which would be better?Using a Queue or recursive?


  • 0
    Pleedoh  commented on Aug. 1, 2017, 9:34 p.m.

    wleung_bvg you're getting it too?


    • 3
      wleung_bvg  commented on Aug. 2, 2017, 1:34 p.m. edited

      Your code has variables that have indeterminate ("random") values. This can sometimes happen when declaring a variable in a non global scope without initializing it with a value. Simply initializing the boolean variable with the value false in your spot struct will allow your code to pass.


      • 0
        Pleedoh  commented on Aug. 2, 2017, 3:37 p.m.

        Ah,thanks. Why does the first case work though?


  • 0
    Pleedoh  commented on Aug. 1, 2017, 11:28 a.m.

    No TLE when I submit in Java. Why does my C++ code get stuck when I submit, but never when I try cases on myself?


  • 1
    Pleedoh  commented on July 31, 2017, 10:36 p.m. edited

    TLE

    Can anyone tell me why I'm getting TLE? I've tested my code with all the test data, and I get all the right answers. Given the fact that it's an 8 by 8 board, I find it very hard to believe my code is actually too slow. I even used a timer, with all cases under 0.1. Is my code getting stuck with the input or something?


    • 0
      hello12_2015  commented on Aug. 16, 2017, 4:15 p.m.

      TLE means Time Limit Exceeded. time limit has nothing to do with answers, only the format you've coded the solution.


      • -1
        Pleedoh  commented on Aug. 16, 2017, 4:25 p.m.

        I know... My code wasn't too slow, as mentioned above. The struct bool wasn't initialized.