Форум программистов, компьютерный форум, киберфорум
Наши страницы

Java SE (J2SE)

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
#1

Поиск кратчайшего пути в лабиринте. Выход за границы массива - Java SE

20.04.2013, 10:12. Просмотров 3276. Ответов 6
Метки нет (Все метки)

Собственно сабж. При лабиринте, например, 4х4 или 5х5 программа работает верно. А если пытаюсь ввести 10x10, то выход за границы массива. Где я ошибся?

представление лабиринта как массив char'ов:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
........
char[][] maze = new char[xLength][yLength];
        String[] str = new String[xLength+1];
        for(int i = 0; i < xLength+1; i++)
            str[i] = input.nextLine(); //получаем лабиринт в массиве типа String
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < str.length; i++)
            result.append(str[i]);
        String newstr = result.toString(); 
        newstr = newstr.replaceAll("\n", ""); //преобразуем массив типа String в переменную String и удаляем в ней все переносы строки
        for (int i = 0; i < xLength; i++) 
        { 
            for (int j = 0; j < yLength; j++) 
            { 
                maze[i][j] = newstr.charAt(c); //преобразуем лабиринт в двумерный массив типа char 
                if(maze[i][j] == 'A')
                {
                    sCoordX = i;
                    sCoordY = j;
                }
                c++; 
            } 
        }
........
сама реализация
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public void findPath(int row, int col) {
        if (maze[row][col] == 'B') {
            solved = true;
            return;
        }
 
        maze[row][col] = ' ';
 
        if (maze[row + 1][col] == '.' || maze[row + 1][col] == 'B') {
            findPath(row + 1, col);
        }
        else if (maze[row][col + 1] == '.' || maze[row][col + 1] == 'B') {
            findPath(row, col + 1);
        }
        else if (maze[row - 1][col] == '.' || maze[row - 1][col] == 'B') {
            findPath(row -1, col);
        }
        else if (maze[row][col - 1] == '.' || maze[row][col - 1] == 'B') {
            findPath(row, col - 1);
        }
        else {
            wall = true;
            return;
        }
 
        if (wall) {
            wall = false;
            findPath(row, col);
        }
 
        if (solved) {
            maze[row][col] = '+';
        }
 
    }
Компилятор ругается java.lang.ArrayIndexOutOfBoundsException: 10 на все строки с if'ами (10-21 строки).

Вот что ввожу для теста:
Код
10
10
A......... 
##....##.. 
.####...## 
.......... 
.......### 
.....#.... 
####...### 
B......... 
#...#.###. 
..........
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2013, 10:12
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Поиск кратчайшего пути в лабиринте. Выход за границы массива (Java SE):

Выход за границы массива - Java SE
Доброго времени суток. Начинаю писать на Java, возникла задача взять русский алфавит(вместе со знаками препинания), перемешать его в...

