题解 | 迷宫

package main

/*
   BFS
   分别从S、E出发，把可达位置分别标记为S、E
   遍历过程中判断是否有同一行/列或相邻行/列内既含有S，也含有E
*/

import (
	"fmt"
)

type Node struct {
	i, j int
}

var nS, nE, nH byte = byte('S'), byte('E'), byte('#')

func isAdjoin(a, b int) bool { // 是否相邻
    if a > b{
        return a - b <= 1
    }
    return b - a <= 1
}

func main() {
	var n, m int
	fmt.Scanf("%d %d", &n, &m)
	var k = make([][]byte, n)
	var s string
	var S_i, S_j, E_i, E_j int
	for i := 0; i < n; i++ {
		fmt.Scanf("%s", &s)
		k[i] = make([]byte, m)
		k[i] = []byte(s)
		for j := 0; j < m; j++ {
			if k[i][j] == nS {
				S_i = i
				S_j = j
			}
			if k[i][j] == nE {
				E_i = i
				E_j = j
			}
		}
	}
	if isAdjoin(S_i, E_i) || isAdjoin(S_j, E_j) { // 相邻或同行或同列
		fmt.Println("YES")
		return
	}

    var si, sj = make([]bool, n),make([]bool, m) // 记录某行某列是否S可达 
    si[S_i] = true
    sj[S_j] = true

	dist := [][]int{{1, 0}, {-1, 0}, {0, -1}, {0, 1}} // 四个方向操作
	var cur Node
	var ni, nj int
	// 先从S开始遍历
	queue := []Node{{S_i, S_j}}
	for len(queue) > 0 {
		cur = queue[0]
		queue = queue[1:]

		for _, d := range dist {
			ni = cur.i + d[0]
			nj = cur.j + d[1]
			if ni < 0 || ni >= n || nj < 0 || nj >= m || k[ni][nj] == nS || k[ni][nj] == nH {
				continue
			}
			if k[ni][nj] == nE || isAdjoin(ni, E_i) || isAdjoin(nj, E_j) { // 与E相邻或同行或同列
				fmt.Println("YES")
				return
			}
			k[ni][nj] = nS
            si[ni],sj[nj] = true, true
			queue = append(queue, Node{ni, nj})
		}
	}

	// 再从E开始遍历
	queue = []Node{{E_i, E_j}}
	for len(queue) > 0 {
		cur = queue[0]
		queue = queue[1:]

		for _, d := range dist {
			ni = cur.i + d[0]
			nj = cur.j + d[1]
			if ni < 0 || ni >= n || nj < 0 || nj >= m || k[ni][nj] == nE || k[ni][nj] == nH {
				continue
			}
			if k[ni][nj] == nS || 
                si[ni] || (ni-1>=0&&si[ni-1]) || (ni+1<n&&si[ni+1]) || 
                sj[nj] || (nj-1>=0&&sj[nj-1]) || (nj+1<m&&sj[nj+1]) { // 与S可达的位置相邻或同行或同列
				fmt.Println("YES")
				return
			}
			k[ni][nj] = nE
			queue = append(queue, Node{ni, nj})
		}
	}

    // 都没法满足，无法可达
	fmt.Print("NO")
}