ナイトがターゲットに到達するための最小ステップ |セット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×8セルのチェス盤を考えてみましょう。ここで、ナイトが (3 3) にいて、ターゲットが (7 8) にあるとします。ナイトの現在の位置からは、(2 1) (1 2) (4 1) (1 4) (5 2) (2 5) (5 4) (4 5) の 8 つの手が考えられます。しかし、これらの動きのうち、ターゲットに向かうのは 2 つの手 (5 4) と (4 5) だけであり、他のすべての動きはターゲットから遠ざかります。したがって、最小ステップを見つけるには、(4 5) または (5 4) のいずれかに進みます。次に、(4 5) と (5 4) から目標に到達するために必要な最小ステップを計算します。これは動的計画法によって計算されます。したがって、これにより、(3 3) から (7 8) までの最小ステップが得られます。
8×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) を取得します (ここ)。次に、これら 2 つの点から目標に到達するために必要な最小ステップを計算します。これは動的計画法によって計算されます。したがって、これにより、(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 は列の合計数です。
補助スペース: O(N * M)
あなたにおすすめ
トップ記事
