#577618 (Kotlin) No.1427 Simplified Tetris

• 問題: No.1427 Simplified Tetris
• ユーザー: 箱星
• 提出日時: 2020-11-08 05:21:14
• 言語: Kotlin (2.1.0)
• 結果: AC
• 実行時間: 515 ms / 2,000 ms
• コード長: 9,223 bytes
• コンパイル時間: 21,765 ms
• コンパイル使用メモリ: 462,792 KB
• 実行使用メモリ: 79,952 KB
• 最終ジャッジ日時: 2024-10-14 10:04:00
• 合計ジャッジ時間: 39,410 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 37

コンパイルメッセージ

Main.kt:292:18: warning: name shadowed: s
            for (s in ans) {
                 ^

ソースコード

import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

class MaxFlow(private val n: Int) {
    inner class CapEdge internal constructor(val from: Int, val to: Int, var cap: Long, val rev: Int) {
        val flow: Long
            get() = g[to][rev]!!.cap
    }

    private var m = 0
    private val edges: ArrayList<CapEdge> = ArrayList()
    private val count: IntArray = IntArray(n)
    private val g: Array<Array<CapEdge?>> = Array(n) { emptyArray<CapEdge?>() }

    fun addEdge(from: Int, to: Int, cap: Long): Int {
        rangeCheck(from, 0, n)
        rangeCheck(to, 0, n)
        nonNegativeCheck(cap, "Capacity")
        val e = CapEdge(from, to, cap, count[to])
        count[from]++
        count[to]++
        edges.add(e)
        return m++
    }

    fun getEdge(i: Int): CapEdge {
        rangeCheck(i, 0, m)
        return edges[i]
    }

    fun getEdges(): ArrayList<CapEdge> {
        return edges
    }

    fun changeEdge(i: Int, newCap: Long, newFlow: Long) {
        rangeCheck(i, 0, m)
        nonNegativeCheck(newCap, "Capacity")
        require(newFlow <= newCap) { String.format("Flow %d is greater than capacity %d.", newCap, newFlow) }
        val e = edges[i]
        val er = g[e.to][e.rev]
        e.cap = newCap - newFlow
        er!!.cap = newFlow
    }

    private fun buildGraph() {
        for (i in 0 until n) {
            g[i] = arrayOfNulls(count[i])
        }
        val idx = IntArray(n)
        for (e in edges) {
            g[e.to][idx[e.to]++] = CapEdge(e.to, e.from, 0, idx[e.from])
            g[e.from][idx[e.from]++] = e
        }
    }

    fun maxFlow(s: Int, t: Int): Long {
        return flow(s, t, INF)
    }

    fun flow(s: Int, t: Int, flowLimit: Long): Long {
        rangeCheck(s, 0, n)
        rangeCheck(t, 0, n)
        buildGraph()
        var flow: Long = 0
        val level = IntArray(n)
        val que = IntArray(n)
        val iter = IntArray(n)
        while (true) {
            Arrays.fill(level, -1)
            dinicBFS(s, t, level, que)
            if (level[t] < 0) return flow
            Arrays.fill(iter, 0)
            while (true) {
                val d = dinicDFS(t, s, flowLimit - flow, iter, level)
                if (d <= 0) break
                flow += d
            }
        }
    }

    private fun dinicBFS(s: Int, t: Int, level: IntArray, que: IntArray) {
        var hd = 0
        var tl = 0
        que[tl++] = s
        level[s] = 0
        while (tl > hd) {
            val u = que[hd++]
            for (e in g[u]) {
                val v = e!!.to
                if (e.cap <= 0 || level[v] >= 0) continue
                level[v] = level[u] + 1
                if (v == t) return
                que[tl++] = v
            }
        }
    }

    private fun dinicDFS(cur: Int, s: Int, f: Long, iter: IntArray, level: IntArray): Long {
        if (cur == s) return f
        var res: Long = 0
        while (iter[cur] < count[cur]) {
            val er = g[cur][iter[cur]++]
            val u = er!!.to
            val e = g[u][er.rev]
            if (level[u] >= level[cur] || e!!.cap <= 0) continue
            val d = dinicDFS(u, s, minOf(f - res, e.cap), iter, level)
            if (d <= 0) continue
            e.cap -= d
            er.cap += d
            res += d
            if (res == f) break
        }
        return res
    }

    fun fordFulkersonMaxFlow(s: Int, t: Int): Long {
        return fordFulkersonFlow(s, t, INF)
    }

    fun fordFulkersonFlow(s: Int, t: Int, flowLimit: Long): Long {
        rangeCheck(s, 0, n)
        rangeCheck(t, 0, n)
        buildGraph()
        val used = BooleanArray(n)
        var flow: Long = 0
        while (true) {
            Arrays.fill(used, false)
            val f = fordFulkersonDFS(s, t, flowLimit - flow, used)
            if (f <= 0) return flow
            flow += f
        }
    }

    private fun fordFulkersonDFS(cur: Int, t: Int, f: Long, used: BooleanArray): Long {
        if (cur == t) return f
        used[cur] = true
        for (e in g[cur]) {
            if (used[e!!.to] || e.cap <= 0) continue
            val d = fordFulkersonDFS(e.to, t, minOf(f, e.cap), used)
            if (d <= 0) continue
            e.cap -= d
            g[e.to][e.rev]!!.cap += d
            return d
        }
        return 0
    }

    fun minCut(s: Int): BooleanArray {
        rangeCheck(s, 0, n)
        val reachable = BooleanArray(n)
        val stack = IntArray(n)
        var ptr = 0
        stack[ptr++] = s
        reachable[s] = true
        while (ptr > 0) {
            val u = stack[--ptr]
            for (e in g[u]) {
                val v = e!!.to
                if (reachable[v] || e.cap <= 0) continue
                reachable[v] = true
                stack[ptr++] = v
            }
        }
        return reachable
    }

    private fun rangeCheck(i: Int, minInclusive: Int, maxExclusive: Int) {
        if (i < minInclusive || i >= maxExclusive) {
            throw IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, maxExclusive))
        }
    }

    private fun nonNegativeCheck(cap: Long, attribute: String) {
        require(cap >= 0) { String.format("%s %d is negative.", attribute, cap) }
    }

    companion object {
        private const val INF = Long.MAX_VALUE
    }
}

