Untitled

package org.aliance3

import kotlin.random.Random

fun main() {
    IslandKotlinTest().test()
}

class IslandKotlinTest {

//    @Test
    fun test() {
        val island = Island(28, 10)
        while (true) {
            val values = readln().split(" ").map { it.toInt() }
            island.from = Point(values[0], values[1])
            island.to = Point(values[2], values[3])
            println(island.ownToString())
        }
    }
}

class Island(private val cols: Int, private val rows: Int)  {

    private val random = Random.Default
    private val map = Table(cols, rows) { coin() }

    var from: Point = Point(1, 1)
    var to: Point = Point(cols, rows)

    private fun markPath() {
        findPath(from, to).forEach { map.set(it, 2) }
    }

    private fun findPath(from: Point, to: Point) =
        buildEdgesTree(from, to).let { if (it.isEmpty()) listOf() else traverseThroughMap(it, to) }

    private fun traverseThroughMap(edges: Map<Point, Point>, to: Point) =
        generateSequence(to) { edges[it] }.toList().reversed()

    private fun buildEdgesTree(from: Point, to: Point): Map<Point, Point> {
        val markUpMap = Table(cols, rows) { false }
        val edges = HashMap.newHashMap<Point, Point>(cols * rows)
        val queue = ArrayDeque<Point>()
        queue += from
        markVisited(markUpMap, from)
        while (queue.isNotEmpty() && queue.first() != to) {
            val cur = queue.removeFirst()
            neighbours(cur, markUpMap) { neighbour ->
                queue += neighbour
                markVisited(markUpMap, neighbour)
                edges[neighbour] = cur
            }
        }
        return if (queue.isEmpty()) mapOf() else edges
    }

    private fun countIslands(): Int {
        val markUpMap = Table(cols, rows) { false }
        var k = 0
        map.forEach {
            if (it.value == 1 && !markUpMap.get(it.point)) {
                ++k
                markIslandAsVisited(it.point, markUpMap)
            }
        }
        return k
    }

    private fun markIslandAsVisited(point: Point, markUpMap: Table<Boolean>) {
        markVisited(markUpMap, point)
        neighbours(point, markUpMap) { markIslandAsVisited(it, markUpMap) }
    }

    private fun neighbours(p: Point, markUpMap: Table<Boolean>, consumer: (Point) -> Unit) {
        return listOf(
                Point(p.x + 1, p.y),
                Point(p.x - 1, p.y),
                Point(p.x, p.y + 1),
                Point(p.x, p.y - 1)
            ).filter { it.x in 1..cols && it.y in 1..rows }
            .filter { !markUpMap.get(it) }
            .filter { map.get(it) == 1 }
            .forEach { consumer.invoke(it) }
    }

    private fun markVisited(markUpMap: Table<Boolean>, point: Point) {
        markUpMap.set(point, true)
    }

    private fun coin() = random.nextInt(100).let { if (it > 30) 1 else 0 }

    fun ownToString(): String {
        markPath()
        val builder = StringBuilder(rows * cols)
        map.forEach { c ->
            builder.append(
                when (c.value) {
                    0 -> "@"
                    1 -> "·"
                    2 -> "+"
                    else -> IllegalStateException()
                }
            )
            builder.append(" ")
            if (c.point.x == cols) {
                builder.append("\n")
            }
        }
        builder.append("Islands: ").append(countIslands()).append("\n")
        return builder.toString()
    }
}

data class Point(val x: Int, val y: Int)
data class Cell<T> (var value: T, val point: Point)

class Table<T> (val cols: Int, val rows: Int, private val initFunction: () -> T) : Iterable<Cell<T>> {

    private val table = generateSequence {
        MutableList<T>(rows) { initFunction.invoke() }
    }.take(cols).toList()

    override fun iterator() = Iter()
    fun get(x: Int, y: Int) = table[x - 1][y - 1]
    fun get(point: Point) = get(point.x, point.y)
    fun set(point: Point, value: T) {
        table[point.x - 1][point.y - 1] = value
    }

    inner class Iter : Iterator<Cell<T>> {
        private var x: Int = -1
        private var y: Int = 0

        override fun hasNext() = x != cols - 1 || y != rows - 1
        override fun next(): Cell<T> {
            if (x != cols - 1) {
                x += 1
            } else {
                x = 0
                y += 1
            }
            return Point(x + 1, y + 1).let { Cell(get(it), it) }
        }
    }

}