Posts tagged as “min-max”

花花酱 LeetCode 1728. Cat and Mouse II

By zxi on January 17, 2021

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

Example 4:

Input: grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
Output: false

Example 5:

Input: grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
Output: true

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: MinMax + Memoization

Time complexity: O(m^3 * n^3 * max(n, m))
Space complexity: O(m^3 * n^3)

state: [mouse_pos, cat_pos, turn]

C++

// Author: Huahua

class Solution {

public:

bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {

const int m = grid.size(), n = grid[0].size();

int mouse, cat, food;

for (int pos = 0; pos < m * n; ++pos)

switch (grid[pos / n][ pos % n]) {

case 'M': mouse = pos; break;

case 'C': cat = pos; break;

case 'F': food = pos; break;

default: break;

}

const vector<pair<int, int>> dirs{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

const int limit = m * n * 2;

vector<vector<vector<int>>> seen(m*n,

vector<vector<int>>(m*n, vector<int>(limit + 1, -1)));

function<bool(int, int, int)> dfs =

[&](int mouse, int cat, int d) -> bool {

const bool isCat = d & 1;

if (cat == food || cat == mouse || d >= limit) return isCat;

if (mouse == food) return !isCat;

int& ans = seen[mouse][cat][d];

if (ans != -1) return ans;

const int cur = isCat ? cat : mouse;

const int jumps = isCat ? catJump : mouseJump;

for (const auto& [dx, dy] : dirs)

for (int j = 0; j <= jumps; ++j) {

const int x = (cur % n) + dx * j;

const int y = (cur / n) + dy * j;

const int pos = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == '#') break;

if (!dfs(isCat ? mouse : pos, isCat ? pos : cat, d + 1)) return ans = true;

}

return ans = false;

};

return dfs(mouse, cat, 0);

}

};

花花酱 LeetCode 877. Stone Game

By zxi on July 28, 2018

Problem

Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

Example 1:

Input: [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

Note:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.

Solution 1: min-max (TLE)

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: TLE 26/46 passed.

class Solution {

public:

bool stoneGame(vector<int>& piles) {

return score(piles, 0, piles.size() - 1) > 0;

}

private:

int score(const vector<int>& piles, int l, int r) {

if (l == r) return piles[l];

return max(piles[l] - score(piles, l + 1, r),

piles[r] - score(piles, l, r - 1));

}

};

Solution 2: min-max + memorization

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

m_ = vector<vector<int>>(n, vector<int>(n, INT_MIN));

return score(piles, 0, n - 1) > 0;

}

private:

vector<vector<int>> m_;

int score(const vector<int>& piles, int l, int r) {

if (l == r) return piles[l];

if (m_[l][r] == INT_MIN)

m_[l][r] = max(piles[l] - score(piles, l + 1, r),

piles[r] - score(piles, l, r - 1));

return m_[l][r];

}

};

Solution 3: min-max + DP

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

// dp[i][j] := max(your_stones - op_stones) for piles[i] ~ piles[j]

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int i = 0; i < n; ++i)

dp[i][i] = piles[i];

for (int l = 2; l <= n; ++l)

for (int i = 0; i < n - l + 1; ++i) {

int j = i + l - 1;

dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);

}

return dp[0][n - 1] > 0;

}

};

O(n) Space

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

// dp[i] := max(your_stones - op_stones) for piles[i] to piles[i + l - 1]

vector<int> dp(piles);

for (int l = 2; l <= n; ++l)

for (int i = 0; i < n - l + 1; ++i)

dp[i] = max(piles[i] - dp[i + 1], piles[i + l - 1] - dp[i]);

return dp[0] > 0;

}

};

Problem

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

Solution 1: Recursion

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

int getScore(vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

return max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

}

};

Solution 2: Recursion + Memoization

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

m_ = vector<vector<int>>(nums.size(), vector<int>(nums.size(), INT_MIN));

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

vector<vector<int>> m_;

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

int getScore(vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

if (m_[l][r] != INT_MIN) return m_[l][r];

m_[l][r] = max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

return m_[l][r];

}

};

DP version

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> dp(n, vector<int>(n, INT_MIN));

for (int i = 0; i < n; ++i)

dp[i][i] = nums[i];

for (int l = 2; l <= n; ++l)

for (int i = 0; i <= n - l; ++i) {

int j = i + l - 1;

dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);

}

return dp[0][n - 1] >= 0;

}

};

Posts tagged as “min-max”

花花酱 LeetCode 1728. Cat and Mouse II

Solution: MinMax + Memoization

C++

花花酱 LeetCode 877. Stone Game

Problem

Solution 1: min-max (TLE)

Solution 2: min-max + memorization

Solution 3: min-max + DP

Related Problems

花花酱 LeetCode 464. Can I Win

花花酱 LeetCode 486. Predict the Winner

Problem

Solution 1: Recursion

Solution 2: Recursion + Memoization

Related Problem