Исключительная ситуация. Выход за границы массива - Java SE
В программе рассматривается выход за границы массива. Создается исключительная ситуация в которой увеличивается размер массива /* *...

Выход за границы массива, но не знаю как исправить - Java SE
Здравствуйте товарищи. Есть задание: Дан двумерный массив вещественных чисел произвольной размерности. Разработать программу, которая...

Нахождение кратчайшего расстояния на графе с восстановлением пути - Java SE
Здравствуйте, помогите разобраться. На вход программе подается граф в виде матрицы смежности. Необходимо найти кратчайшее расстояние от...

Создание и применение Web-визуализатора по теме "Поиск в лабиринте" - Java
Привет всем программистам!!!! Меня зовут Наталья. Зашла на этот с форум с целью молить о помощи. Дали мне тему диплома:&quot;Создание и...

Поиск кратчайшего пути в лабиринте - Алгоритмы
Добрый день, знаю два алгоритма. 1. А - стар 2. Волновой Нужен какой нибудь 3... Ссылки приветствуются=)

6
.::.DIMA.::.
143 / 143 / 4
Регистрация: 26.10.2008
Сообщений: 782
20.04.2013, 12:05 #2
Потому что вы не проверяете условия выхода за границы массива.
Сделайте проверку, например,
Java
1
2
3
if(row + 1 < maze.length && col < maze[0].length)
    find(row + 1, col)
...
1
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
20.04.2013, 19:36  [ТС] #3
Цитата Сообщение от .::.DIMA.::. Посмотреть сообщение
Потому что вы не проверяете условия выхода за границы массива.
Сделайте проверку, например,
Java
1
2
3
if(row + 1 < maze.length && col < maze[0].length)
    find(row + 1, col)
...
Добавил, результат тот же самый.
Не понимаю, почему может выходить за границы массива, если я четко указываю размерность лабиринта?

Добавлено через 16 минут
Перебирал лабиринты, заметил, что выход за пределы массива случается в случае, если размерность > 7. Почему так?
0
.::.DIMA.::.
143 / 143 / 4
Регистрация: 26.10.2008
Сообщений: 782
20.04.2013, 22:11 #4
Выложите код полностью.
1
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
20.04.2013, 22:23  [ТС] #5
main class:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package foropenwaygroup;
 
import java.util.InputMismatchException;
import java.util.Scanner; 
 
/**
 * @author Eugene Mironenko
 */
public class TheShortestRoute 
{ 
 
    public static void main(String[] args) throws InputMismatchException //
    { 
        
        Scanner input = new Scanner(System.in);
        int c = 0; //количество символов в лабиринте
        int xLength, yLength; //длина и ширина лабиринта
        int sCoordX = -1, sCoordY = -1; //координаты начальной точки
        int eCoordX = -1, eCoordY = -1; //координаты конечной точки
        int len = 0;
        System.out.println("Введите длину лабиринта");
        xLength = input.nextInt();
        System.out.println("Введите ширину лабиринта");
        yLength = input.nextInt();
        System.out.println("Введите лабиринт в виде:\nA..#\n##.#\n#B.#\n####\n где A - начальная точка, B - конечная точка, . - пустое пространство, # - стена");
        char[][] maze = new char[xLength][yLength];
        String[] str = new String[xLength+1];
        for(int i = 0; i < xLength+1; i++)
            str[i] = input.nextLine(); //получаем лабиринт в массиве типа String
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < str.length; i++)
            result.append(str[i]);
        String newstr = result.toString(); 
        newstr = newstr.replaceAll("\n", ""); //преобразуем массив типа String в переменную String и удаляем в ней все переносы строки
//        String newstr = "A........." 
//                + "##....##.." 
//                + ".####...##" 
//                + ".........." 
//                + ".......###" 
//                + ".....#...." 
//                + "####...###" 
//                + "B........." 
//                + "#...#.###." 
//                + ".........."; 
        for (int i = 0; i < xLength; i++) 
        { 
            for (int j = 0; j < yLength; j++) 
            { 
                maze[i][j] = newstr.charAt(c); //преобразуем лабиринт в двумерный массив типа char 
                if(maze[i][j] == 'A')
                {
                    sCoordX = i;
                    sCoordY = j;
                }
                else if(maze[i][j] == 'B')
                {
                    eCoordX = i;
                    eCoordY = j;
                }
                c++; 
            } 
        }
        if(sCoordX != -1 && sCoordY != -1 && eCoordX != -1 && eCoordY != -1)
        {
            MazeSolver calc = new MazeSolver(maze);
            try
            {
                calc.findPath(sCoordX, sCoordY); //поиск кратчайшего пути
            }
            catch(ArrayIndexOutOfBoundsException e)
            {
                System.out.println("Плохой массив или такого пути не существует");    
            }
            catch(StringIndexOutOfBoundsException e)
            {
                System.out.println("Ошибка в вводе");
            }
            maze[sCoordX][sCoordY] = 'A'; //чтобы было красиво ;)
            for(int i = 0; i < xLength; i++)
            {
                for(int j = 0; j < yLength; j++)
                {
                    if(maze[i][j] == '+')
                        len++;
                }
            }
            if(len != 0)
            {
                len++;
                System.out.println();
                System.out.println("Кратчайший путь в лабиринте:"); 
                calc.printMaze(xLength, yLength);
                System.out.println("Длина кратчайшего пути = " + len);
            }
            else System.out.println("Такого пути нет :(");  
        } 
        else System.out.println("Нет точки старта или финиша!");
    }
}
MazeSolver:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package foropenwaygroup;
 
