こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

幅のある移動 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

ちょっと悩んでAIとも壁打ちした結果、queueという仕組みを使うのが一番効率的なんだと分かりました。

package main
import (
    "fmt"
    "strconv"
)
func main(){
    var h, w int
    fmt.Scan(&h, &w)
    
    s := make([]string, h)
    replace := func(sy, sx, r int) {
        runes := []rune(s[sy])
        runes[sx] = rune(48 + r)
        s[sy] = string(runes)
    }
    var queueY, queueX []int
    for i := 0; i < h; i++ {
        fmt.Scan(&s[i])
        for j, v := range s[i] {
            if v == '*' {
                replace(i, j, 0)
                queueY = append(queueY, i)
                queueX = append(queueX, j)
            }
        }
    }
    
	// 移動方向（上下左右）
	dy := []int{1, -1, 0, 0}
	dx := []int{0, 0, 1, -1}
    for len(queueY) > 0 {
        sy, sx := queueY[0], queueX[0]
        queueY, queueX = queueY[1:], queueX[1:]
        r, _ := strconv.Atoi(string(s[sy][sx]))
        var ly, lx int
        for i := 0; i < 4; i++ {
            ly, lx = sy + dy[i], sx + dx[i]
            if ly >= 0 && lx >= 0 && ly < h && lx < w && s[ly][lx] == '.' {
                replace(ly, lx, r + 1)
                queueY = append(queueY, ly)
                queueX = append(queueX, lx)
            }
        }
    }
    
    for i := 0; i < h; i++ {
        fmt.Println(s[i])
    }
}

queue周りの実装はもう少しいい感じにできた気がしなくもないですが、とりあえずまぁこれで…