Найти путь фиксированной длины через двумерный массив, который дает максимальную сумму
Я просмотрел много кодов форума, похожих на этот вопрос, но я все еще не могу решить свой вопрос. По сути, для двумерного квадратного массива размера n, заполненного целыми числами в пределах [-100,100], мне нужно найти максимальную сумму, учитывая, что длина пути равна 10. Это делается начиная с определенной заданной сетки (обозначается *). Недопустимо посещать одну и ту же сетку дважды.
Пример теста будет:
-55 34 -51 35 1
-76 26 69 61 *
68 98 17 85 81
-27 -69 49 42 83
-10 31 44 75 -41
Будет производить максимальную сумму 637, Обозначается путем: 61 69 26 98 17 85 81 83 42 75
Если я не ошибаюсь, проблема с моим кодом заключается в маркировке сеток, которые я посещал ранее. Но я не знаю, как это решить..
Ниже мой код:
import java.util.*;
class Maze
{
static int[][] matrix;
static int counter = 0;
static int size = 0;
static int maximum = -100000;
static int result = -1000000;
static int currMax;
static int topMax, downMax, leftMax, rightMax;
public static void main(String [] args)
{
Scanner sc = new Scanner(System.in);
size = sc.nextInt();
matrix = new int[size][size];
int xcord = 0;
int ycord = 0;
for (int i=0; i<size; i++){
for (int j=0; j<size; j++){
if (sc.hasNextInt()){
int util = sc.nextInt();
matrix[i][j] = util;
}
else{
String utilStr = sc.next();
xcord = i;
ycord = j;
matrix[i][j] = -2000;
}
}
}
result = 2000 + findMax(xcord, ycord);
System.out.println(result);
}
static int findMax(int currx, int curry){
if (counter >= 9){
return matrix[currx][curry];
}
else {
counter = counter+1;
System.out.println("Round: "+counter);
System.out.println("currx: "+currx+" curry: "+curry);
int temp = matrix[currx][curry];
matrix[currx][curry] = -2000;
downMax = -10000; //To reset it for comparison
if (currx+1 != size && matrix[currx+1][curry] == -2000){
downMax = findMax(currx+1,curry);
}
rightMax = -10000;
if (curry+1 != size && matrix[currx][curry+1] == -2000){
rightMax = findMax(currx,curry+1);
}
topMax = -10000;
if (currx-1 >=0 && matrix[currx-1][curry] == -2000){
topMax = findMax(currx-1,curry);
}
leftMax = -10000;
if (curry-1 >= 0 && matrix[currx][curry-1] == -2000){
leftMax = findMax(currx,curry-1);
}
matrix[currx][curry] = temp;
currMax = Math.max(downMax,rightMax);
currMax = Math.max(currMax, topMax);
currMax = Math.max(currMax, leftMax);
maximum = currMax + temp;
return maximum;
}
}
}
Заранее спасибо!!
2 ответа
Вот мое решение и объяснения:
public static int MAX_DEPTH = 10;
static Integer[][] matrix;
static Coord[] directions = {
new Coord(-1, 0),
new Coord(1, 0),
new Coord(0, -1),
new Coord(0, 1)
};
private static class Coord {
int row;
int col;
private Coord(int row, int col) {
this.col = col;
this.row = row;
}
private Coord newPosition(Coord relative) {
return new Coord(row + relative.row, col + relative.col);
}
}
Сначала я определяю матрицу как двумерный массив Integer а не инт. Это позволяет легко отмечать посещенные позиции и позицию "*", используя null, Это просто удобство.
Я использую небольшой внутренний класс Coord чтобы помочь мне с вычислениями координат. Как вы видите, я создал статический массив всех направлений, которые мне нужно исследовать на каждом этапе, поскольку это упростит рекурсивный метод и предотвратит ненужные повторения кода, которые впоследствии могут потребоваться исправить в четырех разных местах.
private static Coord fillMatrix() {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
matrix = new Integer[size][size];
Coord coord = new Coord(0, 0);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (sc.hasNextInt()) {
int util = sc.nextInt();
matrix[i][j] = util;
} else {
sc.next();
coord.row = i;
coord.col = j;
matrix[i][j] = null;
}
}
}
sc.close();
return coord;
}
мой fillMatrix Метод заполняет матрицу и возвращает координату "*" (точнее, нецелого числа во входных данных). Он основан на вашем, с этими заметками:
- Я отмечаю "*" место в матрице с нуля.
- Вы должны закрыть каждый сканер, который вы открываете.
- Нет необходимости определять переменную для хранения значения сканирования "*", так как мы его не используем. Java позволяет вызывать методы, которые возвращают значение, нигде не присваивая это значение.
private static boolean isLegalPosition(Coord position) {
if ( position.row < 0 || position.row >= matrix.length ) {
return false;
}
if ( position.col < 0 || position.col >= matrix[0].length ) {
return false;
}
return matrix[position.row][position.col] != null;
}
Учитывая позицию в матрице, этот метод проверяет, является ли она допустимой - находится ли она в границах массивов (мы должны предположить, что существует хотя бы одна строка), и не отмечена ли она null (Посетил / старт).
Теперь мы подошли к самому рекурсивному методу. Вы передаете ему текущую глубину и текущую накопленную сумму, в дополнение, конечно, к текущей позиции, с которой он должен начать поиск. Предполагается, что эта позиция уже помечена нулем.
private static Integer findMax(Coord currPosition, int currDepth,
int currSum) {
// Recursion end: if we reached a depth of 10, we have the maximum at
// the current position
if (currDepth == MAX_DEPTH) {
return currSum;
}
// Find the greatest number in all four directions. We start with an
// unknown Max value.
Integer currMax = null;
for (Coord direction : directions) {
Coord newPos = currPosition.newPosition(direction);
// If the position is legal (inside the matrix and not visited),
// explore it by adding depth, and adding the current matrix
// value to the accumulated.
if (isLegalPosition(newPos)) {
// Save the value at the new position, and mark it as visited.
int matrixValue = matrix[newPos.row][newPos.col];
matrix[newPos.row][newPos.col] = null;
Integer newMax = findMax(newPos, currDepth + 1, currSum + matrixValue);
// Restore the value in the current matrix position so that
// upper level recursions don't think it's visited.
matrix[newPos.row][newPos.col] = matrixValue;
// Calculate the new max. If this is the first legal path, use
// it. Otherwise check which one is greater.
if (newMax != null) {
currMax = (currMax == null) ? newMax
: (newMax > currMax ? newMax : currMax);
}
}
}
return currMax;
}
Как видите, я держу переменную с именем currMax, который начинается как null, В итоге он станет максимальным среди всех чисел, собранных по четырем направлениям. Но может случиться так, что все четыре направления не смогли достичь глубины 10, потому что они врезались в стену и посещали позиции. В этом случае они вернут ноль, и если это происходит во всех четырех направлениях, мы возвращаем currMax - который null - также.
Если мы найдем законный путь в любом из направлений, мы обновим currMax с этим (если это больше, чем это, конечно).
На каждом шаге, прежде чем мы углубимся в рекурсию, мы помечаем новую позицию как нулевую, чтобы показать, что она была посещена, но постараемся восстановить ее, как только мы закончим с ней. В противном случае позиция останется отмеченной для посещения следующего направления, для которого она не должна рассматриваться visited,
Призыв к рекурсии из mainпосле заполнения матрицы, конечно, выглядит так:
Integer maxVal = findMax(startCoord, 0, 0);
То есть мы передаем ему координаты "*", начинающиеся с глубины 0 и с накопленной суммой 0. Почему 0, а не -2000? Потому что мы на самом деле не сравниваем это число ни с чем. Любой пройденный нами путь, который фактически достигнет глубины 10, вернет фактическую сумму пройденных им позиций, добавленную к этому нулю, независимо от того, является ли эта сумма отрицательной или положительной. Любой путь, который не заканчивается на глубине 10, вернет ноль. Так что нет необходимости в искусственных ценностях.
Как насчет этого. Текущий путь поиска сохраняется в контейнере Stack, который помогает идентифицировать позиции, которые мы уже видели. На каждом уровне рекурсии мы ищем поля S/N/W/E текущей позиции и устанавливаем currMax на текущую сумму, если текущий размер стека == 11 (начальное поле плюс остальные).
import java.util.*;
import java.io.*;
class Coord {
public Coord(int i,int j) {
this.i=i;
this.j=j;
}
public boolean equals(Object o) {
return ((Coord)o).i == i && ((Coord)o).j == j;
}
public int i;
public int j;
};
class Main {
static int[][] matrix;
static int counter = 0;
static int size = 0;
static int currMax=-2000;
static Stack<Coord> currStack = new Stack<Coord>();
public static void main(String [] args) throws FileNotFoundException
{
FileInputStream f=new FileInputStream(new File("/home/bla/bla.txt"));
Stack<Coord> s = new Stack<Coord> ();
Scanner sc = new Scanner(f);
size = sc.nextInt();
matrix = new int[size][size];
int xcord = 0;
int ycord = 0;
for (int i=0; i<size; i++){
for (int j=0; j<size; j++){
if (sc.hasNextInt()){
int util = sc.nextInt();
matrix[i][j] = util;
}
else{
String utilStr = sc.next();
s.push(new Coord(i,j));
}
}
}
int sum=0;
System.out.println(findMax(s,sum));
Iterator<Coord> i=currStack.iterator();
int ss=0;
while(i.hasNext()) {
Coord c = i.next();
System.out.println(c.i+" "+c.j+" "+matrix[c.i][c.j]);
ss+=matrix[c.i][c.j];
}
System.out.println("<"+ss+">");
}
static int findMax(Stack<Coord> s,int sum){
// TOP
if(s.lastElement().i > 0 && (s.search(new Coord(s.lastElement().i-1,s.lastElement().j ))==-1) ) {
Stack<Coord> nstack = (Stack<Coord>)s.clone();
nstack.push(new Coord(s.lastElement().i-1,s.lastElement().j ));
int nsum = sum + matrix[nstack.lastElement().i][nstack.lastElement().j];
if(nstack.size()<11) {
nsum=findMax(nstack,nsum);
}
else {
if(nsum > currMax) {
currMax = nsum;
currStack = nstack;
}
}
}
// BOTTOM
if(s.lastElement().i+1 < matrix.length && (s.search(new Coord(s.lastElement().i+1,s.lastElement().j ))==-1) ) {
Stack<Coord> nstack = (Stack<Coord>)s.clone();
nstack.push(new Coord(s.lastElement().i+1,s.lastElement().j ));
int nsum = sum + matrix[nstack.lastElement().i][nstack.lastElement().j];
if(nstack.size()<11) {
nsum = findMax(nstack,nsum);
}
else {
if(nsum>currMax) {
currMax = nsum;
currStack = nstack;
}
}
}
// LEFT
if(s.lastElement().j > 0 && (s.search(new Coord(s.lastElement().i ,s.lastElement().j-1))==-1) ) {
Stack<Coord> nstack = (Stack<Coord>)s.clone();
nstack.push(new Coord(s.lastElement().i ,s.lastElement().j-1));
int nsum = sum + matrix[nstack.lastElement().i][nstack.lastElement().j];
if(nstack.size()<11) {
nsum = findMax(nstack,nsum);
}
else {
if(nsum>currMax) {
currMax = nsum;
currStack = nstack;
}
}
}
// RIGHT
if(s.lastElement().j+1 < matrix[0].length && (s.search(new Coord(s.lastElement().i ,s.lastElement().j+1))==-1) ) {
Stack<Coord> nstack = (Stack<Coord>)s.clone();
nstack.push(new Coord(s.lastElement().i ,s.lastElement().j+1));
int nsum = sum +matrix[nstack.lastElement().i][nstack.lastElement().j];
if(nstack.size()<11) {
nsum = findMax(nstack,nsum);
}
else {
if(nsum>currMax) {
currMax = nsum;
currStack = nstack;
}
}
}
return currMax;
}
}