Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / Imagine that you are placed on a grid with n spaces in every row and n spaces in every column
Imagine that you are placed on a grid with n spaces in every row and n spaces in every column. You can start anywhere along the bottom row of the grid, and you must move to the top row of the grid. Each time you move, you can either move directly up (staying in the same column, but moving up a row), up and to the left (moving over one column and up one row), or up and to the right (moving over one column and up one row). You cannot move up and to the left if you are in the leftmost row, and you cannot move up and to the right if you are in the right most row.
Each time you move, you are either paid or pay; that is, every legal move from square x to square y is assigned a real value p(x, y). Sure, p(x, y) can also be 0.
Give a dynamic programming algorithm to compute your sequence of moves to receive the maximum payoff to move from the bottom of the grid to the top of the grid. (Your maximum payoff may be negative.) You must calculate the value of the optimal solution (i.e., the payoff) and the solution itself (i.e., the sequence of moves). Again, you can start at any square in the bottom row and end in any square in the top row.
Answer:
You can refer the following figure to understand different positions in a chessboard.
Now there's this Knight that starts at position A1 which needs to end up at some position XY(eg: D4). The knight can only move in an L shape, i.e., It moves to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally.
So in our example, the knight starts at A1 and should end up at D4 in some k moves. A movement is counted when the knight makes a horizontal and vertical or vertical and horizontal change in its position(The L- Shaped) as discussed earlier.
The problem is to devise an algorithm that calculates the number of ways the knight can end up at XY from A1 in k moves.
Consider our example (A1 to D4)
XY=D4
Let k=2
We have to calculate N(k,x,y)
N(k,x,y)=8 in this case. From A1, C2 and B3 can be reached in two ways. From C2 and B3, D4 can be reached again in two ways, which gives a total of 8 different ways in 2 moves.
PFA
