Gitt et firkantet sjakkbrett på N x N størrelse, får posisjonen til ridder og posisjonen til et mål, oppgaven er å finne ut hvilke minimumssteg en ridder vil ta for å nå målposisjonen.
Eksempler:
Input : (2 4) - knight's position (6 4) - target cell Output : 2 Input : (4 5) (1 1) Output : 3
En BFS-tilnærming for å løse problemet ovenfor har allerede blitt diskutert i tidligere stolpe. I dette innlegget diskuteres en dynamisk programmeringsløsning.
Forklaring av tilnærmingen:
La et sjakkbrett på 8 x 8 celler. La nå si at ridder er på (3 3) og målet er på (7 8). Det er mulige 8 trekk fra den nåværende posisjonen til ridder, dvs. (2 1) (1 2) (4 1) (1 4) (5 2) (2 5) (5 4) (4 5). Men blant disse vil bare to trekk (5 4) og (4 5) være mot målet og alle andre går bort fra målet. Så for å finne minimumstrinn, gå til enten (4 5) eller (5 4). Beregn nå minimumstrinn tatt fra (4 5) og (5 4) for å nå målet. Dette beregnes ved dynamisk programmering. Dermed resulterer dette i minimumstrinn fra (3 3) til (7 8).
La et sjakkbrett på 8 x 8 celler. La oss nå si at ridder er på (4 3) og målet er på (4 7). Det er mulige 8 trekk, men mot målet er det bare 4 trekk, dvs. (5 5) (3 5) (2 4) (6 4). Som (5 5) tilsvarer (3 5) og (2 4) er ekvivalent med (6 4). Så fra disse 4 poengene kan det konverteres til 2 poeng. Tar (5 5) og (6 4) (her). Beregn nå minimumstrinn tatt fra disse to punktene for å nå målet. Dette beregnes ved dynamisk programmering. Dermed resulterer dette i minimumstrinn fra (4 3) til (4 7).
Unntak: Når ridderen vil være i hjørnet og målet er slik at forskjellen mellom x og y koordinater med ridders posisjon er (1 1) eller omvendt. Da vil minimumstrinn være 4.
Dynamisk programmeringsligning:
1) dp[diffOfX][diffOfY] er minimumssteg tatt fra ridderposisjon til målposisjon.
2) dp[diffOfX][diffOfY] = dp[diffOfY][diffOfX] .
hvor diffOfX = forskjellen mellom ridders x-koordinat og målets x-koordinat
diffOfY = forskjell mellom ridders y-koordinat og målets y-koordinat
Nedenfor er implementeringen av tilnærmingen ovenfor:
// 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>
Produksjon:
3
Tidskompleksitet: O(N * M) hvor N er det totale antallet rader og M er det totale antallet kolonner
Hjelpeplass: O(N * M)