結果

問題 No.1323 うしらずSwap
ユーザー 草苺奶昔草苺奶昔
提出日時 2024-09-09 02:21:35
言語 Go
(1.22.1)
結果
AC  
実行時間 374 ms / 3,000 ms
コード長 6,289 bytes
コンパイル時間 14,608 ms
コンパイル使用メモリ 237,600 KB
実行使用メモリ 43,656 KB
最終ジャッジ日時 2024-09-09 02:22:04
合計ジャッジ時間 28,008 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 226 ms
29,160 KB
testcase_17 AC 275 ms
29,240 KB
testcase_18 AC 215 ms
31,304 KB
testcase_19 AC 265 ms
29,244 KB
testcase_20 AC 229 ms
31,312 KB
testcase_21 AC 287 ms
39,644 KB
testcase_22 AC 374 ms
37,588 KB
testcase_23 AC 288 ms
37,564 KB
testcase_24 AC 367 ms
37,580 KB
testcase_25 AC 288 ms
35,464 KB
testcase_26 AC 254 ms
33,380 KB
testcase_27 AC 239 ms
31,276 KB
testcase_28 AC 191 ms
33,388 KB
testcase_29 AC 217 ms
35,316 KB
testcase_30 AC 274 ms
33,260 KB
testcase_31 AC 213 ms
33,252 KB
testcase_32 AC 275 ms
33,228 KB
testcase_33 AC 316 ms
37,600 KB
testcase_34 AC 322 ms
39,716 KB
testcase_35 AC 313 ms
41,752 KB
testcase_36 AC 324 ms
39,400 KB
testcase_37 AC 311 ms
43,560 KB
testcase_38 AC 327 ms
41,728 KB
testcase_39 AC 318 ms
43,552 KB
testcase_40 AC 330 ms
37,380 KB
testcase_41 AC 332 ms
43,656 KB
testcase_42 AC 319 ms
35,328 KB
testcase_43 AC 109 ms
27,036 KB
testcase_44 AC 141 ms
25,168 KB
testcase_45 AC 146 ms
31,324 KB
testcase_46 AC 136 ms
25,140 KB
testcase_47 AC 119 ms
27,352 KB
testcase_48 AC 139 ms
29,144 KB
testcase_49 AC 185 ms
37,612 KB
testcase_50 AC 126 ms
31,220 KB
testcase_51 AC 73 ms
29,012 KB
testcase_52 AC 100 ms
33,452 KB
testcase_53 AC 183 ms
35,588 KB
testcase_54 AC 100 ms
33,436 KB
testcase_55 AC 185 ms
37,580 KB
testcase_56 AC 85 ms
33,440 KB
testcase_57 AC 213 ms
37,580 KB
testcase_58 AC 2 ms
6,944 KB
testcase_59 AC 2 ms
6,940 KB
testcase_60 AC 2 ms
6,940 KB
testcase_61 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

const INF int = 1e18
const INF32 int32 = 1e9 + 10

func main() {
	yuki1323()
	// abc301_e()
}

// No.1323 うしらずSwap (交换位置，移形换位，分类讨论)
// https://yukicoder.me/problems/no/1323
// 给定一个带障碍的网格图和两个人的位置.
// 求两个人交换位置的最短路径总和.注意两个人不能同时移动到同一个位置.
// 如果不能交换位置，输出-1.
//
// 预处理出两个人到所有点的最短路.
// 1.最短路径不唯一 -> 2*D
// 2.最短路径唯一 -> 2*D+2
func yuki1323() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var H, W, sx, sy, gx, gy int32
	fmt.Fscan(in, &H, &W, &sx, &sy, &gx, &gy)
	sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
	G := make([]string, H)
	for i := int32(0); i < H; i++ {
		fmt.Fscan(in, &G[i])
	}

	dist1 := GridBfs(H, W, sx, sy, 4, func(x, y int32) bool { return G[x][y] == '#' })
	dist2 := GridBfs(H, W, gx, gy, 4, func(x, y int32) bool { return G[x][y] == '#' })
	D := dist1[gx][gy]
	if D == INF32 {
		fmt.Fprintln(out, -1)
		return
	}

	// 点是否在最短路径上.
	onPath := func(x, y int32) bool {
		d1, d2 := dist1[x][y], dist2[x][y]
		return d1 < INF32 && d2 < INF32 && d1+d2 == D
	}

	{
		// !最短路径不唯一 -> 2*D
		count := int32(0)
		for x := int32(0); x < H; x++ {
			for y := int32(0); y < W; y++ {
				if onPath(x, y) {
					count++
				}
			}
		}
		if count >= D+2 {
			fmt.Fprintln(out, 2*D)
			return
		}
	}

	res := INF32
	// 经过度数 >= 3 的点.
	{
		for x := int32(0); x < H; x++ {
			for y := int32(0); y < W; y++ {
				if G[x][y] == '#' {
					continue
				}
				deg := int32(0)
				for i := int32(0); i < 4; i++ {
					if G[x+dir8[i][0]][y+dir8[i][1]] != '#' {
						deg++
					}
				}
				if deg >= 3 {
					mid := onPath(x, y)
					if x == sx && y == sy {
						mid = false
					}
					if x == gx && y == gy {
						mid = false
					}
					if mid {
						fmt.Fprintln(out, 2*D+2)
						return
					} else if dist1[x][y] < INF32 {
						res = min32(res, 2*(dist1[x][y]+dist2[x][y])+4)
					}
				}
			}
		}
	}

	// 两条边不相交的路径.
	newG := make([][]byte, H)
	for i := range newG {
		newG[i] = []byte(G[i])
	}
	for x := int32(0); x < H; x++ {
		for y := int32(0); y < W; y++ {
			if onPath(x, y) {
				newG[x][y] = '#'
			}
		}
	}
	newG[sx][sy], newG[gx][gy] = '.', '.'
	dist := make([][]int32, H)
	for i := range dist {
		dist[i] = make([]int32, W)
		for j := range dist[i] {
			dist[i][j] = INF32
		}
	}
	dist[sx][sy] = 0
	queue := [][2]int32{{sx, sy}}
	for len(queue) > 0 {
		x, y := queue[0][0], queue[0][1]
		queue = queue[1:]
		for i := int32(0); i < 4; i++ {
			nx, ny := x+dir8[i][0], y+dir8[i][1]
			if newG[nx][ny] == '#' {
				continue
			}
			if x == sx && y == sy && nx == gx && ny == gy {
				continue
			}
			if dist[nx][ny] > dist[x][y]+1 {
				dist[nx][ny] = dist[x][y] + 1
				queue = append(queue, [2]int32{nx, ny})
			}
		}
	}
	res = min32(res, D+dist[gx][gy])

	if res == INF32 {
		fmt.Fprintln(out, -1)
		return
	}
	fmt.Fprintln(out, res)
}

