Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/15: Рейтинг темы: голосов - 15, средняя оценка - 4.67
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
1

Поиск кратчайшего пути в матрице или установка факта, что такового не существует

10.03.2014, 18:59. Просмотров 3067. Ответов 13
Метки нет (Все метки)

Всем привет!!!я начал решать задачку и у меня не получается, а не получается у меня самое главное понять как её нужно сделать , помогите пожалуйста !!! Итак вот описание
Задается квадратная матрица матрица (NxN) и размер "корабля" (MxM) . задается то что начальная точка находится в левом верхнем углу , а конечная в правом нижнем , также известно что если в матрице встречается символ "." (точка ) следовательно это проходимое место , если встретится "*" то непроходимое , и найти нужно длину самого короткого пути либо убедиться что пути нет.
Подскажите пожалуйста в какую сторону копать или мб кто нибудь встречался с подобными заданиями, или какой нибудь ресурс посвященный алгоритму знает!!!
Всем спасибо за внимание!
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.03.2014, 18:59
Ответы с готовыми решениями:

Поиск кратчайшего пути в матрице
Привет всем, есть задание: "Считать из файла input3.txt двумерный массив. Каждая ячейка имеет вес...

Поиск кратчайшего пути в матрице через рекурсию
Есть задача: найти кратчайший путь в матрице,представляющий из себя сумму значений ее элементов....

Нахождение кратчайшего пути по матрице, или передвижение привидений в игре Пакмен
Подскажите пожалуйста как правильно реализовать? Имеются координаты x,y пакмана и приведения. Я...

Создание графа по матрице и поиск кратчайшего пути из одного графа в другой
Доброго времени суток. Задали задание по матрице составить граф и написать функции 1 функция...

Поиск кратчайшего пути
В одном массиве даны все возможные комбинации чисел (0,1,2,3,4). Представляют собой города. В...

13
Igor3D
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
10.03.2014, 19:19 2
Это задачка на "динамику" (усложненная "размерами"), что не так уж просто. Поэтому не получается сходу = нормально. Метода такая: в каждой клетке храним величину минимального пути до нее + координаты клетки из которой пришли. Теперь "ходим" всеми возможными ходами (проверяем влазит ли корабль) из первой клетки. Попав в клетку вычисляем путь до нее (предыдуший + 1) и сравниваем с записанным в клетке. Если новый путь оказался короче - обновляем информацию в клетке и делаем все ходы из нее. На первый взгляд это ужасно - огромное число вариантов! Но на самом деле большинство комбинаций отсеется т.к. "старый путь короче". В конце-концов не остается клеток для перебора, тогда смотрим на правую нижнюю - если там сидит путь, то он минимальный
1
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
10.03.2014, 19:21  [ТС] 3
спасибо буду пробовать!
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
10.03.2014, 22:30 4
Оглядываясь на решение которое предложил Igor3D хочу предложить свое.
Можно свести решение данной задачи к классической, и наверное более простым способом.
Основная идея - в каждую ячейку исходного массива пытаемся поместить левый верхний край корабля и проверяем помещается ли сам корабль, результат записываем в новый массив. Получаем массив (N-M)^2 и уже на нем решаем самую обычную задачу.
1
10.03.2014, 22:30
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
11.03.2014, 08:13  [ТС] 5
спасибо за совет, но я не очень понял как это так
Цитата Сообщение от wingblack Посмотреть сообщение
в каждую ячейку исходного массива пытаемся поместить левый верхний край корабля и проверяем помещается ли сам корабль, результат записываем в новый массив
Это то есть пытаемся свести задачу к тому чтобы было подобие корабля размером 1х1 , а кстати можно поподробнее ( ссылку или ещё что -нибудь) к решению таких классических задач
Спасибо!
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
11.03.2014, 11:28 6
Цитата Сообщение от Misha_prog Посмотреть сообщение
Это то есть пытаемся свести задачу к тому чтобы было подобие корабля размером 1х1 , а кстати можно поподробнее ( ссылку или ещё что -нибудь) к решению таких классических задач
Спасибо!
Смотри задачи на поиск пути в лабиринте. Самый простой в понимании и реализации - волновой алгоритм (поиск в ширину). Ищите по запросу "алгоритм поиска пути в лабиринте", в том числе на данном форуме много тем.
Алгоритмы поиска на графах(википедия)

