Блог пользователя TooWeak_TooSlow

Автор TooWeak_TooSlow, история, 6 лет назад, По-английски

Hello Everyone, I am trying to solve this problem. but not able to come up with a solution. can someone help me with solving the problem any approach/hint.

Problem Statement: Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position. Only Perpendicular Moves Are Allowed.

Constraints:

1<=N<=150. 0<=StartX<=64 0<=StartY<=64

0<=EndX<=64 0<=EndY<=64

StartX and StartY Indicate Starting Location. EndX and Endy Indicate Ending Location.

Test Case:

Input:

N=8 startX and StartY = 0,5

endX and endY = 6,5

output: 3

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How is the output 3?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Looks like straightforward bfs

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Represent the grid as a graph and do a breadth first search from the starting point.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    But moves are prependucilar so simple bfs algorithm will work? Can you explain briefly if possible.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think n00bie has already explained the approach. Regarding what to do to avoid out of bounds. Assume I am at point (i,j) and want to add edges. I want to add edges from (i,j) to (i+1, j+2), (i+2,j+1), (i-1,j-2) and (i-2,j-1). Before I add each of these edges I check to see the destination point is in the grid. If is it not I don't add the edge.