Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Задача / 20 сообщений из 20, страница 1 из 1
04.05.2005, 14:34
    #33048204
Andrey13
Andrey13
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Сразу оговорюсь, если отвлекаю от важных дел не отвечайте.
Позвонил племянник, помогает подруге решать задачу.

Есть массив(лабиринт) скажем 15х15. Заполнен 0 и 1. Надо пройти сверху вниз
по нолям к выходу. Все сделал, нарисовал лабиринт, заполнил 0 и 1, но вот пройти не получается. Пробуем все время идти если 0 то вперед, если 1 то вправо по идее должен пройти, но не тут то было.

Если есть алгоритм прохода сбросте пожалуйста, может решал кто уже?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 16:44
    #33048633
Antonariy
Antonariy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Не уверен, что правильно понял, лабиринт выглядит так?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 16:45
    #33048637
Antonariy
Antonariy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
[Картинка по пути потерялась]
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 17:43
    #33048817
Andrey13
Andrey13
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Да может именно так (формируется случайно), но как решить?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 20:01
    #33049081
Guest123
Guest123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
I tak ponyla,chto idti nado sverhy vniz i ne obyzatelno esli 0 to vpered,esli 1 to vpravo(eto vi vibrali takoy algoritm)poprobyute tak:
Pole(15,15) array
y, x

EndGame Boolean peremennaya
ishy tochky vhoda sverhy v labirint
y=1
for x=1 to 15
if Pole(y,x)=0 then
Pole(y,x) = 1
EndGame = False

While EndGame = False
--pervim proveryu dorogy vniz(potomy chto zel douti do nizy,chem bistree)
if Pole(y+1,x) = 0 Then
Pole(y+1,x) = 1
y = y+1
goto NextCheck
End if
--proveryau pravo
if Pole(y,x+1) = 0 Then
Pole(y,x+1) = 1
x = x+1
goto NextCheck
End if

--proveryau Levee
if Pole(y,x-1) = 0 Then
Pole(y,x-1) = 1
x = x-1
goto NextCheck
End if

--proveryu vverh
if Pole(y-1,x) = 0 Then
Pole(y-1,x) = 1
y = y-1
goto NextCheck
End if

NextCheck:
--proveryu mojet bit yje konez labirinta
if Pole(y+1,x) = 1 and Pole(y,x-1) = 1 and Pole(y,x+1) = 1 and Pole(y-1,x) = 1 then
EndGame = true
Exit sub
end if

Wend
end if

next x
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 22:28
    #33049245
Andrey13
Andrey13
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
спасибо попробуем, но почему

EndGame Boolean peremennaya
ishy tochky vhoda sverhy v labirint
y=1
for x=1 to 15
if Pole(y,x)=0 then
Pole(y,x) = 1 ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 22:50
    #33049253
Guest123
Guest123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Potomy-chto vezde gde mi nashli 0 zamenyem na 1,chto- bi ne popast v beskonechniy zikl,mojno i bez etogo na pervom shage(vsegda perestrahovivaus)
dlya privedennogo primera na kartinke etot algoritm rabotaet,kak mne kajetsya dlya ostalnix variantov toje
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 23:01
    #33049258
Andrey13
Andrey13
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
А если назад возвращаться прийдется?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 23:18
    #33049271
Guest123
Guest123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Andrey13: poprobyute prouyi po-etomy labirinty s pomoshu eto-algoritma i posmotrite kogda vam pridetsya vozvrashatsya nazad?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.05.2005, 23:43
    #33049280
Guest123
Guest123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Andrey13:Vi pravi mojet ponadobitsya idti nazad,k sojaleniu I yje ybegau domoy,esli vam tak srochno,to v etot algoritm mojno dobavit promejytochniy massiv tipa PreviousStep(x,y) gde sohranyt odin shag nazad ili poly kotorie proshli stavit 2 vmesto 1
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.05.2005, 07:59
    #33049461
Andrey13
Andrey13
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
guest123 большое спасибо за поддержку, я вообще думал что кто то уже решал такую задачу, и есть готовое решение. Мой племянник уже вышел из порложения, на сколько я понял по телефону, он создал несколько подпрограмм Vpered, Nazad, Vpravo, Vlevo, и пользовался этими подпрограммами в момент прохождения лабиринта. Для того и задачи что бы молодеж училась. Хотя любой голову бы поломал над этим.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.05.2005, 10:14
    #33049674
Antonariy
Antonariy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Решал давно на паскале похожий алгоритм, исходников ессно не сохранилось, но идею помню.

В основе всего лежит рекурсия. Не самый быстрый способ, но для поля 15х15 пойдет. Процедура будет выглядеть так:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
Sub FindPath(x, y, FromWhere)
End Sub

Enum Direction
    West =  0 
    North =  1 
    East =  2 
    South =  3 
End Enum
Допустим вход в лабиринт находится в позиции с10 и мы дошли до позиции с9. Из текущей позиции есть три направления - запад, север, восток. Далее перебираем
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
If FromWhere<>South then
    FindPath x- 1 , y, East
    FindPath x, y- 1 , South
    FindPath x+ 1 , y, West
End If
If FromWhere<>East then
    FindPath x- 1 , y, East
    FindPath x, y+ 1 , North
    FindPath x, y- 1 , South
