Question

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 an integer 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 tokens. 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 e 2 3 2 x 2 12 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 m m

Answer 1

import java.util.Scanner;

public class ChessGame {

        static Scanner in = new Scanner(System.in);
        
        String chessBoard[][];
        int size;
        
        int maxPoints = 0;
        int maxPointsRoutes = 0;
        
        Integer solutions[][];
        
        public ChessGame() {
                size = Integer.parseInt(in.nextLine());
                chessBoard = new String[size][size];
                
                for(int i=0; i<size; i++) {
                        chessBoard[i] = new String[size];
                        String line = in.nextLine();
                        String tokens[] = line.split(" ");
                        for(int j=0; j<size; j++) {
                                chessBoard[i][j] = tokens[j];
                        }
                }
        }
        
        private boolean isValidCell(int r, int c) {
                return (r >= 0) && (r < size) && (c >= 0) && (c < size);
        }
        
        private void findSolutionHelper(int startR, int startC, int points) {
                
                if(chessBoard[startR][startC].equals("e")) {
                        if(points > maxPoints) {
                                maxPoints = points;
                                maxPointsRoutes = 1;
                        } else if(points == maxPoints) {
                                maxPointsRoutes += 1;
                        }
                        return;
                }
                
                
                
                if(chessBoard[startR][startC].equals("x")) {
                        // route not possible
                        return;
                }
                
                int pointOfCell = 0;

                if(!chessBoard[startR][startC].equals("s")) {
                        pointOfCell = Integer.parseInt(chessBoard[startR][startC]);
                }
                
                if(isValidCell(startR, startC - 1)) {
                        findSolutionHelper(startR, startC - 1, pointOfCell + points);
                }
                if(isValidCell(startR - 1, startC)) {
                        findSolutionHelper(startR - 1, startC, pointOfCell + points);
                }
                if(isValidCell(startR - 1, startC - 1)) {
                        findSolutionHelper(startR - 1, startC, pointOfCell + points);
                }
        }

        private void findSolution() {
                solutions = new Integer[size][size];
                maxPoints = 0;
                maxPointsRoutes = 0;
                findSolutionHelper(size-1, size-1, 0);
                System.out.println(maxPoints + " " + maxPointsRoutes);
        }
        
        public static void main(String[] args) {
                int numTestCases = Integer.parseInt(in.nextLine());
                
                while(numTestCases-- > 0) {
                        new ChessGame().findSolution();
                }
                
        }

}

please upvote. Thanks!