CCC '10 J5 - Knight Hop

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
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).

8
7
6
5
4
3B
2A
1
12345678

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.

8
7
681
572
4K
363
254
1
12345678

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


  • 0
    learn_to_dive_in_h2o  commented on Feb. 16, 2024, 1:15 p.m.

    How do I make the table like that in the problem statement?


    • 0
      踏雪寻梅  commented on Feb. 19, 2024, 4:59 p.m.

      Imagine rotating this checkerboard 90 degrees, it's actually the same thing as the array. :P


      • -1
        learn_to_dive_in_h2o  commented on Feb. 20, 2024, 7:38 p.m.

        Apologies for the misunderstanding, what I meant to ask was how to create a table similar to the one in the problem statement using Markdown. I'm currently preparing a problem and would like to make a table like that for easier visualization.


  • 6
    gavin_chen  commented on Jan. 15, 2023, 9:54 p.m.

    ♞♘


    • 6
      Haoyun  commented on Dec. 21, 2023, 7:23 p.m. ← edit 13

      ♖ ♘ ♗ ♔ ♕ ♗ ♘ ♖
      ♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙
      ♟ ♟ ♟ ♟ ♟ ♟ ♟ ♟
      ♜ ♞ ♝ ♚ ♛ ♝ ♞ ♜
      Surrender! You stand no chance against my Army of Black and White! Also I have one very high ELO of 1300! ALso my Admiral aka my little Brother has an ELO of 1600. I shall not loose against two kinghts!


  • 2
    KmiloKun  commented on Aug. 25, 2022, 8:54 p.m.

    Help guys. What I have to learn to solve this problem? I think I don't have the bases to solve it.


    • 2
      III  commented on Jan. 27, 2023, 11:37 p.m.

      This problem is solvable by BFS, DFS(Not sure), or others.


      • -2
        GarrisonQ  commented on Dec. 16, 2023, 9:45 a.m.

        DFS does work.


        • -1
          mucube0  commented on Feb. 15, 2024, 7:11 p.m.

          I think DFS won't work since this problem is about the minimum distance


    • 5
      kopichiki  commented on Aug. 25, 2022, 11:22 p.m.

      The problem type is graph theory. So... I guess you need to learn graph theory.


      • 4
        tappbros  commented on Aug. 26, 2022, 5:39 p.m.

        Or you can brute force it.


  • 29
    billsboard  commented on Nov. 28, 2020, 6:34 p.m.

    A chess knight will take at most 5 moves to reach a given square. I don't know if that bit of chess knowledge can be helpful for this problem.


    • 0
      ThePeeps191  commented on Jan. 17, 2022, 10:05 p.m.

      My brain after reading this: to lazy too implement resursion copy-pastes the same code 6 times >_<


    • 6
      Dav_Did  commented on April 19, 2021, 3:06 a.m.

      Good to know I won't need to make a recursion that loops like 50 times without TLE.


    • 23
      aegirwang  commented on Dec. 11, 2020, 4:31 p.m.

      It's actually 6 in some cases, such as from corner to corner.


      • 11
        billsboard  commented on Jan. 9, 2021, 1:29 a.m.

        Ah right, it is 6 moves. Sorry.


    • -8
      Evanhyd  commented on Dec. 1, 2020, 5:36 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • 9
        billsboard  commented on Dec. 2, 2020, 2:29 a.m.

        I was thinking you could pass the problem by setting an exit condition on recursion to be 5, instead of using a visited cache which is what I assume the problem intended.


  • 6
    sjay05  commented on June 15, 2020, 7:44 p.m. ← edited

    Using std::queue with pair<int,int>: https://dmoj.ca/submission/2145895 still MLE's.

    Edit: For comment below.


    • -1
      kresteodymium  commented on June 23, 2021, 9:03 p.m.

      I believe I did the same thing and my program passed without MLEing. I'm not sure why yours did not pass :(. https://dmoj.ca/src/3693845


      • -1
        Badmode  commented on June 29, 2021, 6:07 p.m.

        If there was no memory limit their code would of TLE instead of MLE on test case #6 because of an infinite loop. See Jonathan's comment down below.


    • 2
      kevze  commented on June 15, 2020, 7:52 p.m.

      One mb ://


  • 2
    kevze  commented on June 15, 2020, 4:32 p.m. ← edited

    I mle by one mb on case 6 :(. Any optimization tips?


    • 2
      BreadTurtle  commented on June 15, 2020, 5:58 p.m. ← edit 3

      instead of making separate queues per dimension try using pairs to reduce the number of possible queue entries.


      • 2
        kevze  commented on June 15, 2020, 7:51 p.m.

        A queue of pair<int,int> still mle's. Maybe my BFS algorithm is inefficient? Best solutions only use like 1-2 mb.


        • 5
          Jonathan_Uy  commented on June 15, 2020, 8:14 p.m. ← edit 2

          Your program enters an infinite loop for the test case:

          3 1
1 3

          • 4
            kevze  commented on June 15, 2020, 8:33 p.m.

            Thanks! I got it now!


        • -1
          BreadTurtle  commented on June 15, 2020, 8:08 p.m.

          Then it is most likely that you have a logical error/edge case you did not account for. The runtime for that case took abnormally long as well. I would advise you to look over the semantics.


          • -1
            kevze  commented on June 15, 2020, 8:35 p.m. ← edit 3

            "Then it is most likely that you have a logical error/edge case you did not account for."

            You were right, I had if (visited.at(new_h).at(new_v) == 0) instead of if (visited.at(new_v).at(new_h) == 0).

            *facepalm

            Edit: edits were glitching idk why


  • -1
    delara3838  commented on Feb. 9, 2019, 4:29 p.m.

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


  • -1
    Pleedoh  commented on Aug. 2, 2017, 1:34 a.m.

    wleung_bvg you're getting it too?


    • -1
      wleung_bvg  commented on Aug. 2, 2017, 5: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.


      • -1
        Pleedoh  commented on Aug. 2, 2017, 7:37 p.m.

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