题解 | #迷宫#

迷宫

https://ac.nowcoder.com/acm/problem/15136

技巧

bfs

思路

这里需要分类讨论

1 不需要KEY也能到达终点

2 需要KEY时候先算出 D - K 的距离

2.1 拿到K然后顺路去D

2.2 拿到K然后返回起点再去D

3 如果需不需要KEY都能到达时候取最小值

实现

package main

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

type Pos struct {
	x, y, step int
}

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

// 不拿Key
func case1(sx, sy int, maze []string) int {
	vis := [510][510]bool{}
	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
		}
		for i := 0; i < 4; i++ {
			nx, ny := top.x+dx[i], top.y+dy[i]
			if nx >= 0 && ny >= 0 && nx < len(vis) && ny < len(vis[0]) && !vis[nx][ny] && maze[nx][ny] != 'W' && maze[nx][ny] != 'D' {
				q = append(q, Pos{nx, ny, top.step + 1})
			}
		}
	}
	return ans
}

// 拿Key
func case2(sx, sy int, maze []string) int {
	vis := [510][510]bool{}
	ans := -1
	hasKey := false
	var key Pos
	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] == 'D' {
			if !hasKey {
				if len(q) == 0 {
					break
				}
				q = append(q, top)
				continue
			} else {
				kdPathQ := make([]Pos, 0)
				kdPathQ = append(kdPathQ, Pos{key.x, key.y, 0})
				visTmp := [510][510]bool{}
				distance := 999999999
				for len(kdPathQ) > 0 {
					tmp := kdPathQ[0]
					kdPathQ = kdPathQ[1:]
					visTmp[tmp.x][tmp.y] = true
					if maze[tmp.x][tmp.y] == 'D' {
						distance = tmp.step
						break
					}
					for i := 0; i < 4; i++ {
						nx, ny := tmp.x+dx[i], tmp.y+dy[i]
						if nx >= 0 && ny >= 0 && nx < len(vis) && ny < len(vis[0]) && maze[nx][ny] != 'W' && !visTmp[nx][ny] {
							kdPathQ = append(kdPathQ, Pos{nx, ny, tmp.step + 1})
						}
					}
				}
				//						先拿到K顺路到D						拿到K返回后再去D
				top.step = int(math.Min(float64(distance+key.step), float64(top.step+2*key.step)))
			}
		} else if maze[top.x][top.y] == 'K' {
			hasKey = true
			key = Pos{top.x, top.y, top.step}
		} else if maze[top.x][top.y] == 'E' {
			ans = top.step
			break
		}

		for i := 0; i < 4; i++ {
			nx, ny := top.x+dx[i], top.y+dy[i]
			if nx >= 0 && ny >= 0 && nx < len(vis) && ny < len(vis[0]) && !vis[nx][ny] && maze[nx][ny] != 'W' {
				q = append(q, Pos{nx, ny, top.step + 1})
			}
		}

	}
	return ans
}

func NC15136(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var n, m int
	Fscan(in, &n, &m)
	maze := make([]string, n)
	sx, sy := -1, -1
	for i := 0; i < n; i++ {
		Fscan(in, &maze[i])
		if j := strings.IndexRune(maze[i], 'S'); j != -1 {
			sx, sy = i, j
		}
	}
	if ans := case1(sx, sy, maze); ans != -1 {
		if p := case2(sx, sy, maze); p < ans {
			ans = p
		}
		Fprintln(out, ans)
	} else {
		Fprintln(out, case2(sx, sy, maze))
	}
}
func main() {
	NC15136(os.Stdin, os.Stdout)
}