Добавлено через 10 минут
Цитата Сообщение от Misha_prog Посмотреть сообщение
спасибо за совет, но я не очень понял как это так
Вот пример не оптимизированного перевода в обычную задачу поиска пути.
C++
1
2
3
4
5
6
7
8
9
i=1..n-m
  j=1..n-m {
    flag=true
    k=i..i+m
      l=j..j+m
        if(a[k,l]= * ){flag=false}
    if(flag){b[i,j]= . }
    else {b[i,j]= * }
    }
1
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
16.03.2014, 11:12  [ТС] 7
Цитата Сообщение от wingblack Посмотреть сообщение
Получаем массив (N-M)^2
Извините, вы не подскажите почему получается (N-M)^2 новый размер ?
Спасибо!
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
16.03.2014, 11:57 8
Матрица размера (N-M)*(N-M) (даже более правильно будет (N-M+1)^2) полностью описывает возможные положения корабля размера M в поле размера N.
Если следить за положениями одного из угла корабля, то он всегда лежит в некотором квадрате со стороной (N-M+1).
Вот как пример какие положения полоска размера 3 может принимать внутри полоски размера 5
11100
01110
00111
Очевидно, что для задания положения полоски размера 3 достаточно взять только один из её краев, который будет располагаться в полоске размера (5-3+1)=3
1
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
16.03.2014, 12:59  [ТС] 9
понятно, Спасибо!

Добавлено через 24 минуты
что то не получается у меня опять , вот что понаделал
C++
1
2
3
4
5
6
7
8
9
10
11
    char *pMatrix = NULL;
    pMatrix = new char[(x_count + 1) * (x_count + 1)];
    for(int i = 0; i < x_count ; ++i)
    {
        for(int j = 0; j < x_count; ++j)
        {
            pMatrix[x_count  * i + j] = fgetc(pFile);
        }
 
        fgetc(pFile);
    }
считываю из файла исходную матрицу
далее создаю сконвертированную матрицу
C++
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
char *pMatrixConvert = new char[(x_count - y_count) * (x_count - y_count) ];
 
void MatrixConvert(char * pMatrix, char * pMatrixConvert, int x_count, int raft)
{
    for (int i = 0; i < (x_count - raft); ++i )
    {
        for (int j = 0; j < (x_count - raft) ; ++j)
        {
            bool flag = true;
            for (int k = i ; k <(i + raft) ; ++k)
            {
                for (int l = j ; l < (j + raft); ++l )
                {
                    if (pMatrix[x_count*k + l] == '*')
                        flag = false;
                }
            }
            if (flag)
            {
                pMatrixConvert[(x_count - raft)*i + j] = '.';
            }
            else
            {
                pMatrixConvert[(x_count - raft)*i + j] = '*';
            }
        }
    }
}
и вот сам волновой алгоритм которому передаю сконвертированную матрицу и ещё одну матрицу которая хранит номер шага до точки

C++
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
bool IsSolve(int x_count, char *pMatrix, int * pMatrixRes)
{
    
    for(int i = 0; i < x_count ; ++i)
    {
        for(int j = 0; j < x_count; ++j)
        {
            pMatrixRes[x_count * i + j] = 0;
        }
    }
    pMatrixRes[0] = 0;
    bool noSolution = true;
    int dx[] = {1, 0 , -1, 0};
    int dy[] = {0, -1, 0, 1};
    int xf = x_count - 1;
    int yf = x_count - 1;
    int n = 0;
    do
    {
        noSolution = true;
        for (int i = 0; i < x_count ; ++i)
        {
            for (int j = 0; j < x_count; ++j)
            {
                if (pMatrixRes[x_count * i + j] == n )
                {
                    for (int k = 0; k < 4; ++k)
                    {
                        if (CanGo(i, j, dx[k], dy[k], x_count, x_count, pMatrix, x_count) &&
                            pMatrixRes[x_count * (i + dx[k]) + (j + dy[k]) ] == 0)
                        {
                            noSolution = false;
                            pMatrixRes[x_count * (i + dx[k]) + (j + dy[k])] = n + 1;
                            if ((i + dx[k] == xf) && (j + dy[k] == yf))
                            {
                                return true;
                            }
                        }   
                    }
                }
                n++;
            }
        }
    }while (noSolution);
    return false;
}
и не работает
Спасибо за внимание !
0
salam
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
16.03.2014, 13:29 10
простите, совсем не ясно, какую роль играет размер корабля. ну есть у меня матрица и какие-то клетки проходимы, какие-то нет. найти кратчайший путь. где здесь размер?
0
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
16.03.2014, 17:59  [ТС] 11
Цитата Сообщение от salam Посмотреть сообщение
простите, совсем не ясно, какую роль играет размер корабля. ну есть у меня матрица и какие-то клетки проходимы, какие-то нет. найти кратчайший путь. где здесь размер?
Ну если честно то я не знаю , но как я полагаю что вот допустим есть поле ( 1 -непроходимое , 0 проходимое), вот допустим есть поле такое
00100
00100
01000
0000Ф
Сразу отмечу что пути для корабля размером 2х2 нет т к он "не пролезет" в этом маленьком перешейке а если будем рассматривать для корабля 1х1 то он дойдёт до финишной точки (финишная точка - Ф) вот наверное в этом и есть разница
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
16.03.2014, 18:44 12
Цитата Сообщение от Misha_prog Посмотреть сообщение
и не работает
Спасибо за внимание !
А как конкретно оно не работает? Попробуйте сделать вывод матриц на экран и посмотреть правильно ли оно работает.

