python coding test course, path finding

Problem Description

This is a problem of finding a path from the starting point to the endpoint in a given 2D array. This array consists of passages and obstacles, where passages are represented by 0 and obstacles by 1.

The goal is to determine whether there is a path from the given starting point to the endpoint and to output the possible path. Movement is allowed in four directions: up, down, left, and right.

Problem Definition

    def find_path(maze, start, end):
        """
        :param maze: 2D list representing the maze
        :param start: Tuple of (x, y) coordinates for the start point
        :param end: Tuple of (x, y) coordinates for the end point
        :return: List of tuples representing the path or None if no path exists
        """
    

Problem Example

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)  # Starting point
    end = (4, 4)    # Endpoint
    

Expected result:
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]

Solution Approach

This problem can be solved using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithms. Here, I will explain how to find a path using DFS.

Depth-First Search (DFS) Algorithm

DFS explores all possible paths to determine if the endpoint is reachable. During the path search, it keeps track of visited nodes to prevent revisiting.

Implementation Steps

Step 1: Basic Setup

First, define the maze and the starting and ending points through basic setup.

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)
    end = (4, 4)
    

Step 2: Define the DFS Function

Implement a function to find the path using DFS.

    def dfs(maze, current, end, path, visited):
        if current == end:
            return path
        
        x, y = current
        visited.add(current)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):
                if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:
                    result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)
                    if result is not None:
                        return result
        
        visited.remove(current)
        return None
    

Step 3: Implement the Path Finding Function

Finally, implement the path finding function to call DFS.

    def find_path(maze, start, end):
        visited = set()
        return dfs(maze, start, end, [start], visited)
    

Step 4: Output the Result

Call the function to output the result.

    path = find_path(maze, start, end)
    print("Path:", path)
    

Complete Code

    def dfs(maze, current, end, path, visited):
        if current == end:
            return path
        
        x, y = current
        visited.add(current)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):
                if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:
                    result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)
                    if result is not None:
                        return result
        
        visited.remove(current)
        return None

    def find_path(maze, start, end):
        visited = set()
        return dfs(maze, start, end, [start], visited)

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)
    end = (4, 4)
    path = find_path(maze, start, end)
    print("Path:", path)