人狼羊菜过河详细题解

/** 存储输入的站位  */
val rdm = CharArray(4)

fun main() {
    // do something
    for (i in 0 until 4) {
        // 这里的 map 是输入的起始状态
        rdm[i] = if (map[i] == '.') map[i + 4] else map[i]
    }
    // do something
}

val codeMap = charArrayOf('M', 'W', 'G', 'C', '.')

fun CharArray.getCode(direction: Boolean): Int {
    var result = if (direction) 1 else 0
    for (i in 0 until 4) {
        result = (result shl 3) or codeMap.findIndex(this[i], codeMap.indices)
    }
    return result
}

fun parseCode(code: Int): String {
    // 注意使用循环拼接字符串时 StringBuilder 优先于直接使用加号
    // 如果是使用类似于 `str = 'a' + i + 'b' + q` 的写法的话，两者性能没有区别
    val sb = StringBuilder(13)
    val parse = intArrayOf(
        (code shr 9) and 7,
        (code shr 6) and 7,
        (code shr 3) and 7,
        code and 7
    )
    parse.forEach { sb.append(codeMap[it]) }
    sb.append(if (code shr 12 == 0) " <- " else " -> ")
    parse.forEachIndexed { i, value ->
        sb.append(if (value == 0b100) rdm[i] else '.')
    }
    sb.append('\n')
    return sb.toString()
}

import java.util.*

/** 映射表 */
val codeMap = charArrayOf('M', 'W', 'G', 'C', '.')
/** 存储输入的站位  */
var rdm = State(0)
/** 存储当前序列  */
var map = read().let {
    val tmp = State(it)
    for (i in 0 until 4) {
        val dist = tmp[i]
        rdm = rdm.set(i, if (dist == '.') tmp[i + 4] else dist)
    }
    it.zipCode()
}
/** 存储目标序列  */
val dist = read().zipCode()

fun main() {
    if (!dfs())
        print("None")
}

/** 移动顺序  */
var moveOrder = charArrayOf('W', 'G', 'C')
/** 标记是否为第一次找到答案  */
var nonFirst = false
/** 标记指定序列是否访问过  */
var record = BooleanArray(8200)
/** 存储路径  */
var list = LinkedList<State>()

fun dfs(): Boolean {
    if (record[map.value] || !map.legal) return false
    list += map
    // 检查当前状态是否和目标状态相同
    if (map == dist) {
        // 如果初始状态和目标状态相同，则直接返回 false
        if (list.size == 1) return false
        if (nonFirst) println()
        else nonFirst = true
        list.forEach { print(it.toString()) }
        list.removeLast()
        return true
    }
    record[map.value] = true
    map = map.flipDirection()
    // 先尝试人单独过河
    val mIndex = map.find('M')
    map = map.swap(mIndex)
    var result = dfs()
    if (!result) {
        // 一次尝试人带一个过河
        for (value in moveOrder) {
            val index = map.find(value)
            if (index != -1) {
                map = map.swap(index)
                if (dfs()) result = true
                map = map.swap(index)
            }
        }
    }
    map = map.swap(mIndex).flipDirection()
    record[map.value] = false
    list.removeLast()
    return result
}

/** 保存状态 */
@JvmInline
value class State(val value: Int) {

    /** 获取方向 */
    private val direction: Boolean
        get() = value shr 12 == 1

    /** 是否合法 */
    val legal: Boolean
        get() {
            val w = find('W')
            val g = find('G')
            if (w != -1 && g != -1) return false
            return g == -1 || find('C') == -1
        }

    /** 查找指定符号的位置 */
    fun find(dist: Char): Int {
        for (i in 0 until 4) {
            if (this[i, !direction] == dist) return i
        }
        return -1
    }

    /** 翻转方向 */
    fun flipDirection(): State = State(
        if (direction) value and 1.shl(12).inv() else value or 1.shl(12)
    )

    /** 交换指定值 */
    fun swap(count: Int): State = set(count, getOpposite(count))

    /**
     * 获取指定位置或其对称位置上的符号
     * @param count 下标（从右往左，从 0 开始递增）
     * @param notFlip 是否不取对称位置
     */
    operator fun get(count: Int, notFlip: Boolean): Char =
        if (notFlip) this[count] else getOpposite(count)

    /**
     * 获取指定位上的符号
     * @param count 下标（从右往左，从 0 开始递增）
     */
    operator fun get(count: Int): Char = codeMap[(value shr (count * 3)) and 0b111]

    /**
     * 获取与指定位置对称的位置上的符号
     * @param count 下标（从右往左，从 0 开始递增）
     */
    private fun getOpposite(count: Int): Char {
        val dist = this[count]
        return if (dist == '.') rdm[count] else '.'
    }

    /**
     * 设置指定位置上的符号
     * @param count 下标（从右往左，从 0 开始递增）
     * @param dist 要设置的符号
     */
    fun set(count: Int, dist: Char): State {
        val code = codeMap.indexOf(dist)
        val base = count * 3
        var result = value
        for (i in 0 until 3) {
            val bit = (code shr i) and 1
            val tmp = 1.shl(base + i)
            result = if (bit == 0) result and tmp.inv() else result or tmp
        }
        return State(result)
    }

    override fun toString(): String {
        val sb = StringBuilder(14)
        val parse = charArrayOf(this[3], this[2], this[1], this[0])
        parse.forEach { sb.append(it) }
        sb.append(if (direction) " -> " else " <- ")
        for (i in 3 downTo 0) sb.append(getOpposite(i))
        sb.append('\n')
        return sb.toString()
    }

}

/** 将状态码压缩到 13bit，存储左侧数据 */
fun Int.zipCode(): State = State((this.shr(12) and 0xFFF) or (this shr 24).shl(12))

/**
 * 读取一个状态
 * @return 第 25 位表示方向 1 为右，0 为左，然后从最高位到最低位依次存储输入，一位输入占 3bit
 */
fun read(): Int =
    with(System.`in`) {
        var result = 0
        for (i in 0 until 4) {
            result = (result shl 3) or codeMap.indexOf(read().toChar())
        }
        read()
        val direction = read() == '-'.code
        skip(2)
        for (i in 0 until 4) {
            result = (result shl 3) or codeMap.indexOf(read().toChar())
        }
        read()
        if (direction) result = result or (1 shl 24)
        result
    }