val codeMap = charArrayOf('M', 'W', 'G', 'C', '.')
fun CharArray.getCode(direction: Boolean): Int { var result = if (direction) 1else0 for (i in0 until 4) { result = (result shl 3) or codeMap.findIndex(this[i], codeMap.indices) } return result }
/** 存储输入的站位 */ val rdm = CharArray(4) /** 存储目标序列 */ val dist = CharArray(8) /** 存储目标序列的方向 */ var distDirection = false /** 存储当前序列 */ val map = CharArray(8) /** 存储当前序列的方向 */ var direction = false /** 目标序列的 code */ var distCode = 0
funmain() { direction = read(map) distDirection = read(dist) distCode = dist.getCode(distDirection) for (i in0 until 4) { rdm[i] = if (map[i] == '.') map[i + 4] else map[i] } if (!dfs()) print("None") }
/** 移动顺序 */ val moveOrder = charArrayOf('W', 'G', 'C') /** 标记是否为第一次找到答案 */ var nonFirst = false /** 标记指定序列是否访问过 */ val record = BooleanArray(1 shl 13) /** 存储路径 */ val list = LinkedList<Int>()
fundfs(): Boolean { val code = map.getCode(direction) if (record[code] || !check()) returnfalse list += code // 检查当前状态是否和目标状态相同 if (code == distCode) { // 如果初始状态和目标状态相同,则直接返回 false if (list.size == 1) returnfalse if (nonFirst) println() else nonFirst = true list.forEach { print(parseCode(it)) } list.removeLast() returntrue } record[code] = true val offset = if (direction) 4else -4 direction = !direction // 先尝试人单独过河 val mIndex = findIndex('M', offset) map.swap(mIndex, mIndex + offset) var result = dfs() if (!result) { // 一次尝试人带一个过河 for (value in moveOrder) { val index = findIndex(value, offset) if (index != -1) { map.swap(index, index + offset) if (dfs()) result = true map.swap(index, index + offset) } } } map.swap(mIndex, mIndex + offset) direction = !direction record[code] = false list.removeLast() return result }
funcheck(): Boolean { val offset = if (direction) -4else4 val w = findIndex('W', offset) val g = findIndex('G', offset) if (w != -1 && g != -1) returnfalse val c = findIndex('C', offset) return g == -1 || c == -1 }
/** 在指定范围内查找指定元素的下标 */ fun CharArray.findIndex(dist: Char, range: IntRange): Int { for (i in range) { if (this[i] == dist) return i } return -1 }
/** * 在指定范围的序列中查找目标下标 * @param dist 目标 * @param offset 4 表示在 [0, 4) 范围内查找,-4 表示在 [4, 8) 范围内查找 * @return 查找到返回下标,否则返回 -1 */ funfindIndex(dist: Char, offset: Int): Int { val left = if (offset == 4) 0else4 return map.findIndex(dist, left until left + 4) }
/** 将 code 转换为字符串 */ funparseCode(code: Int): String { val sb = StringBuilder(14) 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() }
/** 将指定状态哈希化 */ fun CharArray.getCode(direction: Boolean): Int { var result = if (direction) 1else0 for (i in0 until 4) { result = (result shl 3) or codeMap.findIndex(this[i], codeMap.indices) } return result }
/** * 读取一个状态 * @return 方向,true 向右,false 向左 */ funread(map: CharArray): Boolean = with(System.`in`) { for (i in0 until 4) map[i] = read().toChar() read() val direction = read() == '-'.code skip(2) for (i in4 until 8) map[i] = read().toChar() read() direction }
// 在指定范围内搜索目标下标 intfindIndex(char array[], char dist, int left, int right){ for (int i = left; i != right; ++i) { if (array[i] == dist) return i; } return-1; }
// 在指定范围内查找目标下标 intfindIndex(char dist, int offset){ int left = offset == 4 ? 0 : 4; returnfindIndex(map, dist, left, left + 4); } // 检查当前序列是否合法 boolcheck(){ int offset = direction ? -4 : 4; int w = findIndex('W', offset); int g = findIndex('G', offset); if (w != -1 && g != -1) returnfalse; int c = findIndex('C',offset); return g == -1 || c == -1; }
/** 映射表 */ val codeMap = charArrayOf('M', 'W', 'G', 'C', '.') /** 存储输入的站位 */ var rdm = State(0) /** 存储当前序列 */ var map = read().let { val tmp = State(it) for (i in0 until 4) { val dist = tmp[i] rdm = rdm.set(i, if (dist == '.') tmp[i + 4] else dist) } it.zipCode() } /** 存储目标序列 */ val dist = read().zipCode()
funmain() { if (!dfs()) print("None") }
/** 移动顺序 */ var moveOrder = charArrayOf('W', 'G', 'C') /** 标记是否为第一次找到答案 */ var nonFirst = false /** 标记指定序列是否访问过 */ var record = BooleanArray(8200) /** 存储路径 */ var list = LinkedList<State>()
fundfs(): Boolean { if (record[map.value] || !map.legal) returnfalse list += map // 检查当前状态是否和目标状态相同 if (map == dist) { // 如果初始状态和目标状态相同,则直接返回 false if (list.size == 1) returnfalse if (nonFirst) println() else nonFirst = true list.forEach { print(it.toString()) } list.removeLast() returntrue } 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 classState(val value: Int) {
/** * 设置指定位置上的符号 * @param count 下标(从右往左,从 0 开始递增) * @param dist 要设置的符号 */ funset(count: Int, dist: Char): State { val code = codeMap.indexOf(dist) val base = count * 3 var result = value for (i in0 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) }
overridefuntoString(): 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 in3 downTo 0) sb.append(getOpposite(i)) sb.append('\n') return sb.toString() }
}
/** 将状态码压缩到 13bit,存储左侧数据 */ funInt.zipCode(): State = State((this.shr(12) and 0xFFF) or (this shr 24).shl(12))
/** * 读取一个状态 * @return 第 25 位表示方向 1 为右,0 为左,然后从最高位到最低位依次存储输入,一位输入占 3bit */ funread(): Int = with(System.`in`) { var result = 0 for (i in0 until 4) { result = (result shl 3) or codeMap.indexOf(read().toChar()) } read() val direction = read() == '-'.code skip(2) for (i in0 until 4) { result = (result shl 3) or codeMap.indexOf(read().toChar()) } read() if (direction) result = result or (1 shl 24) result }