fun construct(grid: Array<Array<Char>>): List<String> {
    val n = grid.count()
    val m = grid[0].count()
    var blocks = 0L
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (grid[i][j] == '#') blocks++
        }
    }
    val g = MaxFlow(n * m + 2)
    val s = n * m
    val t = n * m + 1
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (grid[i][j] == '.') continue
            val v = i * m + j
            if ((i + j) % 2 == 0) {
                g.addEdge(s, v, 1)
            } else {
                g.addEdge(v, t, 1)
            }
        }
    }
    for (i in 0 until n) {
        for (j in 0 until m) {
            if ((i + j) % 2 != 0 || grid[i][j] == '.') continue
            val v0 = i * m + j
            if (i > 0 && grid[i - 1][j] == '#') {
                val v1 = (i - 1) * m + j
                g.addEdge(v0, v1, 1)
            }
            if (j > 0 && grid[i][j - 1] == '#') {
                val v1 = i * m + (j - 1)
                g.addEdge(v0, v1, 1)
            }
            if (i + 1 < n && grid[i + 1][j] == '#') {
                val v1 = (i + 1) * m + j
                g.addEdge(v0, v1, 1)
            }
            if (j + 1 < m && grid[i][j + 1] == '#') {
                val v1 = i * m + (j + 1)
                g.addEdge(v0, v1, 1)
            }
        }
    }
    val maxflow = g.maxFlow(s, t)
    if (maxflow * 2 != blocks) {
        return listOf("No")
    }
    val lst = mutableListOf("Yes")
    val chars = (0 until 52).map { if (it < 26) 'a' + it else 'A' + (it - 26) }.toList()
    var id = 0
    for (e in g.getEdges()) {
        if (e.from == s || e.to == t || e.flow == 0L) continue
        val i0 = e.from / m
        val j0 = e.from % m
        val i1 = e.to / m
        val j1 = e.to % m
        grid[i0][j0] = chars[id]
        grid[i1][j1] = chars[id]
        id++
    }
    for (i in 0 until n) {
        lst.add(grid[i].joinToString(""))
    }
    return lst
}

fun PrintWriter.solve(sc: FastScanner) {
    val h = sc.nextInt()
    val w = sc.nextInt()
    val s = Array(h) { Array(w) { '.' } }
    val lst = mutableListOf<Array<Char>>()
    for (i in 0 until h) {
        val _s = sc.nextLine()
        var empty = true
        var allblock = true
        for (j in 0 until w) {
            s[i][j] = _s[j]
            if (s[i][j] == '#') empty = false
            if (s[i][j] == '.') allblock = false
        }
        if (allblock || (empty && lst.count() > 0)) {
            println("No")
            return
        }
        if (!empty) {
            lst.add(s[i])
        }
    }
    lst.reverse()
    for (bits in 0 until 1.shl(h)) {
        val grid = Array(h) { Array(w) { '#' } }
        var id = 0
        for (i in 0 until h) {
            if ((1.shl(i) and bits) != 0) {
                if (id < lst.count()) {
                    grid[h - 1 - i] = lst[id]
                    id++
                } else {
                    grid[h - 1 - i] = Array(w) { '.' }
                }
            }
        }
        if (id != lst.count()) continue
        val ans = construct(grid)
        if (ans[0] == "Yes") {
            for (s in ans) {
                println(s)
            }
            return
        }
    }
    println("No")
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}