Very important, I DO NOT WANT C++ CODE, WRITE THE ALGORITHM IN THE FOLLOWING FOR
ID: 3708988 • Letter: V
Question
Very important, I DO NOT WANT C++ CODE, WRITE THE ALGORITHM IN THE FOLLOWING FORMAT
Write the algorithm in a format like this :
//Applies dynamic programming to compute the largest number of
//coins a robot can collect on an n × m board by starting at (1, 1)
//and moving right and down from upper left to down right corner
//Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and 0
//for cells with and without a coin, respectively
//Output: Largest number of coins the robot can bring to cell (n, m)
F[1, 1]? C[1, 1]; for j ? 2 to m do F[1, j ]? F[1, j ? 1] + C[1, j ]
for i ? 2 to n do
F[i, 1]? F[i ? 1, 1] + C[i, 1]
for j ? 2 to m do
F[i, j ]? max(F[i ? 1, j ], F[i, j ? 1]) + C[i, j ]
return F[n, m]
Exercise 8.1, problem 7 (a) only A chess rook can move horizontally or vertically to any square in the same row or in the same column of a chessboard. Find the number of shortest paths by which a rook can move from one comer of a chessboard to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the first and the last squares. Solve the problem ic programming algorithm a. by a dynam Hint: a chessboard consists of 8x8 squares. You can assume that the chess rook is initially located at the top left corner. You wanted to find the number of the shortest path to move the rook from the top left corner to the bottom right corner. This problem is similar to the path counting problem from the slides. For example, there are 3 different shortest paths to move the rook from (1, 1) to (2, 3) (1, 1) to (1, 2) to (2, 2) to (2, 3) (1, 1) to (2, 1) to (2, 2) to (2, 3)Explanation / Answer
#include<bits/stdc++.h>
using namespace std;
int numberOfPaths(int m, int n)
{
int count[m][n];
for (int i = 0; i < m; i++)
count[i][0] = 1;
for (int j = 0; j < n; j++)
count[0][j] = 1;
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
count[i][j] = count[i-1][j] + count[i][j-1];
}
return count[m-1][n-1];
}
int main()
{
cout << numberOfPaths(8, 8);
return 0;
}
Ok so let's see what the algorithm is. 1st since we need the smallest path, our rook cannot go backward. So the only possible ways to move is either to right or towards the bottom. Now if we follow this, irrespective of the path we choose, the length of the path will be the same. now to count the path number, we use DP.
NOTE: This algorithm is valid for any matrix. we use 8x8 since it is a chessboard.
the first column and first row are filled with 1. This is because, irrespective of the number of squares we travel, the no. of ways to travel to that box from the starting point is 1. For the middle boxes, the number of ways to travel to any middlebox is equal to the number of ways to travel to the box above it + the number of ways to travel to the box present to the left of it. If we iterate this algorithm till the last (right bottom corner) element, we get the number of ways to reach that element which is equal to the number of shortest paths to reach there.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.