Problem of March '21

It’s March and another problem of the month is here. As I chose some Div. II Hard problems in previous months, this time I chose a simpler problem, Div. 2 Medium level.

The problem we have is TheQuestForGold .

I chose this problem because:

• I found a different solution than the editorial solution. So, there are at least two solutions to the problem that can help you understand different ways to solve this kind of a problem.

• It’s a good start for practicing DFS and BFS. It involves the basics of DFS and BFS and can be a good problem for someone who is practicing this concept.

• It’s an application of DFS and BFS on matrices.

• Low rate of accepted solutions during the SRM. I use this as a parameter to pick a problem statement that might have been trickier to tackle during the contest.

Prerequisites: DFS of BFS.

Given a map of a game, containing S as starting position, P as die position, T as gold position (maybe absent) and dot (.) as empty position.

In this game two cells are adjacent if they share a side. In each move the player can go to an adjacent cell. Adjacent cells of a die position have some warning, you can notice that there is a die position adjacent to this cell.

The goal of the game is first not to die, and second to find the gold.

Is it possible to find the gold?

One approach is described in the editorial by misof. I describe another approach that can help you understand misof’s approach too.

The first point to notice is when we enter a cell with a warning, we just step back; any other move may cause death. Although my approach is not easier to code, it gives a good view on the problem, which is why I take this approach.

We try to discover safe cells with no warning one by one, we call this safe-discovery. It means we discover every cell without warning that has a path with cells without warning to the starting position.

1
2
3
4
5
6
7
8
9
10
{
  "SDDDD",
  "...DD",
  "PPP.D",
  "...DD",
  "DDDDD",
  "DD...",
  "D.PPP",
  "DDT.."
}

As you can see above, we can safe-discover all cells signed with “D”. Also we can safe-discover “S”. But we can’t safe-discover T. Why? Because T is a cell with warning.

Note that not all cells that we can discover are safe-discoverable. The sample above is a clear example. If T is a safe-discoverable cell, the answer is surely positive. The other case that makes the answer positive is that T is not safe-discoverable, but it’s adjacent with a safe-discoverable cell. In the latter case, we can first move to the safe-discoverable cell and then visit T, which is a cell with warning and cannot be safe-discovered.

Finding safe-discoverable cells is easy using DFS or BFS. Do not enter cells with a warning during DFS or BFS.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from collections
import deque
class TheQuestForGold:
  def explore(self, cave):
  queue = deque()
seen = [[False] * len(cave[0]) for i in range(len(cave))]

def inside(c):
  return 0 <= c[0] < len(cave) and 0 <= c[1] < len(cave[0])

def adjacent(c):
  x, y = c
result = []
for candidate in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
  if inside(candidate):
  result += [candidate]
return result

def good(c):
  return inside(c) and not seen[c[0]][c[1]] and all(not inside(adj_1) or cave[adj_1[0]][adj_1[1]] != 'P'
    for adj_1 in
    adjacent(c))

t_pos = None
for i in range(len(cave)):
  for j in range(len(cave[0])):
  if cave[i][j] == 'S'
and good([i, j]):
  queue += [[i, j]]
seen[i][j] = True
if cave[i][j] == 'T':
  t_pos = [i, j]

while len(queue) > 0:
  v = queue.popleft()
for adj in filter(good, adjacent(v)):
  queue += [adj]
seen[adj[0]][adj[1]] = True
return "gold"
if t_pos and any(seen[adj[0]][adj[1]]
  for adj in adjacent(t_pos))
else "no gold"