аоооооооооооооооооооооооооооооооо""""""""""""""""""""""""""""""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄffffffffffffffffffffffffffffffff33333333333333333333333333333333 >А?оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™оооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™оооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™оооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™оооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™оооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™оооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™оооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄ™™™™™™™™™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™ооооооооЄЄЄЄЄЄЄЄооооЄЄЄЄЄЄЄЄЄЄЄЄооооооооооооооооЄЄЄЄооооЄЄЄЄ™™™™ооооЄЄЄЄоооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооо™™™™ооооЄЄЄЄ™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄЄЄЄЄ™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™™™™™™™™™оооо™™™™оооооооооооооооооооооооооооо™™™™ЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооо™™™™™™™™™™™™™™™™ооооооооЄЄЄЄ™™™™™™™™ЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™ооооЄЄЄЄЄЄЄЄ™™™™™™™™ооооооооЄЄЄЄЄЄЄЄоооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™ооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооffffооооооооооооооооffffооооооооооооооооffffооооооооооооооооffffооооооооооооооооffffооооооооооооооооffffооооооооооооооооffffооооооооооооооооffffооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооу -- title: Depth-First Search -- author: Jeremy Miller -- desc: Depth-first search visualized -- script: lua -- sprites FLOOR=0 WALL=1 START=2 VISITED=3 STACKED=4 GOAL=5 PATH=6 -- buttons A=4 MAP_WIDTH=30 MAP_HEIGHT=17 function init() stack={} visited={} start={ x=1, y=1, visited=false, parent=nil, } table.insert(stack,start) goal={ x=28, y=15, } current=nil done=false end function input() if btnp(A) then -- restart resetMap() init() end end -- Clear map of any existing sprites function resetMap() for y=1,MAP_HEIGHT-2 do for x=1,MAP_WIDTH-2 do if mget(x,y)~=WALL then mset(x,y,FLOOR) end end end end function update() if not done then if #stack>0 then -- TODO current=pop() if current.x==goal.x and current.y==goal.y then -- found goal done=true else -- no goal yet, keep looking addAdjacentCells(current) end else -- no more edges, didn't find goal end end end -- Remove last cell from stack and -- return it function pop() local cell=stack[#stack] table.remove(stack,#stack) cell.visited=true table.insert(visited,cell) return cell end -- Add adjacent cells of given cell -- to stack if they aren't already in -- stack, haven't been visited, and -- are not walls function addAdjacentCells(cell) local adjacents={ {x=cell.x,y=cell.y-1}, {x=cell.x,y=cell.y+1}, {x=cell.x-1,y=cell.y}, {x=cell.x+1,y=cell.y}, } for _,c in ipairs(adjacents) do if not contains(stack,c.x,c.y) and not contains(visited,c.x,c.y) and mget(c.x,c.y)~=WALL then local adjacentCell={ x=c.x, y=c.y, visited=false, parent=cell, } table.insert(stack,adjacentCell) end end end -- Check if a cell with given X/Y is -- in given table "t" function contains(t,x,y) for _,item in ipairs(t) do if item.x==x and item.y==y then return true end end return false end function draw() drawMap() drawVisited() drawStack() drawPath() drawStartEnd() end function drawMap() map(0,0,30,17) end function drawVisited() for _,cell in ipairs(visited) do mset(cell.x,cell.y,VISITED) end end function drawStack() for _,cell in ipairs(stack) do mset(cell.x,cell.y,STACKED) end end function drawPath() if done then drawPathCell(current) end end function drawPathCell(cell) mset(cell.x,cell.y,PATH) if cell.parent then drawPathCell(cell.parent) end end function drawStartEnd() mset(start.x,start.y,START) mset(goal.x,goal.y,GOAL) end init() function TIC() cls() input() update() draw() end