The Maze

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 136 ms)

Metric	Value
Runtime	136 ms
Memory	27.9 MB
Date	2019-12-08

Solution

public class Solution {
    public bool HasPath(int[][] maze, int[] start, int[] destination) {
    int m = maze.Length;
    int n = maze[0].Length;
    Queue<Point> bfs = new Queue<Point>();
    bool[,] visited = new bool[m, n];
    bfs.Enqueue(new Point(start[0], start[1]));
    visited[start[0], start[1]] = true;
    var dirs = new List<int[]> { new int[] { 1, 0 }, new int[] { -1, 0 }, new int[] { 0, -1 }, new int[] { 0, 1 } };

    while (bfs.Count != 0)
    {
        var head = bfs.Dequeue();
        if (head.x == destination[0] && head.y == destination[1])
        {
            return true;
        }
        foreach (var dir in dirs)
        {
            var xx = head.x;
            var yy = head.y;
            while (xx >= 0 && xx < m && yy >= 0 && yy < n && maze[xx][yy] == 0)
            {
                xx += dir[0];
                yy += dir[1];
            }
            xx -= dir[0];
            yy -= dir[1];
            if(visited[xx,yy]) continue;
            visited[xx,yy] = true;
            
            if(xx == destination[0] && yy == destination[1])
            {
                return true;
            }
            bfs.Enqueue(new Point(xx, yy));
        }
    }
    return false;
}
}

public class Point
{
    public int x { get; set; }
    public int y { get; set; }
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

📜 1 more C# submission(s)

Submission (2018-05-27) — 244 ms, N/A

public class Solution {
    public bool HasPath(int[,] maze, int[] start, int[] destination) {
      int m = maze.GetLength(0), n = maze.GetLength(1);
    if (start[0] == destination[0] && start[1] == destination[1]) return true;
    int[,] dir = new int[,] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    bool[,] visited = new bool[m,n];
    Queue<Point> list = new Queue<Point>();
    visited[start[0],start[1]] = true;
    list.Enqueue(new Point(start[0], start[1]));
    while (list.Count>0)
    {
        Point p = list.Dequeue();
        int x = p.x, y = p.y;
        for (int i = 0; i < 4; i++)
        {
            int xx = x, yy = y;
            while (xx >= 0 && xx < m && yy >= 0 && yy < n && maze[xx,yy] == 0)
            {
                xx += dir[i,0];
                yy += dir[i,1];
            }
            xx -= dir[i,0];
            yy -= dir[i,1];
            if (visited[xx,yy]) continue;
            visited[xx,yy] = true;
            if (xx == destination[0] && yy == destination[1]) return true;
            list.Enqueue(new Point(xx, yy));
        }
    }
    return false;

}
class Point
{
    public int x, y;
    public Point(int _x, int _y) { x = _x; y = _y; }
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed