Use BFS or multi-source BFS starting at terminal states. When you mark a state as a win for one player, check all predecessors. A predecessor is a mouse-win if it is the mouse's turn and any move leads to a mouse-win. It is a cat-win if it is the cat's turn and any move leads to a cat-win.
Keep track of how many children each state has. When all children of a state lead to the opponent winning, that state is a loss.