Gegeven een vierkant schaakbord van N x N-formaat, wordt de positie van het paard en de positie van een doelwit gegeven. De taak is om uit te vinden welke minimale stappen een ridder zal nemen om de doelpositie te bereiken.
Voorbeelden:
Input : (2 4) - knight's position (6 4) - target cell Output : 2 Input : (4 5) (1 1) Output : 3
Een BFS-aanpak om het bovenstaande probleem op te lossen is al besproken in de vorig na. In dit bericht wordt een dynamische programmeeroplossing besproken.
Uitleg van de aanpak:
Laat een schaakbord van 8 x 8 cellen. Laten we nu zeggen dat het paard op (3 3) staat en het doelwit op (7 8). Er zijn 8 zetten mogelijk vanaf de huidige positie van het paard, d.w.z. (2 1) (1 2) (4 1) (1 4) (5 2) (2 5) (5 4) (4 5). Maar hiervan zijn slechts twee zetten (5 4) en (4 5) in de richting van het doel en alle andere gaan van het doel af. Dus voor het vinden van de minimale stappen gaat u naar (4 5) of (5 4). Bereken nu de minimale stappen die zijn genomen vanaf (4 5) en (5 4) om het doel te bereiken. Dit wordt berekend door dynamisch programmeren. Dit resulteert dus in de minimale stappen van (3 3) tot (7 8).
Laat een schaakbord van 8 x 8 cellen. Laten we nu zeggen dat het paard op (4 3) staat en het doelwit op (4 7). Er zijn 8 zetten mogelijk, maar richting het doel zijn er slechts 4 zetten, d.w.z. (5 5) (3 5) (2 4) (6 4). Omdat (5 5) gelijk is aan (3 5) en (2 4) gelijk is aan (6 4). Van deze 4 punten kan het dus worden omgezet in 2 punten. Nemen (5 5) en (6 4) (hier). Bereken nu de minimale stappen die vanaf deze twee punten zijn genomen om het doel te bereiken. Dit wordt berekend door dynamisch programmeren. Dit resulteert dus in de minimale stappen van (4 3) naar (4 7).
Uitzondering : Wanneer het paard in de hoek staat en het doel zo is dat het verschil tussen de x- en y-coördinaten met de positie van het paard (1 1) is, of omgekeerd. Dan zijn de minimale stappen 4.
Dynamische programmeervergelijking:
1) dp[diffOfX][diffOfY] is de minimale stappen die zijn genomen van de positie van het paard naar de positie van het doelwit.
2) dp[diffOfX][diffOfY] = dp[diffOfY][diffOfX] .
waarbij diffOfX = verschil tussen de x-coördinaat van het paard en de x-coördinaat van het doelwit
diffOfY = verschil tussen de y-coördinaat van het paard en de y-coördinaat van het doelwit
Hieronder vindt u de implementatie van bovenstaande aanpak:
// C++ code for minimum steps for // a knight to reach target position #include
//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 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# 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*/
<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(xytxty) { // 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>
Uitgang:
3
Tijdcomplexiteit: O(N * M) waarbij N het totale aantal rijen is en M het totale aantal kolommen
Hulpruimte: O(N * M)