1. プログラミング
2. 2200 view

Contents

# 深さ優先探索で迷路を解く

## プログラム

### コード

Go言語での実装
```package main

import (
"bufio"
"fmt"
"os"
)

type Point struct {
X int
Y int
}

type Content struct {
Type string
IsChecked bool
}

type Node struct {
Parent *Node
Pos Point
}

type Stack struct {
Values []*Node
Size int
}
func (s *Stack) Length() int {
return s.Size
}
func (s *Stack) Push(n *Node) {
s.Values[s.Size] = n
s.Size += 1
}
func (s *Stack) Pop() *Node {
if s.Size &amp;gt; 0 {
s.Size -= 1
return s.Values[s.Size]
}
return nil
}

func IsWay(maze [][]Content, x int, y int) bool {
if x &amp;gt;= 0 &amp;amp;&amp;amp; x &amp;lt;= 11 &amp;amp;&amp;amp; y &amp;gt;= 0 &amp;amp;&amp;amp; y &amp;lt;= 11 &amp;amp;&amp;amp; maze[y][x].Type != "WALL" &amp;amp;&amp;amp; maze[y][x].IsChecked == false {
return true
} else {
return false
}
}

var endNode *Node
func SolveMaze(maze [][]Content, start Node) {
stack := Stack{make([]*Node, 1000), 0}
stack.Push(&amp;amp;start)

cur := &amp;amp;start
for ; maze[cur.Pos.Y][cur.Pos.X].Type != "END"; cur=stack.Pop() {
fmt.Printf("(%v,%v) Stack Size : %v\n", cur.Pos.X, cur.Pos.Y, stack.Length())
maze[cur.Pos.Y][cur.Pos.X].IsChecked = true
if IsWay(maze, cur.Pos.X, cur.Pos.Y-1) {
child := Node{cur, Point{cur.Pos.X, cur.Pos.Y-1}}
stack.Push(&amp;amp;child)
}
if IsWay(maze, cur.Pos.X, cur.Pos.Y+1) {
child := Node{cur, Point{cur.Pos.X, cur.Pos.Y+1}}
stack.Push(&amp;amp;child)
}
if IsWay(maze, cur.Pos.X-1, cur.Pos.Y) {
child := Node{cur, Point{cur.Pos.X-1, cur.Pos.Y}}
stack.Push(&amp;amp;child)
}
if IsWay(maze, cur.Pos.X+1, cur.Pos.Y) {
child := Node{cur, Point{cur.Pos.X+1, cur.Pos.Y}}
stack.Push(&amp;amp;child)
}
}

endNode = cur
}

func main() {
MAX_X := 11
MAX_Y := 11

// File open
var fp *os.File
fp, err := os.Open("maze.txt")
if err != nil {
panic(err)
}
defer fp.Close()

// Convert maze string to array of point
var startX, startY int
maze := make([][]Content, MAX_Y+1)
for y:= 0; y &amp;lt;= MAX_Y; y++ {
maze[y] = make([]Content, MAX_X+1)
}
counter := 0
y := -1
scanner := bufio.NewScanner(fp)
for scanner.Scan() {
y += 1
x := -1
for _, char := range scanner.Text() {
x += 1
switch char {
case 'S':
maze[y][x] = Content{"START", false}
startX = x
startY = y
case 'G':
maze[y][x] = Content{"END", false}
case '.':
maze[y][x] = Content{"WAY", false}
case '#':
maze[y][x] = Content{"WALL", false}
}
counter += 1
}
}
if err := scanner.Err(); err != nil {
panic(err)
}
fmt.Println(maze)

// Convert maze to binary tree
start := Node{nil, Point{startX, startY}}
SolveMaze(maze, start)
fmt.Println(endNode)

// Print Route
cur := endNode
for ; cur.Parent != nil; cur = cur.Parent {
fmt.Println(cur.Pos)
}
fmt.Println(cur.Pos)
}
```

### 実行結果

```{9 11}  # End
{9 10}
{8 10}
{7 10}
{6 10}
{6 9}
{6 8}
{7 8}
{8 8}
{9 8}
{9 7}
{9 6}
{8 6}
{7 6}
{6 6}
{6 5}
{6 4}
{6 3}
{6 2}
{5 2}
{4 2}
{3 2}
{2 2}
{2 1}
{2 0}  # Start
```