Description

One day, you wake up inside a mysterious underground maze. Fortunately, you discover a map showing the walls, open spaces, and the exit.

The maze is represented as an M × N grid, containing four symbols:

• . : An open space you can walk through.

• x : A wall you cannot pass through (lowercase x, not uppercase X).

• S : Your starting position.

• D : The destination you want to reach.

You may move up, down, left, or right. Diagonal movement is not allowed.

Before attempting to escape, you decide to investigate the maze and discover how many possible escape routes are available.

Your task is to implement the following two functions:

1. survey_zone(row, col)

The maze may contain several disconnected areas.

A safe zone is a group of connected walkable cells. Two cells belong to the same safe zone if you can travel between them without passing through walls.

Explore the safe zone containing the given position and mark all reachable cells as visited.

• row and col represent the current position.

• Both S and D are considered walkable cells.

• Return 1 if the position belongs to a previously unexplored safe zone.

• Return 0 if the position is outside the maze, is a wall, or has already been visited.

2. count_escape_routes(row, col)

An escape route is a path that starts at S and ends at D.

Count the total number of different valid escape routes.

• row and col represent the current position.

• An escape route must not contain any loops. Each cell can be visited at most once within the same route.

• Different routes may share cells, but each route must be counted separately.

• Use the global variable paths to count the total number of valid escape routes.

• The function does not need to return a value.

Important Notes

• You may only move up, down, left, or right. Diagonal movement is not allowed.

• You cannot move outside the maze or through walls.

• The wall symbol is a lowercase x, not an uppercase X.

• The maze contains exactly one starting position S and one destination D.

• An escape route ends immediately upon reaching D.

• The two functions use separate visited arrays: visited_zones and visited_routes.

Start code

m, n = map(int, input().split())
maze = [list(input()) for _ in range(m)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited_zones = [[False] * n for _ in range(m)]
visited_routes = [[False] * n for _ in range(m)]
zones = 0
paths = 0
for i in range(m):
    for j in range(n):
        if maze[i][j] == 'S':
            start_row, start_col = i, j

def survey_zone(row, col):
    # TODO
    pass

def count_escape_routes(row, col):
    # TODO
    pass

for i in range(m):
    for j in range(n):
        zones += survey_zone(i, j)
count_escape_routes(start_row, start_col)
print("Safe Zones:", zones)
print("Escape Routes:", paths)

Input

The first line contains two integers, M and N, representing the number of rows and columns in the maze.

The next M lines each contain exactly N characters representing the maze, with no spaces between characters.

Each character is one of ., x, S, or D.

Output

Print two lines:

• Safe Zones: Z, where Z is the total number of disconnected safe zones.

• Escape Routes: P, where P is the total number of valid escape routes from S to D.

If no escape route exists, P should be 0.

Sample Input  Download

Sample Output  Download

Discuss