LeetCode in Kotlin

1728. Cat and Mouse II

Hard

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.

• Players are represented by the characters 'C'(Cat),'M'(Mouse).
• Floors are represented by the character '.' and can be walked on.
• Walls are represented by the character '#' and cannot be walked on.
• Food is represented by the character 'F' and can be walked on.
• There is only one of each character 'C', 'M', and 'F' in grid.

Mouse and Cat play according to the following rules:

• Mouse moves first, then they take turns to move.
• During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid.
• catJump, mouseJump are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
• Staying in the same position is allowed.
• Mouse can jump over Cat.

The game can end in 4 ways:

• If Cat occupies the same position as Mouse, Cat wins.
• If Cat reaches the food first, Cat wins.
• If Mouse reaches the food first, Mouse wins.
• If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a rows x cols matrix grid and two integers catJump and mouseJump, return true if Mouse can win the game if both Cat and Mouse play optimally, otherwise return false.

Example 1:

Input: grid = [”####F”,”#C…”,”M….”], catJump = 1, mouseJump = 2

Output: true

Explanation: Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

Example 2:

Input: grid = [“M.C…F”], catJump = 1, mouseJump = 4

Output: true

Example 3:

Input: grid = [“M.C…F”], catJump = 1, mouseJump = 3

Output: false

Constraints:

• rows == grid.length
• cols = grid[i].length
• 1 <= rows, cols <= 8
• grid[i][j] consist only of characters 'C', 'M', 'F', '.', and '#'.
• There is only one of each character 'C', 'M', and 'F' in grid.
• 1 <= catJump, mouseJump <= 8

Solution

@Suppress("NAME_SHADOWING")
class Solution {
    private val graphs: Array<Array<List<Int>>> = arrayOf(arrayOf(), arrayOf())
    private var foodPos = 0
    private lateinit var memo: Array<Array<IntArray>>

    fun canMouseWin(grid: Array<String>, catJump: Int, mouseJump: Int): Boolean {
        val m = grid.size
        val n = grid[0].length
        var mousePos = 0
        var catPos = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                val c = grid[i][j]
                if (c == 'F') {
                    foodPos = i * n + j
                } else if (c == 'C') {
                    catPos = i * n + j
                } else if (c == 'M') {
                    mousePos = i * n + j
                }
            }
        }
        graphs[0] = buildGraph(mouseJump, grid)
        graphs[1] = buildGraph(catJump, grid)
        memo = Array(m * n) { Array(m * n) { IntArray(2) } }
        for (i in 0 until m) {
            for (j in 0 until n) {
                val c = grid[i][j]
                if (c == '#' || c == 'F') {
                    continue
                }
                val catTurn = 1
                dfs(i * n + j, foodPos, catTurn)
            }
        }
        return memo[mousePos][catPos][MOUSE_TURN] < 0
    }

    private fun buildGraph(jump: Int, grid: Array<String>): Array<List<Int>> {
        val dirs = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, 1), intArrayOf(0, -1))
        val m = grid.size
        val n = grid[0].length
        val graph: Array<List<Int>> = Array(m * n) { mutableListOf() }
        for (i in 0 until m) {
            for (j in 0 until n) {
                val list: MutableList<Int> = ArrayList()
                graph[i * n + j] = list
                if (grid[i][j] == '#') {
                    continue
                }
                list.add(i * n + j)
                for (dir in dirs) {
                    for (step in 1..jump) {
                        val x = i + dir[0] * step
                        val y = j + dir[1] * step
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') {
                            break
                        }
                        list.add(x * n + y)
                    }
                }
            }
        }
        return graph
    }

    private fun dfs(p1: Int, p2: Int, turn: Int) {
        var turn = turn
        if (p1 == p2) {
            return
        }
        if ((if (turn == 0) p2 else p1) == foodPos) {
            return
        }
        if (memo[p1][p2][turn] < 0) {
            return
        }
        memo[p1][p2][turn] = -1
        turn = turn xor 1
        for (w in graphs[turn][p2]) {
            if (turn == MOUSE_TURN || ++memo[w][p1][turn] == graphs[turn][w].size) {
                dfs(w, p1, turn)
            }
        }
    }

    companion object {
        private const val MOUSE_TURN = 0
    }
}

This site is open source. Improve this page.