Голова сейчас не варит чтобы разбираться в этом коде.
1
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
16.03.2014, 19:22  [ТС] 13
Да я выводил) там почему то вниз не идет то есть допустим есть вот такое
..**...
..**...
.**....
.**....
........
он вот выводит вот такой результат
12**...
2.**...
.**....
........
а дальше( т е прямо вниз) он путь не видит почему то
Спасибо за внимание!
вот я ещё немного переисал функцию волновго алгоритма
C++
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
bool Wave(char *pMatrix, int * pMatrixRes, int border, int & res, int raft)
{
    for (int i = 0 ; i < border ; ++i)
    {
        for (int j = 0; j < border ; ++j)
        {
            pMatrixRes[i * border + j] = 0;
        }
    }
    
    pMatrixRes[0] = 1;
    int  n = 1;
    bool noSolution = true;
    while (noSolution) 
    {
        for (int i = 0; i < border ; ++i)
        {
            for (int j = 0; j < border ; ++j)
            {
                if (pMatrixRes[i * border + j] == n)
                {
                    /*for (int k = 0; k < 4 ; ++k)
                    {*/
                        if (CanGo(i, j, 1, 0, border,pMatrix) && 
                            (pMatrixRes[(i + 1) * border + (j + 0)] == 0))
                        {
                            PrintMatrix(pMatrixRes, border);
                            noSolution = false;
                            pMatrixRes[(i + 1) * border + (j + 0)] = n + 1;
                            if ((i + 1) == (border - 1) && ((j + 0) == (border - 1)))
                            {
                                res = n;
                                return true;
                            }
                        }
                        if (CanGo(i, j, -1, 0, border,pMatrix) && 
                            (pMatrixRes[(i - 1) * border + (j + 0)] == 0))
                        {
                            PrintMatrix(pMatrixRes, border);
                            noSolution = false;
                            pMatrixRes[(i - 1) * border + (j + 0)] = n + 1;
                            if ((i - 1) == (border - 1) && ((j + 0) == (border - 1)))
                            {
                                res = n;
                                return true;
                            }
                        }
                        if (CanGo(i, j, 0, -1, border,pMatrix) && 
                            (pMatrixRes[(i + 0) * border + (j - 1)] == 0))
                        {
                            PrintMatrix(pMatrixRes, border);
                            noSolution = false;
                            pMatrixRes[(i + 0) * border + (j - 1)] = n + 1;
                            if ((i + 0) == (border - 1) && ((j - 1) == (border - 1)))
                            {
                                res = n;
                                return true;
                            }
                        }
                        if (CanGo(i, j, 0, 1, border,pMatrix) && 
                            (pMatrixRes[(i + 0) * border + (j + 1)] == 0))
                        {
                            PrintMatrix(pMatrixRes, border);
                            noSolution = false;
                            pMatrixRes[(i + 0) * border + (j + 1)] = n + 1;
                            if ((i + 0) == (border - 1) && ((j + 1) == (border - 1)))
                            {
                                res = n;
                                return true;
                            }
                        }
                        //}
                //  }
                    n++;
                }
            }
        }
    }
    return false;
}
0
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
31.03.2014, 16:44  [ТС] 14
Всё !!! спасибо всем!!! получилось !!!!!
0
31.03.2014, 16:44
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2014, 16:44

Поиск кратчайшего пути
Задача о коммивояжере. Коммивояжер должен посетить клиентов, находящихся в разных городах....

Поиск кратчайшего пути
Саша и Маша путешествуют вдоль оси Ох на которой есть (неизвестное кол-во) достопримечательностей в...

Поиск кратчайшего пути
Как сделать что бы задача не считала стоимость проезда в обратную сторону ? #include &lt;cstdlib&gt; ...


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

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

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