Chess board Puzzle

general
, ,
1

Implement using c/c++

You’re given a chess board with dimension n x n. There’s a king at the bottom right square of the board marked with s. The king needs to reach the top left square marked with e. The rest of the squares are labeled either with a number p (marking a point) or with x marking an obstacle. Note that the king can move up, left and up-left (diagonal) only. Find the maximum points the king can collect and the number of such paths the king can take in order to do so.
Input Format
The first line of input consists of an integer t. This is the number of test cases. Each test case contains a number n which denotes the size of board. This is followed by n lines each containing n space separated integers.
Output Format
For each case, print in a separate line the maximum points that can be collected and the number of paths available in order to ensure maximum, both values separated by a space. If e is unreachable from s, print 0 0.
Sample Input
3
3
e 2 3
2 x 2
1 2 s
3
e 1 2
1 x 1
2 1 s
3
e 1 1
x x x
1 1 s
Sample Output
7 1
4 2
0 0
Constraints
1 <= t <= 100
2 <= n <= 200
1 <= p <= 9

3 Likes
2

Classical dp problem :slight_smile:

3

Any solution for this question, kindly let me know how solve it, thanks in advance

4

As @anon55659401 said, it is a classic Dynamic Programming problem and you can probably find exactly the same problem online but its better in my opinion that you figure out at least some part of the solution for yourself.
The following link describes a very similar problem. Read it and try to come up with a solution to your problem. 1

Hint

Number of ways to reach an obstacle is 0

After you are done solving that you can try 2

Some advice for future posts:

  1. Don’t just copy paste the problem statement if you have a link to the source available.
1 Like