Кратчайший путь в Java Maze 2d int array
В настоящее время я застрял в проекте. Моя цель - использовать алгоритм Дейкстры.
Я понимаю, что начинаю с точки (0,0), смотрю на два узла рядом с начальной точкой, а затем сначала перехожу к наименьшему и смотрю на окружающие узлы. Мой лабиринт случайный, но чтобы облегчить его начало, скажем, что это мой лабиринт.
Я начну с (0,0) и хочу закончить на (9,9), числа - уровень ОПАСНОСТИ, и мы стремимся к самому безопасному пути, а не к самому короткому.
Мне нужен толчок, чтобы понять, как это настроить. Я знаю, что мне нужен список или путь, чтобы оставаться там, где я нахожусь и куда хочу смотреть. но я не знаю, как это сделать в java.
import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class solver {
/**
* @param args
*/
public static int[][]maze;
public static int[][]openlist;
public static int[][]closed;
public static int[][]copy;
public static int danger;
public static int size=100;
static int Max=9;
static int Min=0;
public static List path = new ArrayList();
public static void main(String[] args) {
// TODO Auto-generated method stub
maze = new int[size][size];
openlist = new int[size][size];
closed = new int[size][size];
copy = new int[size][size];
filler(maze);
copy=dijstkra();
printer(maze);
//printer(copy);
EDSfAO(maze,0,0);
printer(openlist);
printer(copy);
}
private static Boolean notwall(int i, int j){
if((i>maze.length-1)||(j>maze.length-1)||(i<0)||(j<0))
{return false;}
return true;}
private static int[][] dijstkra(){
for(int i=0;i<maze.length;i++){
for(int j=0;j<maze.length;j++){
copy[i][j]=100000000;
}}
copy[0][0]=0;
return copy;
}
private static void EDSfAO(int[][] maze,int i,int j){
int min=100000000;
int holdx = 0;
int holdy = 0;
openlist[i][j]=1;
danger=copy[i][j];
if(i==maze.length-1&&j==maze.length-1){
printer(copy);
for(holdx=0;holdx<path.size();holdx++){
System.out.print(path.get(holdx));
}
}
else{
if(notwall(i+1,j)&&openlist[i+1][j]!=1){
copy[i+1][j]=danger+maze[i+1][j];
} if(notwall(i,j+1)&&openlist[i][j+1]!=1){
copy[i][j+1]=danger+maze[i][j+1];
} if(notwall(i,j-1)&&openlist[i][j-1]!=1){
copy[i][j-1]=danger+maze[i][j-1];
} if(notwall(i-1,j)&&openlist[i-1][j]!=1){
copy[i-1][j]=danger+maze[i-1][j];
}
for(int x=0;x<maze.length;x++){
for(int y=0;y<maze.length;y++){
if(openlist[x][y]!=1){
if(min>copy[x][y]){
min=copy[x][y];
holdx=x;
holdy=y;
}
}
}}
moveToPosition(holdx,holdy);
}
}
private static void moveToPosition(int x, int y) {
openlist[x][y]=1;
path.add("("+x+","+y+")");
openlist[x][y]=1;
EDSfAO(maze,x,y);
}
private static void printer(int[][] maze) {
// TODO Auto-generated method stub
for(int i=0;i<maze.length;i++){
for(int j=0;j<maze.length;j++){
System.out.print("["+maze[i][j]+"]");
}
System.out.println();
}
}
public static void filler(int[][] maze){
for(int i=0;i<maze.length;i++){
for(int j=0;j<maze.length;j++){
//If i=0 AND j=0 then maze[0][0]= 0(start) OR i= maze.length-1 AND j= maze.length-1 then maze[maze.length][maze.length]=0
if((i==0 && j==0) || (i==maze.length-1 && j==maze.length-1)){
maze[i][j]=0;
}else{
maze[i][j]=Min + (int)(Math.random() * ((Max - Min) + 1));
}
}
}
}
}
Лабиринт соединен без стен, все ящики - комнаты. Я пытался работать над этим какое-то время, и мне действительно пригодился толчок. Я просмотрел много видео об алгоритме Дийсткра, и сейчас я действительно заблудился.
Я добавил массив, в котором я сохраняю опасность. Он начинается с создания любого узла 100000000, но начальный узел (0,0) равен 0.
Может кто-нибудь помочь мне со следующими шагами Я понимаю, что это домашнее задание, но я готов время истекает, и действительно нужны указатели.
ОБНОВЛЕНИЕ:
Хорошо, у меня все работает. Он печатает путь, который он берет, но если он находит лучший путь, он печатает оба, кто-нибудь может помочь мне исправить это.
Также он ломается, если я использую элемент 100X100, может кто-нибудь сказать мне, почему? Это последнее из настоящих «программных заданий». Как и следовало ожидать, здесь будут задействованы графики (с изюминкой); но, конечно же, придется решать и некоторые проблемы. Инструкция
Представьте себе «игру в подземелье», в которой все комнаты расположены в идеальной сетке с квадратной средой.В каждой комнате есть существо, представляющее некоторую степень опасности в диапазоне от 0 (безвредно) до 9 (избегание было бы разумным). Цель состоит в том, чтобы найти путь через подземелье от начала до конца, который сводит к минимуму общую опасность.
Каждая комната, если она не находится на границе, существует только в направлениях вверх, вниз, влево и вправо (без диагоналей). Вход находится в верхнем левом углу (0,0), а выход - в правом нижнем углу (n-1, n-1).
Перечислите все «комнаты», которые необходимо пройти, в виде пути с координатами комнат от начала до конца.
Например:
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (3,3) (4,3) (4,4)
Общая опасность = 11 Вход
Входной файл будет состоять из 100 строк по 100 цифр, 0–9. (Да, 10000 - это много комнат, но, к счастью, наш бесстрашный путешественник никогда не выходит из дома без портативного компьютера и коллекции электронных наборов данных на все случаи жизни, полученной во время прошлогоднего обмена подарками; вероятно, он был подарен повторно. ) *
* Для этого задания вам нужно будет сгенерировать свои собственные тестовые данные. Вот почему я не хожу на такие вечеринки ... Выходные данные
Программа должна записать выходные данные в файл (в формате, показанном выше, включая выходные данные «полная опасность»). Спасибо.
ОБНОВЛЕНИЕ 2: я обнаружил ошибку в коде. У меня есть
if(min>copy[x][y]){
min=copy[x][y];
holdx=x;
holdy=y;
}
Это заставит его проверять каждый путь, который есть в данной точке, мой кратчайший путь больше, чем другой путь, как мне это исправить?
Что Я скучаю? ОБНОВЛЕНИЕ Я закончил это спасибо за ОЧЕНЬ НЕБОЛЬШУЮ помощь.