迷路: http://okajima.air-nifty.com/b/2010/01/post-abc6.html

.gitignore

*~
*.6
*.8
gomaze

gomaze.go

/*
 * http://okajima.air-nifty.com/b/2010/01/post-abc6.html
 */

package main

import (
	"container/vector";
	"fmt";
	"math";
	"strings";
)

type Point struct {
	x, y int;
}

func (p *Point) IsIn(x, y, width, height int) bool {
	return 0 <= p.x && p.x < x + width &&
		0 <= p.y && p.y < y + height;
}

func (p *Point) Equals(other *Point) bool {
	return p.x == other.x && p.y == other.y;
}

type IntTable2D struct {
	width, height int;
	values []int;
}

func NewIntTable2D(width, height int) *IntTable2D {
	return &IntTable2D{width, height, make([]int, width * height)};
}

func (v *IntTable2D) At(x, y int) int {
	return v.values[x + y * v.width];
}

func (v *IntTable2D) Set(x, y, value int) {
	v.values[x + y * v.width] = value;
}

func main() {
	inputStr := `**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************`;
	var startPoint, goalPoint Point;
	lines := strings.Split(inputStr, "\n", 0);
	mazeWidth := len(lines[0]);
	mazeHeight := len(lines);
	maze := NewIntTable2D(mazeWidth, mazeHeight);
	distances := NewIntTable2D(mazeWidth, mazeHeight);
	for j, line :=  range lines {
		fmt.Print(line + "\n");
		for i, c := range strings.Bytes(line) {
			maze.Set(i, j, int(c));
			switch c {
			case 'S':
				startPoint.x, startPoint.y = i, j;
			case 'G':
				goalPoint.x, goalPoint.y = i, j;
			}
			if c == 'S' {
				distances.Set(i, j, 0);
			} else {
				distances.Set(i, j, math.MaxInt32);
			}
		}
	}

	currentPoints := new(vector.Vector);
	currentPoints.Push(startPoint);
	currentDistance := 0;
	for {
		nextPoints := new(vector.Vector);
		currentPoints.Do(func (e interface{}) {
			p := e.(Point);
			if maze.At(p.x, p.y) == '*' {
				return;
			}
			if currentDistance < distances.At(p.x, p.y) {
				distances.Set(p.x, p.y, currentDistance);
			}
			for _, p2 := range []Point{
				Point{p.x-1, p.y},
				Point{p.x+1, p.y},
				Point{p.x, p.y-1},
				Point{p.x, p.y+1},
			} {
				if p2.IsIn(0, 0, mazeWidth, mazeHeight) &&
					distances.At(p2.x, p2.y) == math.MaxInt32 {
					nextPoints.Push(p2);
				}
			}
		});
		if distances.At(goalPoint.x, goalPoint.y) < math.MaxInt32 {
			break;
		}
		if nextPoints.Len() == 0 {
			panic("Can't goal!");
		}
		currentPoints = nextPoints;
		currentDistance++;
	}
	p := goalPoint;
	for {
		for _, np := range []Point{
			Point{p.x-1, p.y},
			Point{p.x+1, p.y},
			Point{p.x, p.y-1},
			Point{p.x, p.y+1},
		} {
			if np.IsIn(0, 0, mazeWidth, mazeHeight) &&
				distances.At(np.x, np.y) == currentDistance {
				if np.Equals(&startPoint) {
					goto EndRouting;
				} else {
					maze.Set(np.x, np.y, '$');
					p = np;
					break;
				}
			}
		}
		currentDistance--;
	}
EndRouting:

	fmt.Print("Result:\n");
	for j := 0; j < mazeHeight; j++ {
		for i := 0; i < mazeWidth; i++ {
			fmt.Printf("%c", maze.At(i, j));
		}
		fmt.Print("\n");
	}
	
	fmt.Print("Done\n");
}

Makefile

include $(GOROOT)/src/Make.$(GOARCH)

TARG = gomaze
GOFILES = gomaze.go

include $(GOROOT)/src/Make.cmd