I need help with this problem quickly In Java or python or c++. Help me someone!
ID: 3874908 • Letter: I
Question
I need help with this problem quickly In Java or python or c++. Help me someone!!!!!!!!!!
Your goal for this challenge will be to determine the best path for moving across a matrix of integers. For each matrix of size n, you will start in the top-left corner (0, 0) and must end in the bottom-right corner (n, n) by moving only down or to the right (you cannot move up or to the left). The value in each cell of the matrix represents the number of points you get from visiting the cell. Your algorithm should find the path that results in the maximum possible number of points while successfully crossing the matrix. In the case of a tie, your algorithm should prefer the path that would move to the right before it would move down. Input: A square matrix of integers. Each row will be separated by a semicolon; each column within a row will be separated by a space. Examples:
Output
A comma separated list of your moves across the matrix. Each move should be specified by:
Examples of correct solutions to the matrices listed above:
Test 1
Test Input
Download Test Input
Expected Output
Download Test Output
Test 2
Test Input
Download Test Input
Expected Output
Download Test Output
Test 3
Test Input
Download Test Input
Expected Output
Download Test Output
Running Test 1... failed!
Test 1 Input
Expected Output
Your Output
End Test Case Output Tab Content
Running Test 2... failed!
Test 2 Input
Expected Output
Your Output
End Test Case Output Tab Content
Running Test 3... failed!
Test 3 Input
Expected Output
Your Output
My work
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
public class Main {
/**
* Iterate through each line of input.
*/
public static void main(String[] args) throws IOException {
InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
BufferedReader in = new BufferedReader(reader);
String line;
while ((line = in.readLine()) != null) {
System.out.println(line);
}
}
}
Explanation / Answer
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Y2018.January;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
*
* @author sambh
*/
public class Download {
private static int getPathWeight(int[][] arr, String path) {
int r = 0, c = 0;
int sum = arr[r][c];
for (int i = 0; i < path.length(); i++) {
if (path.charAt(i) == 'd')
r++;
else
c++;
sum += arr[r][c];
}
return sum;
}
public static String path(int arr[][], int r, int c, String path){
if (r == arr.length -1 && c == arr[r].length -1)
return path;
if (r == arr.length -1)
return path(arr, r, c +1, path + 'r');
if (c == arr[r].length -1)
return path(arr, r +1, c, path + 'd');
String rPath = path(arr, r, c +1, path + 'r');
String dPath = path(arr, r +1, c, path + 'd');
if (getPathWeight(arr, rPath) >= getPathWeight(arr, dPath))
return rPath;
return dPath;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("INPUT:");
String arrText = br.readLine();
String[] rows = arrText.split(";");
int[][] arr = new int[rows.length][];
for (int i = 0; i < rows.length; i++) {
String[] cols = rows[i].split(",");
arr[i] = new int[cols.length];
for (int j = 0; j < cols.length; j++)
arr[i][j] = Integer.parseInt(cols[j]);
}
System.out.println(path(arr, 0, 0, ""));
}
}