結果

問題 No.1427 Simplified Tetris
ユーザー 箱星箱星
提出日時 2020-12-19 17:12:14
言語 Kotlin
(1.9.23)
結果
WA  
実行時間 -
コード長 9,246 bytes
コンパイル時間 21,212 ms
コンパイル使用メモリ 472,496 KB
実行使用メモリ 88,884 KB
最終ジャッジ日時 2024-10-14 10:04:47
合計ジャッジ時間 40,114 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 350 ms
60,456 KB
testcase_01 AC 304 ms
56,732 KB
testcase_02 WA -
testcase_03 AC 293 ms
54,240 KB
testcase_04 AC 294 ms
54,344 KB
testcase_05 AC 351 ms
60,356 KB
testcase_06 AC 438 ms
65,704 KB
testcase_07 AC 353 ms
60,368 KB
testcase_08 AC 292 ms
54,432 KB
testcase_09 AC 554 ms
80,292 KB
testcase_10 AC 347 ms
57,148 KB
testcase_11 AC 512 ms
79,932 KB
testcase_12 AC 352 ms
57,024 KB
testcase_13 AC 343 ms
60,472 KB
testcase_14 AC 382 ms
60,920 KB
testcase_15 AC 442 ms
65,708 KB
testcase_16 AC 606 ms
88,884 KB
testcase_17 AC 386 ms
62,948 KB
testcase_18 AC 297 ms
54,168 KB
testcase_19 AC 516 ms
72,116 KB
testcase_20 AC 354 ms
56,872 KB
testcase_21 AC 294 ms
54,396 KB
testcase_22 AC 363 ms
60,420 KB
testcase_23 WA -
testcase_24 AC 424 ms
64,524 KB
testcase_25 WA -
testcase_26 AC 291 ms
54,324 KB
testcase_27 AC 289 ms
54,256 KB
testcase_28 AC 354 ms
57,124 KB
testcase_29 WA -
testcase_30 AC 353 ms
60,472 KB
testcase_31 AC 526 ms
71,964 KB
testcase_32 AC 484 ms
74,552 KB
testcase_33 AC 521 ms
70,636 KB
testcase_34 AC 350 ms
60,328 KB
testcase_35 AC 301 ms
54,372 KB
testcase_36 AC 487 ms
73,660 KB
testcase_37 AC 586 ms
86,368 KB
testcase_38 AC 500 ms
80,096 KB
testcase_39 AC 500 ms
78,040 KB
testcase_40 AC 481 ms
74,964 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter
import java.util.*
import kotlin.math.*

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<CharArray>): 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() {
    val h = nextInt()
    val w = nextInt()
    val s = Array(h) { CharArray(w) { '.' } }
    val lst = mutableListOf<CharArray>()
    for (i in 0 until h) {
        val _s = 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()
    val map = mutableMapOf<Int, String>()
    for (bits in 0 until 1.shl(h)) {
        val grid = Array(h) { CharArray(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].copyOf()
                    id++
                } else {
                    grid[h - 1 - i] = CharArray(w) { '.' }
                }
            }
        }
        if (id != lst.count()) continue
        val ans = construct(grid)
        if (ans[0] == "Yes") {
            var count = 0
            for (t in ans) {
                count += t.count { it != '.' }
            }
            map[count] = ans.joinToString("\n")
        }
    }
    if (map.count() == 0) {
        println("No")
    } else {
        println(map[map.keys.min()])
    }
}

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

// region Scanner
private var st = StringTokenizer("")
private val br = System.`in`.bufferedReader()

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()
// endregion
0