用GOLANG实现了一个走迷宫程序

GOALGN实现的一个走迷宫程序，用到广度优先和深度优先算法。

首先从filename指定的文件读取地图，文件中第一行的两个数表示地图的行数，列数；第二行前面两个坐标表示起点和终点，括号不要去改，改数字就行了。后边是地图。

比如有如下地图：

6 5
(0, 0) (5, 4)
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 0
0 1 0 0 0

运行程序后输出如下：

Got a map from file:maze_map.in
  0  1  0  0  0
  0  0  0  1  0
  0  1  0  1  0
  1  1  1  0  0
  0  1  0  0  0
  0  1  0  0  0
Find the end point:
  0  0  4  5  6
  1  2  3  0  7
  2  0  4  0  8
  0  0  0 10  9
  0  0 12 11 10
  0  0  0 12 11
The path is :
{0 0} {1 0} {1 1} {1 2} {0 2} {0 3} {0 4} {1 4} {2 4} {3 4} {4 4} {5 4} 
Picture:
  *  0  *  *  *
  *  *  *  0  *
  2  0  4  0  *
  0  0  0 10  *
  0  0 12 11  *
  0  0  0 12  *

Process finished with exit code 0

代码如下，因为只是练习，就先不考虑设计模式和分package了。代码和filename指定的地图在同一个目录下面。

package main

import (
	"os"
	"fmt"
	"errors"
	"log"
)

//struct of point
type Point struct {
	i, j int
}
//struct of maze
type Maze struct {
	root [][]int
	row, col int
}
//direction of a point
var dir = [...]Point{
	{-1,0},  //up
	{0, -1}, //left
	{1, 0},  //down
	{0, 1},  //right
}
var (
	startPoint Point = Point{i:0, j:0}
	endPoint Point = Point{i:0, j:0}
)
// map information read from filename
const filename = "maze_map.in"

func main() {
	// read maze map from filename
	maze := readMazeFromFile(filename)
	footPrint, err := walkMaze( maze, startPoint, endPoint )
	if err != nil {
		fmt.Println(err.Error())
		footPrint.Show()
		return
	}
	fmt.Println("Find the end point:")
	footPrint.Show()
	footPrint.printThePath(startPoint, endPoint)
}
/** method of Point *****/
func (p Point)add(point Point) Point  {
	return Point{p.i + point.i, p.j + point.j}
}
/***********************/

/** method of Maze *****/
func (maze * Maze)Visitable(tryPoint Point, targetValue int ) bool {
	if tryPoint.i < 0 || tryPoint.j < 0 || tryPoint.i >= maze.row || tryPoint.j >= maze.col {
		return false
	}
	if maze.root[tryPoint.i][tryPoint.j] == targetValue {
		return true
	} else {
		return false
	}
}

func (maze * Maze)Show()  {
	for i := range maze.root {
		for j := range maze.root[i] {
			fmt.Printf("%3d", maze.root[i][j])
		}
		fmt.Println()
	}
}

func (maze * Maze)printThePath(start, end Point)  {
	var steps []Point

	//find from end point
	steps = append(steps, end)
	//start point is the target point
	var ok bool
	if steps, ok = maze.dfsMaze(steps, start); !ok {
		fmt.Println("cannot found the path from the start point")
		return
	}
	fmt.Println("The path is :")
	sLen := len(steps)
	var cur Point
	for i := sLen - 1; i >= 0; i-- {
		cur = steps[i]
		fmt.Printf("%v ", cur)
		maze.root[cur.i][cur.j] = -1
	}
	fmt.Println("\nPicture:")
	for i := range maze.root {
		for j := range maze.root[i] {
			if maze.root[i][j] == -1 {
				fmt.Printf("  *", )
			} else {
				fmt.Printf("%3d", maze.root[i][j])
			}
		}
		fmt.Println()
	}
}

