結果

問題 No.2855 Move on Grid
ユーザー ID 21712
提出日時 2025-04-06 04:02:35
言語 Go
(1.23.4)
結果
AC  
実行時間 1,410 ms / 3,000 ms
コード長 1,651 bytes
コンパイル時間 16,071 ms
コンパイル使用メモリ 244,152 KB
実行使用メモリ 8,176 KB
最終ジャッジ日時 2025-04-06 04:03:39
合計ジャッジ時間 58,064 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "sort"
import "container/heap"

func main() {
	var n,m,k int
	Scan(&n,&m,&k)
	a := make([][]int, n)
	for i := range a {
		a[i] = make([]int, m)
		for j := range a[i] {
			Scan(&a[i][j])
		}
	}
	ans := solve(n, m, k, a)
	Println(ans)
}

func solve(n, m, k int, a [][]int) int {
	vs := make([]int, 0, n*m+1)
	for _, aa := range a {
		vs = append(vs, aa...)
	}
	vs = append(vs, 1e9)
	Sort(Reverse(IntSlice(vs)))
	z := make([]int, n*m)
	h := make(IntHeap, n*m)
	dt := []int{-1, 0, 1, 0, -1}
	vj := Search(len(vs), func(vi int) bool {
		v := vs[vi]
		// Println("v=",v)
		for i := range z {
			z[i] = n*m+1
		}
		h = h[:0]
		if a[0][0] < v {
			heap.Push(&h, n*m)
		} else {
			heap.Push(&h, 0)
		}
		for h.Len() > 0 {
			p := heap.Pop(&h).(int)
			d, x, y := p/(n*m), p%(n*m)%m, p%(n*m)/m
			// Println(d,x,y)
			if d > k {
				return false
			}
			if x == m-1 && y == n-1 {
				return d <= k
			}
			for i, dx := range dt[1:] {
				dy := dt[i]
				xx, yy := x+dx, y+dy
				if xx<0||m<=xx||yy<0||n<=yy {
					continue
				}
				zi := yy*m+xx
				if a[yy][xx] < v {
					if d+1 < z[zi] {
						z[zi] = d+1
						heap.Push(&h, (d+1)*(n*m)+zi)
					}
				} else if d < z[zi] {
					z[zi] = d
					heap.Push(&h, d*(n*m)+zi)
				}
			}
		}
		return false
	})
	return vs[vj]
}

type IntHeap []int

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}
0