Passi minimi per raggiungere l'obiettivo da parte di un Cavaliere | Insieme 2
Data una scacchiera quadrata di dimensioni N x N, viene data la posizione del Cavaliere e la posizione di un bersaglio, il compito è scoprire i passi minimi che un Cavaliere farà per raggiungere la posizione di destinazione.
Esempi:
Input : (2 4) - knight's position (6 4) - target cell Output : 2 Input : (4 5) (1 1) Output : 3
Un approccio BFS per risolvere il problema di cui sopra è già stato discusso nel precedente inviare. In questo post viene discussa una soluzione di Programmazione Dinamica.
Spiegazione dell'approccio:
Consideriamo una scacchiera di 8 x 8 celle. Ora diciamo che il cavallo è su (3 3) e il bersaglio è su (7 8). Sono possibili 8 mosse dalla posizione attuale del Cavallo, ovvero (2 1) (1 2) (4 1) (1 4) (5 2) (2 5) (5 4) (4 5). Ma di questi solo due movimenti (5 4) e (4 5) saranno verso il bersaglio e tutti gli altri si allontaneranno dal bersaglio. Quindi per trovare i passaggi minimi vai a (4 5) o (5 4). Ora calcola i passi minimi compiuti da (4 5) e (5 4) per raggiungere l'obiettivo. Questo viene calcolato mediante programmazione dinamica. Ciò si traduce quindi nei passi minimi da (3 3) a (7 8).
Consideriamo una scacchiera di 8 x 8 celle. Ora diciamo che il cavallo è su (4 3) e il bersaglio è su (4 7). Sono possibili 8 mosse ma verso il bersaglio ci sono solo 4 mosse cioè (5 5) (3 5) (2 4) (6 4). Poiché (5 5) è equivalente a (3 5) e (2 4) è equivalente a (6 4). Quindi da questi 4 punti può essere convertito in 2 punti. Prendendo (5 5) e (6 4) (qui). Ora calcola i passi minimi compiuti da questi due punti per raggiungere l'obiettivo. Questo viene calcolato mediante programmazione dinamica. Ciò si traduce quindi nei passi minimi da (4 3) a (4 7).
Eccezione: Quando il Cavallo sarà all'angolo e il bersaglio è tale che la differenza delle coordinate xey con la posizione del Cavallo è (1 1) o viceversa. Quindi i passaggi minimi saranno 4.
Equazione di programmazione dinamica:
1) dp[diffOfX][diffOfY] è il passo minimo compiuto dalla posizione del Cavallo alla posizione del bersaglio.
2) dp[diffOfX][diffOfY] = dp[diffOfY][diffOfX] .
dove diffOfX = differenza tra la coordinata x del cavaliere e la coordinata x del bersaglio
diffOfY = differenza tra la coordinata y del cavaliere e la coordinata y del bersaglio
Di seguito è riportata l'implementazione dell'approccio di cui sopra:
// 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>
Produzione:
3
Complessità temporale: O(N * M) dove N è il numero totale di righe e M è il numero totale di colonne
Spazio ausiliario: O(N*M)
Potrebbe Piacerti
Articoli Più
