[白俊]1941号:有名な七姫

当初,DFSナビゲーションまたはBFSナビゲーションによりバックエンド追跡を行い,Yが4回出現したときに停止し,合計7回ナビゲーションが発生したときに正確なカウントを向上させることを試みたが,以下のテストケースの限界はDFSとBFSでは解決できなかった.

import java.util.*

var answer = 0
val dx = listOf(1, 0, -1, 0)
val dy = listOf(0, 1, 0, -1)
lateinit var seats: MutableList<List<String>>
lateinit var isPrincess: Array<Boolean>
lateinit var selected: Array<Int>

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    seats = mutableListOf()
    for (i in 0 until 5) {
        seats.add(br.readLine().split("").filter { it.isNotBlank() })
    }
    
    isPrincess = Array(25) { false }
    selected = Array(7) { 0 }
    
    combination(0, 0, 0)
    
    bw.write("$answer")

    br.close()
    bw.close()
}

fun combination(index: Int, cntTotal: Int, cntS: Int,) {
    if(cntTotal == 7) {
        if (cntS >= 4) {
            if (isAdjacent()) answer++
        }
        return
    }

    for(i in index..24) {
        isPrincess[i] = true
        selected[cntTotal] = i
        if (seats[i / 5][i % 5] == "S") combination(i + 1, cntTotal + 1, cntS + 1)
        else combination(i + 1, cntTotal + 1, cntS)
        
        isPrincess[i] = false
    }
}

fun isAdjacent(): Boolean {
    val visited = Array(25) { false }
    val queue: Queue<Int> = LinkedList()
    queue.add(selected[0])
    var cnt = 1
    
    while (queue.isNotEmpty()) {
        val curr = queue.poll()
        
        for (i in 0..3) {
            val nx = curr / 5 + dx[i]
            val ny = curr % 5 + dy[i]
            val next = nx * 5 + ny
            if (nx !in 0..4 || ny !in 0..4) continue
            if (visited[next]) continue
            if (!isPrincess[next]) continue

            cnt++
            visited[next] = true
            queue.add(next)
        }
    }
    
    return cnt == 7
}