C# Coding Test Course, Pathfinding

Hello! In this article, we will discuss one of the algorithm problems that frequently appears in coding tests, the Path Finding problem. This tutorial will explain the definition of the problem, the solution, C# code implementation, and more. We will start with the fundamentals of the necessary algorithms and explore how to apply complex pathfinding algorithms.

Problem Definition

The problem is as follows:

Find the shortest path from the starting point S to the endpoint E in a given 2D grid. The grid consists of 0s and 1s, where 0 represents a traversable cell and 1 represents a wall. The path can only move to adjacent cells in up, down, left, or right directions. If a path exists, return the length of the shortest path; if not, return -1.

Example

Here are the example inputs and outputs:

Input:
grid = [
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 1],
  [0, 1, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [1, 1, 1, 1, 0]
]
start = (0, 0)  // Position of S
end = (4, 4)    // Position of E

Output:
Length of the shortest path = 8

Approach to Problem Solving

There are various methods to solve the problem, but we will use the BFS (Breadth-First Search) algorithm. BFS is very effective in solving shortest path problems. It explores the current node and its adjacent nodes in turn, returning the shortest path after exploring all nodes.

Algorithm Explanation

The basic structure of the BFS algorithm is as follows:

  1. Put the starting point in the queue and mark it as visited.
  2. Repeat while the queue is not empty:
    • Dequeue the current position from the queue.
    • If the current position is the endpoint, return the length of the shortest path.
    • Check all adjacent cells of the current position:
      • If the cell is traversable and not visited, add it to the queue and mark it as visited.
  3. If the endpoint is not reached after exploring all paths, return -1.

C# Code Implementation

Now, let’s implement the algorithm described above in C# code.


using System;
using System.Collections.Generic;

class Program {
    public static int ShortestPath(int[,] grid, (int, int) start, (int, int) end) {
        int rows = grid.GetLength(0);
        int cols = grid.GetLength(1);
        
        int[] directions = {0, 1, 0, -1, 0}; // Up, Down, Left, Right movements

        Queue<((int, int), int)> queue = new Queue<((int, int), int)>();
        bool[,] visited = new bool[rows, cols];
        
        queue.Enqueue((start, 0)); // (position, length of the path)
        visited[start.Item1, start.Item2] = true;

        while (queue.Count > 0) {
            var (current, length) = queue.Dequeue();

            if (current == end) {
                return length;
            }

            for (int i = 0; i < 4; i++) {
                int newRow = current.Item1 + directions[i];
                int newCol = current.Item2 + directions[i + 1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && 
                    grid[newRow, newCol] == 0 && !visited[newRow, newCol]) {
                    
                    queue.Enqueue(((newRow, newCol), length + 1));
                    visited[newRow, newCol] = true;
                }
            }
        }

        return -1; // If unable to reach the endpoint
    }

    public static void Main() {
        int[,] grid = {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 1},
            {0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {1, 1, 1, 1, 0}
        };
        
        var start = (0, 0);
        var end = (4, 4);
        int result = ShortestPath(grid, start, end);
        Console.WriteLine("Length of the shortest path: " + result);
    }
}

Code Review

The above code demonstrates how to find a path using the BFS algorithm. Let’s take a closer look at each part of the code.

Variable Explanation

  • rows and cols: Store the number of rows and columns in the grid.
  • directions: Define the directions for up, down, left, and right movements.
  • queue: A queue for BFS that stores pairs of (position, length of the path).
  • visited: A 2D array that keeps track of whether each cell has been visited.

Functioning of the Queue

We dequeue the current position from the queue and check all adjacent cells, adding them to the queue if they are traversable. This process continues until we find the shortest path.

Performance Analysis

The time complexity of this algorithm is O(V + E), where V is the number of vertices (all cells in the 2D grid) and E is the number of edges (the number of adjacent cells). The space complexity is O(V), which accounts for the space required for the BFS queue and visit tracking.

Conclusion

In this article, we discussed the pathfinding problem using C#. We explained the process of finding the shortest path using the BFS algorithm and implemented it in code. When solving algorithmic problems, it is important to understand the problem accurately and select the appropriate algorithm for the approach. I hope you can improve your skills through various problems!

Thank you!