기사가 목표물에 도달하기 위한 최소 단계 | 세트 2
N x N 크기의 정사각형 체스판에서 기사의 위치와 목표의 위치가 주어지면 기사가 목표 위치에 도달하기 위해 취하는 최소 단계를 찾는 것이 임무입니다.
예:
Input : (2 4) - knight's position (6 4) - target cell Output : 2 Input : (4 5) (1 1) Output : 3
위의 문제를 해결하기 위한 BFS 접근 방식은 이미 논의된 바 있습니다. 이전의 우편. 이 게시물에서는 동적 프로그래밍 솔루션에 대해 논의합니다.
접근 방식에 대한 설명:
8 x 8 셀의 체스판을 보자. 이제 기사가 (3 3)에 있고 목표가 (7 8)에 있다고 가정해 보겠습니다. 기사의 현재 위치에서 가능한 이동 수는 (2 1) (1 2) (4 1) (1 4) (5 2) (2 5) (5 4) (4 5)입니다. 그러나 이 중에서 두 가지 움직임(5 4)과 (4 5)만이 목표를 향해 움직이고 다른 모든 움직임은 목표에서 멀어집니다. 따라서 최소 단계를 찾으려면 (4 5) 또는 (5 4)로 이동하세요. 이제 목표에 도달하기 위해 (4 5)와 (5 4)에서 취한 최소 단계를 계산합니다. 이는 동적 프로그래밍으로 계산됩니다. 따라서 이는 (3 3)에서 (7 8)까지의 최소 단계가 됩니다.
8 x 8 셀의 체스판을 보자. 이제 기사가 (4 3)에 있고 대상이 (4 7)에 있다고 가정해 보겠습니다. 8개의 이동이 가능하지만 목표를 향한 이동은 4개뿐입니다(예: (5 5) (3 5) (2 4) (6 4)). (5 5)는 (3 5)와 같고 (2 4)는 (6 4)와 같습니다. 따라서 이 4개 포인트를 2개 포인트로 변환할 수 있습니다. (5 5)와 (6 4)를 취합니다(여기). 이제 목표에 도달하기 위해 이 두 지점에서 취한 최소 단계를 계산하십시오. 이는 동적 프로그래밍으로 계산됩니다. 따라서 이는 (4 3)에서 (4 7)까지의 최소 단계가 됩니다.
예외 : 나이트가 코너에 있고 타겟이 나이트 위치와 x 및 y 좌표의 차이가 (1 1)이거나 그 반대인 경우. 그러면 최소 단계는 4가 됩니다.
동적 프로그래밍 방정식:
1) dp[diffOfX][diffOfY] 기사 위치에서 목표 위치까지 이동하는 최소 단계입니다.
2) dp[diffOfX][diffOfY] = dp[diffOfY][diffOfX] .
여기서 diffOfX = 기사의 x 좌표와 대상의 x 좌표 간의 차이
diffOfY = 나이트의 y좌표와 타겟의 y좌표의 차이
다음은 위의 접근 방식을 구현한 것입니다.
// C++ code for minimum steps for // a knight to reach target position #include using namespace std ; // initializing the matrix. int dp [ 8 ][ 8 ] = { 0 }; int getsteps ( int x int y int tx int ty ) { // if knight is on the target // position return 0. if ( x == tx && y == ty ) return dp [ 0 ][ 0 ]; else { // if already calculated then return // that value. Taking absolute difference. if ( dp [ abs ( x - tx )][ abs ( y - ty )] != 0 ) return dp [ abs ( x - tx )][ abs ( y - ty )]; else { // there will be two distinct positions // from the knight towards a target. // if the target is in same row or column // as of knight then there can be four // positions towards the target but in that // two would be the same and the other two // would be the same. int x1 y1 x2 y2 ; // (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 . if ( x <= tx ) { if ( y <= ty ) { x1 = x + 2 ; y1 = y + 1 ; x2 = x + 1 ; y2 = y + 2 ; } else { x1 = x + 2 ; y1 = y - 1 ; x2 = x + 1 ; y2 = y - 2 ; } } else { if ( y <= ty ) { x1 = x - 2 ; y1 = y + 1 ; x2 = x - 1 ; y2 = y + 2 ; } else { x1 = x - 2 ; y1 = y - 1 ; x2 = x - 1 ; y2 = y - 2 ; } } // ans will be 1 + minimum of steps // required from (x1 y1) and (x2 y2). dp [ abs ( x - tx )][ abs ( y - ty )] = min ( getsteps ( x1 y1 tx ty ) getsteps ( x2 y2 tx ty )) + 1 ; // exchanging the coordinates x with y of both // knight and target will result in same ans. dp [ abs ( y - ty )][ abs ( x - tx )] = dp [ abs ( x - tx )][ abs ( y - ty )]; return dp [ abs ( x - tx )][ abs ( y - ty )]; } } } // Driver Code int main () { int i n x y tx ty ans ; // size of chess board n*n n = 100 ; // (x y) coordinate of the knight. // (tx ty) coordinate of the target position. x = 4 ; y = 5 ; tx = 1 ; ty = 1 ; // (Exception) these are the four corner points // for which the minimum steps is 4. if (( x == 1 && y == 1 && tx == 2 && ty == 2 ) || ( x == 2 && y == 2 && tx == 1 && ty == 1 )) ans = 4 ; else if (( x == 1 && y == n && tx == 2 && ty == n - 1 ) || ( x == 2 && y == n - 1 && tx == 1 && ty == n )) ans = 4 ; else if (( x == n && y == 1 && tx == n - 1 && ty == 2 ) || ( x == n - 1 && y == 2 && tx == n && ty == 1 )) ans = 4 ; else if (( x == n && y == n && tx == n - 1 && ty == n - 1 ) || ( x == n - 1 && y == n - 1 && tx == n && ty == n )) ans = 4 ; else { // dp[a][b] here a b is the difference of // x & tx and y & ty respectively. dp [ 1 ][ 0 ] = 3 ; dp [ 0 ][ 1 ] = 3 ; dp [ 1 ][ 1 ] = 2 ; dp [ 2 ][ 0 ] = 2 ; dp [ 0 ][ 2 ] = 2 ; dp [ 2 ][ 1 ] = 1 ; dp [ 1 ][ 2 ] = 1 ; ans = getsteps ( x y tx ty ); } cout < < ans < < endl ; return 0 ; }
Java //Java code for minimum steps for // a knight to reach target position public class GFG { // initializing the matrix. static int dp [][] = new int [ 8 ][ 8 ] ; static int getsteps ( int x int y int tx int ty ) { // if knight is on the target // position return 0. if ( x == tx && y == ty ) { return dp [ 0 ][ 0 ] ; } else // if already calculated then return // that value. Taking absolute difference. if ( dp [ Math . abs ( x - tx ) ][ Math . abs ( y - ty ) ] != 0 ) { return dp [ Math . abs ( x - tx ) ][ Math . abs ( y - ty ) ] ; } else { // there will be two distinct positions // from the knight towards a target. // if the target is in same row or column // as of knight then there can be four // positions towards the target but in that // two would be the same and the other two // would be the same. int x1 y1 x2 y2 ; // (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 . if ( x <= tx ) { if ( y <= ty ) { x1 = x + 2 ; y1 = y + 1 ; x2 = x + 1 ; y2 = y + 2 ; } else { x1 = x + 2 ; y1 = y - 1 ; x2 = x + 1 ; y2 = y - 2 ; } } else if ( y <= ty ) { x1 = x - 2 ; y1 = y + 1 ; x2 = x - 1 ; y2 = y + 2 ; } else { x1 = x - 2 ; y1 = y - 1 ; x2 = x - 1 ; y2 = y - 2 ; } // ans will be 1 + minimum of steps // required from (x1 y1) and (x2 y2). dp [ Math . abs ( x - tx ) ][ Math . abs ( y - ty ) ] = Math . min ( getsteps ( x1 y1 tx ty ) getsteps ( x2 y2 tx ty )) + 1 ; // exchanging the coordinates x with y of both // knight and target will result in same ans. dp [ Math . abs ( y - ty ) ][ Math . abs ( x - tx ) ] = dp [ Math . abs ( x - tx ) ][ Math . abs ( y - ty ) ] ; return dp [ Math . abs ( x - tx ) ][ Math . abs ( y - ty ) ] ; } } // Driver Code static public void main ( String [] args ) { int i n x y tx ty ans ; // size of chess board n*n n = 100 ; // (x y) coordinate of the knight. // (tx ty) coordinate of the target position. x = 4 ; y = 5 ; tx = 1 ; ty = 1 ; // (Exception) these are the four corner points // for which the minimum steps is 4. if (( x == 1 && y == 1 && tx == 2 && ty == 2 ) || ( x == 2 && y == 2 && tx == 1 && ty == 1 )) { ans = 4 ; } else if (( x == 1 && y == n && tx == 2 && ty == n - 1 ) || ( x == 2 && y == n - 1 && tx == 1 && ty == n )) { ans = 4 ; } else if (( x == n && y == 1 && tx == n - 1 && ty == 2 ) || ( x == n - 1 && y == 2 && tx == n && ty == 1 )) { ans = 4 ; } else if (( x == n && y == n && tx == n - 1 && ty == n - 1 ) || ( x == n - 1 && y == n - 1 && tx == n && ty == n )) { ans = 4 ; } else { // dp[a][b] here a b is the difference of // x & tx and y & ty respectively. dp [ 1 ][ 0 ] = 3 ; dp [ 0 ][ 1 ] = 3 ; dp [ 1 ][ 1 ] = 2 ; dp [ 2 ][ 0 ] = 2 ; dp [ 0 ][ 2 ] = 2 ; dp [ 2 ][ 1 ] = 1 ; dp [ 1 ][ 2 ] = 1 ; ans = getsteps ( x y tx ty ); } System . out . println ( ans ); } } /*This code is contributed by PrinciRaj1992*/
Python3 # Python3 code for minimum steps for # a knight to reach target position # initializing the matrix. dp = [[ 0 for i in range ( 8 )] for j in range ( 8 )]; def getsteps ( x y tx ty ): # if knight is on the target # position return 0. if ( x == tx and y == ty ): return dp [ 0 ][ 0 ]; # if already calculated then return # that value. Taking absolute difference. elif ( dp [ abs ( x - tx )][ abs ( y - ty )] != 0 ): return dp [ abs ( x - tx )][ abs ( y - ty )]; else : # there will be two distinct positions # from the knight towards a target. # if the target is in same row or column # as of knight then 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 x2 y2 = 0 0 0 0 ; # (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 . if ( x <= tx ): if ( y <= ty ): x1 = x + 2 ; y1 = y + 1 ; x2 = x + 1 ; y2 = y + 2 ; else : x1 = x + 2 ; y1 = y - 1 ; x2 = x + 1 ; y2 = y - 2 ; elif ( y <= ty ): x1 = x - 2 ; y1 = y + 1 ; x2 = x - 1 ; y2 = y + 2 ; else : x1 = x - 2 ; y1 = y - 1 ; x2 = x - 1 ; y2 = y - 2 ; # ans will be 1 + minimum of steps # required from (x1 y1) and (x2 y2). dp [ abs ( x - tx )][ abs ( y - ty )] = min ( getsteps ( x1 y1 tx ty ) getsteps ( x2 y2 tx ty )) + 1 ; # exchanging the coordinates x with y of both # knight and target will result in same ans. dp [ abs ( y - ty )][ abs ( x - tx )] = dp [ abs ( x - tx )][ abs ( y - ty )]; return dp [ abs ( x - tx )][ abs ( y - ty )]; # Driver Code if __name__ == '__main__' : # size of chess board n*n n = 100 ; # (x y) coordinate of the knight. # (tx ty) coordinate of the target position. x = 4 ; y = 5 ; tx = 1 ; ty = 1 ; # (Exception) these are the four corner points # for which the minimum steps is 4. if (( x == 1 and y == 1 and tx == 2 and ty == 2 ) or ( x == 2 and y == 2 and tx == 1 and ty == 1 )): ans = 4 ; 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 )): ans = 4 ; 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 )): ans = 4 ; 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 )): ans = 4 ; else : # dp[a][b] here a b is the difference of # x & tx and y & ty respectively. dp [ 1 ][ 0 ] = 3 ; dp [ 0 ][ 1 ] = 3 ; dp [ 1 ][ 1 ] = 2 ; dp [ 2 ][ 0 ] = 2 ; dp [ 0 ][ 2 ] = 2 ; dp [ 2 ][ 1 ] = 1 ; dp [ 1 ][ 2 ] = 1 ; ans = getsteps ( x y tx ty ); print ( ans ); # This code is contributed by PrinciRaj1992
C# // C# code for minimum steps for // a knight to reach target position using System ; public class GFG { // initializing the matrix. static int [ ] dp = new int [ 8 8 ]; static int getsteps ( int x int y int tx int ty ) { // if knight is on the target // position return 0. if ( x == tx && y == ty ) { return dp [ 0 0 ]; } else // if already calculated then return // that value. Taking Absolute difference. if ( dp [ Math . Abs ( x - tx ) Math . Abs ( y - ty )] != 0 ) { return dp [ Math . Abs ( x - tx ) Math . Abs ( y - ty )]; } else { // there will be two distinct positions // from the knight towards a target. // if the target is in same row or column // as of knight then there can be four // positions towards the target but in that // two would be the same and the other two // would be the same. int x1 y1 x2 y2 ; // (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 . if ( x <= tx ) { if ( y <= ty ) { x1 = x + 2 ; y1 = y + 1 ; x2 = x + 1 ; y2 = y + 2 ; } else { x1 = x + 2 ; y1 = y - 1 ; x2 = x + 1 ; y2 = y - 2 ; } } else if ( y <= ty ) { x1 = x - 2 ; y1 = y + 1 ; x2 = x - 1 ; y2 = y + 2 ; } else { x1 = x - 2 ; y1 = y - 1 ; x2 = x - 1 ; y2 = y - 2 ; } // ans will be 1 + minimum of steps // required from (x1 y1) and (x2 y2). dp [ Math . Abs ( x - tx ) Math . Abs ( y - ty )] = Math . Min ( getsteps ( x1 y1 tx ty ) getsteps ( x2 y2 tx ty )) + 1 ; // exchanging the coordinates x with y of both // knight and target will result in same ans. dp [ Math . Abs ( y - ty ) Math . Abs ( x - tx )] = dp [ Math . Abs ( x - tx ) Math . Abs ( y - ty )]; return dp [ Math . Abs ( x - tx ) Math . Abs ( y - ty )]; } } // Driver Code static public void Main () { int i n x y tx ty ans ; // size of chess board n*n n = 100 ; // (x y) coordinate of the knight. // (tx ty) coordinate of the target position. x = 4 ; y = 5 ; tx = 1 ; ty = 1 ; // (Exception) these are the four corner points // for which the minimum steps is 4. if (( x == 1 && y == 1 && tx == 2 && ty == 2 ) || ( x == 2 && y == 2 && tx == 1 && ty == 1 )) { ans = 4 ; } else if (( x == 1 && y == n && tx == 2 && ty == n - 1 ) || ( x == 2 && y == n - 1 && tx == 1 && ty == n )) { ans = 4 ; } else if (( x == n && y == 1 && tx == n - 1 && ty == 2 ) || ( x == n - 1 && y == 2 && tx == n && ty == 1 )) { ans = 4 ; } else if (( x == n && y == n && tx == n - 1 && ty == n - 1 ) || ( x == n - 1 && y == n - 1 && tx == n && ty == n )) { ans = 4 ; } else { // dp[a b] here a b is the difference of // x & tx and y & ty respectively. dp [ 1 0 ] = 3 ; dp [ 0 1 ] = 3 ; dp [ 1 1 ] = 2 ; dp [ 2 0 ] = 2 ; dp [ 0 2 ] = 2 ; dp [ 2 1 ] = 1 ; dp [ 1 2 ] = 1 ; ans = getsteps ( x y tx ty ); } Console . WriteLine ( ans ); } } /*This code is contributed by PrinciRaj1992*/
JavaScript < script > // JavaScript code for minimum steps for // a knight to reach target position // initializing the matrix. let dp = new Array ( 8 ) for ( let i = 0 ; i < 8 ; i ++ ){ dp [ i ] = new Array ( 8 ). fill ( 0 ) } function getsteps ( x y tx ty ) { // if knight is on the target // position return 0. if ( x == tx && y == ty ) return dp [ 0 ][ 0 ]; else { // if already calculated then return // that value. Taking absolute difference. if ( dp [( Math . abs ( x - tx ))][( Math . abs ( y - ty ))] != 0 ) return dp [( Math . abs ( x - tx ))][( Math . abs ( y - ty ))]; else { // there will be two distinct positions // from the knight towards a target. // if the target is in same row or column // as of knight then there can be four // positions towards the target but in that // two would be the same and the other two // would be the same. let x1 y1 x2 y2 ; // (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 . if ( x <= tx ) { if ( y <= ty ) { x1 = x + 2 ; y1 = y + 1 ; x2 = x + 1 ; y2 = y + 2 ; } else { x1 = x + 2 ; y1 = y - 1 ; x2 = x + 1 ; y2 = y - 2 ; } } else { if ( y <= ty ) { x1 = x - 2 ; y1 = y + 1 ; x2 = x - 1 ; y2 = y + 2 ; } else { x1 = x - 2 ; y1 = y - 1 ; x2 = x - 1 ; y2 = y - 2 ; } } // ans will be 1 + minimum of steps // required from (x1 y1) and (x2 y2). dp [( Math . abs ( x - tx ))][( Math . abs ( y - ty ))] = Math . min ( getsteps ( x1 y1 tx ty ) getsteps ( x2 y2 tx ty )) + 1 ; // exchanging the coordinates x with y of both // knight and target will result in same ans. dp [( Math . abs ( y - ty ))][( Math . abs ( x - tx ))] = dp [( Math . abs ( x - tx ))][( Math . abs ( y - ty ))]; return dp [( Math . abs ( x - tx ))][( Math . abs ( y - ty ))]; } } } // Driver Code let i n x y tx ty ans ; // size of chess board n*n n = 100 ; // (x y) coordinate of the knight. // (tx ty) coordinate of the target position. x = 4 ; y = 5 ; tx = 1 ; ty = 1 ; // (Exception) these are the four corner points // for which the minimum steps is 4. if (( x == 1 && y == 1 && tx == 2 && ty == 2 ) || ( x == 2 && y == 2 && tx == 1 && ty == 1 )) ans = 4 ; else if (( x == 1 && y == n && tx == 2 && ty == n - 1 ) || ( x == 2 && y == n - 1 && tx == 1 && ty == n )) ans = 4 ; else if (( x == n && y == 1 && tx == n - 1 && ty == 2 ) || ( x == n - 1 && y == 2 && tx == n && ty == 1 )) ans = 4 ; else if (( x == n && y == n && tx == n - 1 && ty == n - 1 ) || ( x == n - 1 && y == n - 1 && tx == n && ty == n )) ans = 4 ; else { // dp[a][b] here a b is the difference of // x & tx and y & ty respectively. dp [ 1 ][ 0 ] = 3 ; dp [ 0 ][ 1 ] = 3 ; dp [ 1 ][ 1 ] = 2 ; dp [ 2 ][ 0 ] = 2 ; dp [ 0 ][ 2 ] = 2 ; dp [ 2 ][ 1 ] = 1 ; dp [ 1 ][ 2 ] = 1 ; ans = getsteps ( x y tx ty ); } document . write ( ans ' ' ); // This code is contributed by shinjanpatra. < /script>
산출:
3
시간 복잡도: O(N * M) 여기서 N은 총 행 수이고 M은 총 열 수입니다.
보조 공간: 오(N*M)
마음에 드실지도 몰라요
인기 기사
