Submission #71698377

---

Source Code Expand

fun main() {
    val cin = System.`in`.bufferedReader()
    val cout = System.out.bufferedWriter()

    val (h, w) = cin.readLine().split(" ").map { it.toInt() }
    val g = Array(h) { cin.readLine().toCharArray() }
    val p = Array(26) { mutableListOf<Pair<Int, Int>>() }
    for (r in 0 until h) for (c in 0 until w) {
        val ch = g[r][c] - 'a'
        if (ch in 0..<26) p[ch].add(r to c)
    }
//    cout.write("p:${p.joinToString(" ")}\n")
    val added = Array(h) { BooleanArray(w) }
    added[0][0] = true
    var ans = 0
    val q = ArrayDeque<Pair<Int, Int>>()
    q.add(0 to 0)
    var found = false
    val d = intArrayOf(-1, 0, 1, 0, -1)
    while (!q.isEmpty()) {
        var k = q.size
        while (k-- > 0) {
            val (r, c) = q.removeFirst()
//            cout.write("visiting $r $c ${g[r][c]}\n")
            if (r == h-1 && c == w-1) {
                found = true
                break
            }
            for (j in 0 until 4) {
                val nr = r + d[j]
                val nc = c + d[j + 1]
                if (nr !in 0..<h || nc !in 0..<w) continue
                if (g[nr][nc] == '#' || added[nr][nc]) continue
                q.addLast(nr to nc)
//                cout.write("added $nr $nc ${g[nr][nc]}\n")
                added[nr][nc] = true
            }
            val ch = g[r][c] - 'a'
//            cout.write("$r $c ch:$ch\n")
            if (ch in 0..<26) {
//                cout.write("warping from $r $c $ch\n")
                for ((wr, wc) in p[ch]) {
                    if (added[wr][wc]) continue
                    q.addLast(wr to wc)
                    added[wr][wc] = true
//                    cout.write("added by warping $wr $wc ${g[wr][wc]}\n")
                }
                p[ch].clear()
            }
        }
        if (found) break
        ans++
    }
    if (!found) ans = -1
    cout.write("${ans}\n")
    cout.flush()
}

Submission Info

Judge Result