题解 | #走出迷宫#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"math"
	"os"
	"sort"
	"strings"
)

type Pos struct {
	x, y, step int
}

var (
	dx = []int{0, 1, -1, 0}
	dy = []int{1, 0, 0, -1}
)

func NC14572(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	for {
		var n, m int
		Fscan(in, &n, &m)
		if n == 0 && m == 0 {
			break
		}
		vis := [510][510]bool{}
		maze := make([]string, n)

		var sx, sy, ex, ey int
		for i := 0; i < n; i++ {
			Fscan(in, &maze[i])
			if j := strings.IndexRune(maze[i], 'S'); j != -1 {
				sx, sy = i, j
				vis[sx][sy] = true
			}
			if j := strings.IndexRune(maze[i], 'E'); j != -1 {
				ex, ey = i, j
			}
		}

		ans := -1
		q := make([]Pos, 0)
		q = append(q, Pos{sx, sy, 0})
		for len(q) > 0 {
			top := q[0]
			q = q[1:]
			vis[top.x][top.y] = true
			if maze[top.x][top.y] == 'E' {
				ans = top.step
				break
			}
			pa := make([]Pos, 0)
			for i := 0; i < 4; i++ {
				nx, ny := top.x+dx[i], top.y+dy[i]
				if nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] && maze[nx][ny] != '#' {
					pa = append(pa, Pos{nx, ny, 1 + top.step})
				}
			}
			sort.Slice(pa, func(i, j int) bool {
				return math.Abs(float64(ex-pa[i].x))+math.Abs(float64(ey-pa[i].y)) < math.Abs(float64(ex-pa[j].x))+math.Abs(float64(ey-pa[j].y))
			})
			for i := 0; i < len(pa); i++ {
				q = append(q, pa[i])
			}
		}
		if ans == -1 {
			Fprintln(out, "No")
		} else {
			Fprintln(out, "Yes")
		}

	}

}

func main() {
	NC14572(os.Stdin, os.Stdout)
}