题解 | 双人成行 ACM中的AC题

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const INF = 1e9

type Node struct {
	r, c int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	parts := strings.Fields(scanner.Text())
	n, _ := strconv.Atoi(parts[0])
	m, _ := strconv.Atoi(parts[1])
	r_start, _ := strconv.Atoi(parts[2])
	c_start, _ := strconv.Atoi(parts[3])
	r_start--
	c_start-- // 0-indexed

	grid := make([]string, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		grid[i] = scanner.Text()
	}

	// Step 1: Multi-source BFS for solo phase
	dist_solo := make([][]int, n)
	for i := range dist_solo {
		dist_solo[i] = make([]int, m)
		for j := range dist_solo[i] {
			dist_solo[i][j] = -1
		}
	}

	q_solo := make([]Node, 0)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '@' {
				dist_solo[i][j] = 0
				q_solo = append(q_solo, Node{i, j})
			}
		}
	}

	dr := []int{-1, 1, 0, 0}
	dc := []int{0, 0, -1, 1}

	for len(q_solo) > 0 {
		current := q_solo[0]
		q_solo = q_solo[1:]
		r, c := current.r, current.c

		for i := 0; i < 4; i++ {
			nr := r + dr[i]
			nc := c + dc[i]
			if nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#' && dist_solo[nr][nc] == -1 {
				dist_solo[nr][nc] = dist_solo[r][c] + 1
				q_solo = append(q_solo, Node{nr, nc})
			}
		}
	}

	// Step 2: BFS for paired phase
	dist_pair := make([][]int, n)
	for i := range dist_pair {
		dist_pair[i] = make([]int, m)
		for j := range dist_pair[i] {
			dist_pair[i][j] = -1
		}
	}

	q_pair := make([]Node, 0)
	dist_pair[r_start][c_start] = 0
	q_pair = append(q_pair, Node{r_start, c_start})

	for len(q_pair) > 0 {
		current := q_pair[0]
		q_pair = q_pair[1:]
		r1, c1 := current.r, current.c

		r2 := 2*r_start - r1
		c2 := 2*c_start - c1

		for i := 0; i < 4; i++ {
			nr1 := r1 + dr[i]
			nc1 := c1 + dc[i]
			nr2 := r2 - dr[i]
			nc2 := c2 - dc[i]

			if nr1 >= 0 && nr1 < n && nc1 >= 0 && nc1 < m && grid[nr1][nc1] != '#' &&
				nr2 >= 0 && nr2 < n && nc2 >= 0 && nc2 < m && grid[nr2][nc2] != '#' &&
				dist_pair[nr1][nc1] == -1 {
				dist_pair[nr1][nc1] = dist_pair[r1][c1] + 1
				q_pair = append(q_pair, Node{nr1, nc1})
			}
		}
	}

	// Step 3: Combine results
	min_total_time := int64(-1)

	for r1 := 0; r1 < n; r1++ {
		for c1 := 0; c1 < m; c1++ {
			if dist_pair[r1][c1] != -1 {
				t_pair := int64(dist_pair[r1][c1])
				r2 := 2*r_start - r1
				c2 := 2*c_start - c1

				if r2 >= 0 && r2 < n && c2 >= 0 && c2 < m {
					if grid[r1][c1] == '@' && dist_solo[r2][c2] != -1 {
						current_time := t_pair + int64(dist_solo[r2][c2])
						if min_total_time == -1 || current_time < min_total_time {
							min_total_time = current_time
						}
					}
					if grid[r2][c2] == '@' && dist_solo[r1][c1] != -1 {
						current_time := t_pair + int64(dist_solo[r1][c1])
						if min_total_time == -1 || current_time < min_total_time {
							min_total_time = current_time
						}
					}
				}
			}
		}
	}

	fmt.Println(min_total_time)
}