Minimum steps to reach target by a Knight | Set 2 | initializing the matrix . ; if knight is on the target position return 0. ; if already calculated then return that value . Taking absolute difference . ; there will be two distinct positions from the knight towards a target . if the target is in same row or column as of knight than there can be four positions towards the target but in that two would be the same and the other two would be the same . ; ( x1 , y1 ) and ( x2 , y2 ) are two positions . these can be different according to situation . From position of knight , the chess board can be divided into four blocks i . e . . N - E , E - S , S - W , W - N . ; ans will be , 1 + minimum of steps required from ( x1 , y1 ) and ( x2 , y2 ) . ; exchanging the coordinates x with y of both knight and target will result in same ans . ; Driver Code ; size of chess board n * n ; ( x , y ) coordinate of the knight . ( tx , ty ) coordinate of the target position . ; ( Exception ) these are the four corner points for which the minimum steps is 4. ; dp [ a ] [ b ] , here a , b is the difference of x & tx and y & ty respectively .
dp = [ [ 0 for i in range ( 8 ) ] for j in range ( 8 ) ] ; NEW_LINE def getsteps ( x , y , tx , ty ) : NEW_LINE INDENT if ( x == tx and y == ty ) : NEW_LINE INDENT return dp [ 0 ] [ 0 ] ; NEW_LINE DEDENT elif ( dp [ abs ( x - tx ) ] [ abs ( y - ty ) ] != 0 ) : NEW_LINE INDENT return dp [ abs ( x - tx ) ] [ abs ( y - ty ) ] ; NEW_LINE DEDENT else : NEW_LINE INDENT x1 , y1 , x2 , y2 = 0 , 0 , 0 , 0 ; NEW_LINE if ( x <= tx ) : NEW_LINE INDENT if ( y <= ty ) : NEW_LINE INDENT x1 = x + 2 ; NEW_LINE y1 = y + 1 ; NEW_LINE x2 = x + 1 ; NEW_LINE y2 = y + 2 ; NEW_LINE DEDENT else : NEW_LINE INDENT x1 = x + 2 ; NEW_LINE y1 = y - 1 ; NEW_LINE x2 = x + 1 ; NEW_LINE y2 = y - 2 ; NEW_LINE DEDENT DEDENT elif ( y <= ty ) : NEW_LINE INDENT x1 = x - 2 ; NEW_LINE y1 = y + 1 ; NEW_LINE x2 = x - 1 ; NEW_LINE y2 = y + 2 ; NEW_LINE DEDENT else : NEW_LINE INDENT x1 = x - 2 ; NEW_LINE y1 = y - 1 ; NEW_LINE x2 = x - 1 ; NEW_LINE y2 = y - 2 ; NEW_LINE DEDENT dp [ abs ( x - tx ) ] [ abs ( y - ty ) ] = min ( getsteps ( x1 , y1 , tx , ty ) , getsteps ( x2 , y2 , tx , ty ) ) + 1 ; NEW_LINE dp [ abs ( y - ty ) ] [ abs ( x - tx ) ] = dp [ abs ( x - tx ) ] [ abs ( y - ty ) ] ; NEW_LINE return dp [ abs ( x - tx ) ] [ abs ( y - ty ) ] ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 100 ; NEW_LINE x = 4 ; NEW_LINE y = 5 ; NEW_LINE tx = 1 ; NEW_LINE ty = 1 ; NEW_LINE if ( ( x == 1 and y == 1 and tx == 2 and ty == 2 ) or ( x == 2 and y == 2 and tx == 1 and ty == 1 ) ) : NEW_LINE INDENT ans = 4 ; NEW_LINE DEDENT elif ( ( x == 1 and y == n and tx == 2 and ty == n - 1 ) or ( x == 2 and y == n - 1 and tx == 1 and ty == n ) ) : NEW_LINE INDENT ans = 4 ; NEW_LINE DEDENT elif ( ( x == n and y == 1 and tx == n - 1 and ty == 2 ) or ( x == n - 1 and y == 2 and tx == n and ty == 1 ) ) : NEW_LINE INDENT ans = 4 ; NEW_LINE DEDENT elif ( ( x == n and y == n and tx == n - 1 and ty == n - 1 ) or ( x == n - 1 and y == n - 1 and tx == n and ty == n ) ) : NEW_LINE INDENT ans = 4 ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 1 ] [ 0 ] = 3 ; NEW_LINE dp [ 0 ] [ 1 ] = 3 ; NEW_LINE dp [ 1 ] [ 1 ] = 2 ; NEW_LINE dp [ 2 ] [ 0 ] = 2 ; NEW_LINE dp [ 0 ] [ 2 ] = 2 ; NEW_LINE dp [ 2 ] [ 1 ] = 1 ; NEW_LINE dp [ 1 ] [ 2 ] = 1 ; NEW_LINE ans = getsteps ( x , y , tx , ty ) ; NEW_LINE DEDENT print ( ans ) ; NEW_LINE DEDENT