public class MazeSolver 
{
    boolean wall = false;
    char[][] maze;
    boolean solved;
    int startX;
    int startY;
 
    public MazeSolver(char[][] in_maze) { //конструктор
        maze = in_maze;
    }
 
    public void findPath(int row, int col) { //реализация метода нахождения кратчайшего пути
        if (maze[row][col] == 'B') {
            solved = true;
            return;
        }
 
        maze[row][col] = '#';
 
        if (maze[row + 1][col] == '.' || maze[row + 1][col] == 'B') {
            findPath(row + 1, col);
        }
        else if (maze[row][col + 1] == '.' || maze[row][col + 1] == 'B') {
            findPath(row, col + 1);
        }
        else if (maze[row - 1][col] == '.' || maze[row - 1][col] == 'B') {
            findPath(row -1, col);
        }
        else if (maze[row][col - 1] == '.' || maze[row][col - 1] == 'B') {
            findPath(row, col - 1);
        }
        else
        {
            wall = true;
            return;
        }
 
        if (wall) {
            wall = false;
            findPath(row, col);
        }
 
        if (solved) {
            maze[row][col] = '+';
        }
 
    }
 
    public void printMaze(int rows, int cols) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(maze[i][j]);
            }
 
            System.out.println();
        }
    }
}
0
.::.DIMA.::.
143 / 143 / 4
Регистрация: 26.10.2008
Сообщений: 782
20.04.2013, 22:53 #6
Я проверил на примере, который у вас закомментирован. Ошибка происходит, при вызове функции findPath с параметрами 9, 9. Очевидно, при первой же попытке обратиться к элементу maze[row + 1][col], обращение происходит по индексам 10, 9, что выходит за границы массива.

Как я и говорил, делайте проверку, на то, что индексы не превыщают возможных значений или меняйте алгоритм.
Например, в самом начале функции напишите:

Java
1
2
3
4
5
 if(row == maze.length - 1 && col == maze[row].length - 1) {
            System.out.println("Достигнули крайнюю клетку лабиринта");
            // что-то делаем ещё
            return ;
 }
Добавлено через 1 минуту
Генерируется исключение или нет зависит скорее всего не от размера лабиринта а от вида лабиринта.
1
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
20.04.2013, 23:10  [ТС] #7
Думаю, что имеет смысл изменить алгоритм. Спасибо.
0
20.04.2013, 23:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.04.2013, 23:10
Привет! Вот еще темы с ответами:

Поиск кратчайшего пути в лабиринте - Алгоритмы
Пишу программу для нахождения (и вывода) кратчашего пути в лабиринте, заданном в текстовом файле в виде бинарной матрицы. Пример: 1 1 1...

Поиск пути в лабиринте - Delphi
В приведенном ниже плане лабиринте буквой А помечен мобильный агент, буквой В выход из лабиринта. Цель агента – выйти из лабиринта. ...

Поиск пути в лабиринте - Visual Basic
Вобщем задача проста: Дан лабиринт в виде массива. Цифрами 1 являются стены, 0-пути, 3-выход из лабиринта. Написать программу для поиска...

Поиск пути в лабиринте - C#
Здравствуйте! Я написал программу поиска пути в двумерном массиве используя волновой алгоритм. Но мне щас надо переделать свой код по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru