Uber OA-5 2023

Problem Description

It is the year 2050, and humans have evolved into two supernatural species: Alpha (Alph) and Beta (Bts). Yakohama, the kingdom of the Alpha group, is under threat from Beta members who plan to attack through a secret path in the forest. Akari, the king of Yakohama, must defend his kingdom by killing as many Bts members as possible in the forest.

The forest is represented by an m*n grid where each cell either contains a volcano (denoted by 1) or a Beta member (denoted by 0). Akari can move left, right, up, or down to kill Beta members in cells containing a 0. He cannot enter cells containing volcanoes, as he will be engulfed by lava. Akari also has a limited number of hours to complete his mission, and he must return to his starting position (top-left corner) before his time runs out.

Your task is to determine the maximum number of Beta members Akari can kill, given his movement constraints and time limit.

Input Format:

• forestPlan: A 2D integer array where 0 represents a Beta member and 1 represents a volcano.
• hours_to_survive: An integer representing the maximum number of hours Akari can survive and move in the forest.

Output Format:

• Return an integer representing the maximum number of Beta members Akari can kill, ensuring he returns to the starting point (top-left corner) within the time limit.

Constraints:

• 1 <=forestPlan.length<=10
• 1 <=forestPlan[i].length<= 10
• 1 <=hours_to_survive <=12
• The starting point will not contain a volcano (forestPlan[0][0] is always 0).

Sample Testcase:

Input:

forestPlan = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
]
hours_to_survive = 6

Output:

3

Explanation:

In the given grid:

• forestPlan = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
• Akari starts at position (0, 0) and can take the path: (0, 0) → (0, 1) → (0, 2) → (0, 1) → (0, 0).
• Along this path, Akari kills 3 Bts members, and he returns to the starting point within 6 hours.