Hello! In this article, we will discuss one of the algorithm problems that frequently appears in coding tests, the Path Finding<\/strong> 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.<\/p>\n The problem is as follows:<\/p>\n 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.<\/p>\n<\/blockquote>\n Here are the example inputs and outputs:<\/p>\n There are various methods to solve the problem, but we will use the BFS (Breadth-First Search)<\/strong> 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.<\/p>\n The basic structure of the BFS algorithm is as follows:<\/p>\n Now, let’s implement the algorithm described above in C# code.<\/p>\n 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.<\/p>\n 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.<\/p>\nProblem Definition<\/h2>\n
\n
Example<\/h2>\n
\nInput:\ngrid = [\n [0, 0, 1, 0, 0],\n [0, 0, 0, 0, 1],\n [0, 1, 1, 0, 0],\n [0, 0, 0, 0, 0],\n [1, 1, 1, 1, 0]\n]\nstart = (0, 0) \/\/ Position of S\nend = (4, 4) \/\/ Position of E\n\nOutput:\nLength of the shortest path = 8\n<\/pre>\n
Approach to Problem Solving<\/h2>\n
Algorithm Explanation<\/h3>\n
\n
\n
\n
C# Code Implementation<\/h2>\n
\nusing System;\nusing System.Collections.Generic;\n\nclass Program {\n public static int ShortestPath(int[,] grid, (int, int) start, (int, int) end) {\n int rows = grid.GetLength(0);\n int cols = grid.GetLength(1);\n \n int[] directions = {0, 1, 0, -1, 0}; \/\/ Up, Down, Left, Right movements\n\n Queue<((int, int), int)> queue = new Queue<((int, int), int)>();\n bool[,] visited = new bool[rows, cols];\n \n queue.Enqueue((start, 0)); \/\/ (position, length of the path)\n visited[start.Item1, start.Item2] = true;\n\n while (queue.Count > 0) {\n var (current, length) = queue.Dequeue();\n\n if (current == end) {\n return length;\n }\n\n for (int i = 0; i < 4; i++) {\n int newRow = current.Item1 + directions[i];\n int newCol = current.Item2 + directions[i + 1];\n\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && \n grid[newRow, newCol] == 0 && !visited[newRow, newCol]) {\n \n queue.Enqueue(((newRow, newCol), length + 1));\n visited[newRow, newCol] = true;\n }\n }\n }\n\n return -1; \/\/ If unable to reach the endpoint\n }\n\n public static void Main() {\n int[,] grid = {\n {0, 0, 1, 0, 0},\n {0, 0, 0, 0, 1},\n {0, 1, 1, 0, 0},\n {0, 0, 0, 0, 0},\n {1, 1, 1, 1, 0}\n };\n \n var start = (0, 0);\n var end = (4, 4);\n int result = ShortestPath(grid, start, end);\n Console.WriteLine(\"Length of the shortest path: \" + result);\n }\n}\n<\/code><\/pre>\nCode Review<\/h2>\n
Variable Explanation<\/h3>\n
\n
rows<\/code> and cols<\/code>: Store the number of rows and columns in the grid.<\/li>\ndirections<\/code>: Define the directions for up, down, left, and right movements.<\/li>\nqueue<\/code>: A queue for BFS that stores pairs of (position, length of the path).<\/li>\nvisited<\/code>: A 2D array that keeps track of whether each cell has been visited.<\/li>\n<\/ul>\nFunctioning of the Queue<\/h3>\n
Performance Analysis<\/h2>\n