End If
... и т.д. То есть проверяем все направления, кроме того, откуда пришли. Если на текушей позиции единица, то выходим из процедуры. Если координаты совпадают с координатами выхода - End.
Код: plaintext
1.
2.
3.
4.
5.
6.
Sub FindPath(x, y, FromWhere)
    If MazeMatrix(x, y)= 1  Then Exit Sub
    If x= 8  and y= 1  Then 
        MsgBox "Дошли!"
        End
    End If

А насчет того, чтобы "пройти назад"... хоть вперед, хоть назад, хоть вбок. Конечный результат задается координатами, а этот алгоритм блуждает по лабиринту вслепую, ему пох, куда идти.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.05.2005, 10:20
    #33049698
Antonariy
Antonariy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Вот весь листинг:
Код: plaintext
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.
Enum Direction
    West =  0 
    North =  1 
    East =  2 
    South =  3 
End Enum

Dim MazeMatrix( 1  To  15 ,  1  To  15 )

Sub FindPath(x, y, FromWhere As Direction)
    If MazeMatrix(x, y) =  1  Then Exit Sub
    If x =  8  And y =  1  Then
        MsgBox "Дошли!"
        End
    End If
    If FromWhere <> South Then
        FindPath x -  1 , y, East
        FindPath x, y -  1 , South
        FindPath x +  1 , y, West
    End If
    If FromWhere <> East Then
        FindPath x -  1 , y, East
        FindPath x, y +  1 , North
        FindPath x, y -  1 , South
    End If
    If FromWhere <> North Then
        FindPath x -  1 , y, East
        FindPath x, y +  1 , North
        FindPath x +  1 , y, West
    End If
    If FromWhere <> West Then
        FindPath x +  1 , y, West
        FindPath x, y +  1 , North
        FindPath x, y -  1 , South
    End If
End Sub
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.05.2005, 10:23
    #33049716
Antonariy
Antonariy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Слегка затупил:
Код: plaintext
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.
Enum Direction
    West =  0 
    North =  1 
    East =  2 
    South =  3 
End Enum

Dim MazeMatrix( 1  To  15 ,  1  To  15 )

Sub FindPath(x, y, FromWhere As Direction)
    If MazeMatrix(x, y) =  1  Then Exit Sub
    If x =  8  And y =  1  Then
        MsgBox "Äîøëè!"
        End
    End If
    If FromWhere <> South Then
        FindPath x -  1 , y, East
        FindPath x, y -  1 , South
        FindPath x +  1 , y, West
    ElseIf FromWhere <> East Then
        FindPath x -  1 , y, East
        FindPath x, y +  1 , North
        FindPath x, y -  1 , South
    ElseIf FromWhere <> North Then
        FindPath x -  1 , y, East
        FindPath x, y +  1 , North
        FindPath x +  1 , y, West
    ElseIf FromWhere <> West Then
        FindPath x +  1 , y, West
        FindPath x, y +  1 , North
        FindPath x, y -  1 , South
    End If
End Sub
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.05.2005, 18:53
    #33051450
Andrey13
Andrey13
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Спасибо большое. Отошлю пускай посмотрит. Но у него тоже работает, только что вечером заходил смотрел. Правда код длинный. Только я не понял, у тебя будет бродить пока до конца не дойдет В СЛЕПУЮ, или я ошибаюсь?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.05.2005, 11:16
    #33052209
Antonariy
Antonariy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Именно. Преставь себе слепого в коридоре. Он сделал шаг, повел палкой налево - стена, вперед - стена, направо - проход есть. Сзади елозить не нужно, потому что оттуда пришел. Делает шаг направо. Опять елозит палкой. Однако, если зашел в тупик, ему не надо точно так же вслепую брести в обратную сторону. Благодаря рекурсии все повороты уже в памяти.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.05.2005, 11:22
    #33052230
Antonariy
Antonariy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Еще один момент. Лучше заменить условия
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
Celect Case FromWhere
    Case North
        FindPath x -  1 , y, East
        FindPath x, y -  1 , South
        FindPath x +  1 , y, West
    Case West
        FindPath x -  1 , y, East
        FindPath x, y +  1 , North
        FindPath x, y -  1 , South
    Case East
        FindPath x +  1 , y, West
        FindPath x, y +  1 , North
        FindPath x, y -  1 , South
    Case South
        FindPath x -  1 , y, East
        FindPath x, y +  1 , North
        FindPath x +  1 , y, West
End Select
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.05.2005, 18:17
    #33053518
Andrey13
Andrey13
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Тогда все правильно получается что и не слепой.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
15.05.2011, 14:47
    #37261269
General1992
General1992
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
Andrey13, а это решение ратоает черз Excel? мне надо 0 и 1 самому вводить на странице эксель а потом проверять, можно ли пройти от ячейки А1 до противоположного конца...размер вводимой матрицы произвольный...не поможете?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.05.2011, 18:11
    #37261459
Shocker.Pro
Shocker.Pro
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача
General1992Andrey13, а это решение ратоает черз Excel?
грубо говоря, заменить обращение к массиву
Код: plaintext
MazeMatrix(x, y)
на обращение к ячейке
Код: plaintext
Cells(x, y)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Задача / 20 сообщений из 20, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 137ms
Закрыть
start [/forum/topic.php?fid=60&mobile=1&tid=2158717]:
 0ms
get settings:
 9ms
get forum list:
 12ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 31ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 53ms
get tp. blocked users:
 2ms
others: 11ms
total:  137ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]