// E - Pac-Takahashi
// https://atcoder.jp/contests/abc301/tasks/abc301_e
// 最短路+状压dp
//
// bfs 预处理出所有点之间(起点、关键点、终点)的最短路
// 状态压缩dp，dp[s][i] 表示经过 s 中的点，最后到达 i 的最短路
func abc301_e() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var H, W, T int32
	fmt.Fscan(in, &H, &W, &T)
	A := make([]string, H)
	for i := int32(0); i < H; i++ {
		fmt.Fscan(in, &A[i])
	}

	pos := [][2]int32{}
	for x := int32(0); x < H; x++ {
		for y := int32(0); y < W; y++ {
			if A[x][y] == 'S' {
				pos = append(pos, [2]int32{x, y})
			}
		}
	}
	for x := int32(0); x < H; x++ {
		for y := int32(0); y < W; y++ {
			if A[x][y] == 'o' {
				pos = append(pos, [2]int32{x, y})
			}
		}
	}
	for x := int32(0); x < H; x++ {
		for y := int32(0); y < W; y++ {
			if A[x][y] == 'G' {
				pos = append(pos, [2]int32{x, y})
			}
		}
	}

	N := int32(len(pos))
	dist := make([][]int32, N)
	for i := range dist {
		dist[i] = make([]int32, N)
	}
	for i := int32(0); i < N; i++ {
		sx, sy := pos[i][0], pos[i][1]
		mat := GridBfs(H, W, sx, sy, 4, func(x, y int32) bool {
			return A[x][y] == '#'
		})
		for j := int32(0); j < N; j++ {
			a, b := pos[j][0], pos[j][1]
			dist[i][j] = mat[a][b]
		}
	}

	dp := make([][]int, 1<<N)
	for i := range dp {
		dp[i] = make([]int, N)
		for j := range dp[i] {
			dp[i][j] = INF
		}
	}
	dp[1][0] = 0

	for s := int32(1); s < 1<<N; s++ {
		for a := int32(0); a < N; a++ {
			if dp[s][a] == INF {
				continue
			}
			for b := int32(0); b < N; b++ {
				t := s | 1<<b
				if s == t {
					continue
				}
				if tmp := dp[s][a] + int(dist[a][b]); tmp < dp[t][b] {
					dp[t][b] = tmp
				}
			}
		}
	}

	if dist[0][N-1] > T {
		fmt.Fprintln(out, -1)
		return
	}

	res := int32(0)
	for s := int32(1); s < 1<<N; s++ {
		if dp[s][N-1] > int(T) {
			continue
		}
		n := int32(bits.OnesCount32(uint32(s)) - 2)
		if n > res {
			res = n
		}
	}

	fmt.Fprintln(out, res)
}

var dir8 = [][]int32{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}

// 网格最短路.
func GridBfs(
	row, col int32, sx, sy int32, dmax int32,
	isWall func(int32, int32) bool,
) [][]int32 {
	isIn := func(x, y int32) bool {
		if x < 0 || row <= x {
			return false
		}
		if y < 0 || col <= y {
			return false
		}
		return !isWall(x, y)
	}

	dist := make([][]int32, row)
	for i := range dist {
		dist[i] = make([]int32, col)
		for j := range dist[i] {
			dist[i][j] = INF32
		}
	}
	queue := [][2]int32{{sx, sy}}
	add := func(x, y, d int32) {
		if !isIn(x, y) {
			return
		}
		if dist[x][y] > d {
			dist[x][y] = d
			queue = append(queue, [2]int32{x, y})
		}
	}
	add(sx, sy, 0)

	for len(queue) > 0 {
		x, y := queue[0][0], queue[0][1]
		queue = queue[1:]
		for i := int32(0); i < dmax; i++ {
			nx, ny := x+dir8[i][0], y+dir8[i][1]
			add(nx, ny, dist[x][y]+1)
		}
	}
	return dist
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}
0