题解 | #wyh的迷宫#

package main

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

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

type Pos struct {
	x, y int
}

func process(maze []string, vis []bool, sx, sy, ex, ey, n, m int) bool {
	q := make([]Pos, 0)
	q = append(q, Pos{sx, sy})
	vis[sx*m+sy] = true

	for len(q) > 0 {
		head := q[0]
		q = q[1:]
		if maze[head.x][head.y] == 't' {
			return true
		}
		pArr := make([]Pos, 0)
		for i := 0; i < 4; i++ {
			nx, ny := head.x+dx[i], head.y+dy[i]
			if nx >= 0 && ny >= 0 && nx < n && ny < m && maze[nx][ny] != 'x' && !vis[nx*m+ny] {
				pArr = append(pArr, Pos{nx, ny})
			}
		}
		sort.Slice(pArr, func(i, j int) bool {
			return math.Abs(float64(ex-pArr[i].x))+math.Abs(float64(ey-pArr[i].y)) < math.Abs(float64(ex-pArr[j].x))+math.Abs(float64(ey-pArr[j].y))
		})
		for i := 0; i < len(pArr); i++ {
			q = append(q, pArr[i])
			vis[pArr[i].x*m+pArr[i].y] = true
		}

	}
	return false
}

func NC15434(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var T int
	for Fscan(in, &T); T > 0; T-- {
		var n, m int
		Fscan(in, &n, &m)
		maze := make([]string, n)
		vis := make([]bool, n*m)
		sx, sy, ex, ey := -1, -1, -1, -1
		for i := 0; i < n; i++ {
			Fscan(in, &maze[i])
			if j := strings.IndexRune(maze[i], 't'); j != -1 {
				ex, ey = i, j
			}
			if k := strings.IndexRune(maze[i], 's'); k != -1 {
				sx, sy = i, k
			}
		}
		if process(maze, vis, sx, sy, ex, ey, n, m) {
			Fprintln(out, "YES")
		} else {
			Fprintln(out, "NO")
		}
	}
}
func main() {
	NC15434(os.Stdin, os.Stdout)
}