func (maze * Maze)dfsMaze(steps []Point, end Point) ([]Point, bool) {
	var tryPoint, cur Point
	stepsLen := len(steps)
	//peak last Point
	cur = steps[stepsLen-1]

	if cur == end {
		//the end point
		return steps, true
	}

	for _, tmpPoint := range dir {
		tryPoint = cur.add(tmpPoint)
		if maze.Visitable(tryPoint, maze.root[cur.i][cur.j] - 1) {
			steps = append(steps, tryPoint)
			var ok bool
			if steps ,ok = maze.dfsMaze(steps, end); ok {
				return steps, true
			} else {//pop this point
				steps = steps[0:len(steps)-1]
			}
		}
	}

	return steps, false
}

func (maze * Maze)setVisited(tryPoint Point )  {
	maze.root[tryPoint.i][tryPoint.j] = 2
}
func (maze * Maze)stepMark(cur, tryPoint Point) (int, error)  {
	curStep,err := maze.stepAt(cur)
	if err != nil {
		log.Printf("Got an bad point in maze.stepAt: %v, %s", cur, err.Error())
		return 0, err
	}
	maze.root[tryPoint.i][tryPoint.j] = curStep + 1

	return curStep + 1, nil
}
func (maze * Maze)stepAt(dstPoint Point ) (int, error) {
	if dstPoint.i < 0 || dstPoint.j < 0 || dstPoint.i >= maze.row || dstPoint.j >= maze.col {
		return 0, errors.New("point out of maze range")
	}
	return maze.root[dstPoint.i][dstPoint.j], nil
}

func walkMaze(maze * Maze, start, end Point ) (* Maze, error)  {
	var footPrint Maze
	footPrint.row = maze.row
	footPrint.col = maze.col
	footPrint.root = make([][]int, footPrint.row)
	for i := range footPrint.root {
		footPrint.root[i] = make([]int, footPrint.col)
	}

	step := make([]Point, 0)
	step = append(step, start)
	var tryPoint Point
	for len(step) != 0 {
		me := step[0]

		if me == end {
			//me is the end point
			return &footPrint, nil
		}
		//find and append the visitable point into Q
		for _, tmpPoint := range dir {
			tryPoint = me.add(tmpPoint)
			if maze.Visitable(tryPoint, 0) {
				// appen this tryPoint to Q
				step = append(step, tryPoint)
				//reject double add to Q
				maze.root[tryPoint.i][tryPoint.j] = 3
				// mark this point in footPrint base cur stepNum
				footPrint.stepMark(me, tryPoint)
			}
		}
		maze.setVisited(me)
		step = step[1:]
	}

	return &footPrint, errors.New("can not get to the target point")
}
/***********************/

func readMazeFromFile(filename string)  * Maze {
	var (
		err error
	    maze Maze
		file *os.File
	)
	file, err = os.Open(filename)
	if err != nil {
		fmt.Println("Open file failed:",filename )
		panic(err.Error())
	}
	defer file.Close()

	_, err = fmt.Fscanf(file, "%d %d\n", &maze.row, &maze.col)
	if err != nil {
		fmt.Printf("Read row and col form %s failed\n",filename )
		panic(err.Error())
	}
	//get start and end point
	_, err = fmt.Fscanf(file, "(%d, %d) (%d, %d)",
								&startPoint.i, &startPoint.j,
								&endPoint.i, &endPoint.j)
	if err != nil {
		fmt.Printf("Read start and end point from %s failed\n",filename )
		panic(err.Error())
	}
	fmt.Fscanln(file) //eat the '\n'

	maze.root = make([][]int, maze.row)
	for i :=  range maze.root {
		maze.root[i] = make([]int, maze.col)
		for j := range maze.root[i] {
			fmt.Fscanf(file, "%d", &maze.root[i][j] )
		}
		fmt.Fscanln(file) //eat the '\n'
	}
	fmt.Printf("Got a map from file:%s\n", filename)
	maze.Show()

	return &maze
}