C# - DFS - verbose but clear code and beats 100% (for C# entries)


  • 0

    Here I use the standard DFS search technique keeping in mind to try the directions in lexicographical order to fulfill the requirement of finding the first lexicographical path with the shortest distance.

    public class Solution
    {
        const int MARK_VISITED = 2;
        const int MARK_EMPTY = 0;
    
        int[,] maze;
        int[] ball;
        int[] hole;
        int shortestPathLen = int.MaxValue;
        string shortestPath = null;
        int[,] shortestMap = null;
    
        public string FindShortestWay(int[,] maze, int[] ball, int[] hole)
        {
            this.maze = maze;
            this.ball = ball;
            this.hole = hole;
            
            // store map of shortest paths from each cell in order to short curcuit search paths
            this.shortestMap = GetMatrix(this.maze.GetLength(0), this.maze.GetLength(1), int.MaxValue);
    
            // begin DFS search
            this.maze[ball[0], ball[1]] = MARK_VISITED;
            Find(new StringBuilder(), 0, ball[0], ball[1]);
            return shortestPath ?? "impossible";
        }
    
        public void Find(StringBuilder curr, int len, int r, int c)
        {
            if (len >= shortestPathLen || len >= shortestMap[r,c]) return;
            
            shortestMap[r,c] = len;
    
            if (r == hole[0] && c == hole[1])
            {
                shortestPathLen = len;
                shortestPath = curr.ToString();
                return;
            }
    
            int down = DownBoundary(r, c);
            if (down > 0 && maze[r + down, c] != MARK_VISITED)
            {
                curr.Append('d');
                maze[r + down, c] = MARK_VISITED;
                Find(curr, len + down, r + down, c);
                maze[r + down, c] = MARK_EMPTY;
                curr.Length--;
            }
    
            int left = LeftBoundary(r, c);
            if (left > 0 && maze[r, c - left] != MARK_VISITED)
            {
                curr.Append('l');
                maze[r, c - left] = MARK_VISITED;
                Find(curr, len + left, r, c - left);
                maze[r, c - left] = MARK_EMPTY;
                curr.Length--;
            }
    
            int right = RightBoundary(r, c);
            if (right > 0 && maze[r, c + right] != MARK_VISITED)
            {
                curr.Append('r');
                maze[r, c + right] = MARK_VISITED;
                Find(curr, len + right, r, c + right);
                maze[r, c + right] = MARK_EMPTY;
                curr.Length--;
            }
    
            int up = UpBoundary(r, c);
            if (up > 0 && maze[r - up, c] != MARK_VISITED)
            {
                curr.Append('u');
                maze[r - up, c] = MARK_VISITED;
                Find(curr, len + up, r - up, c);
                maze[r - up, c] = MARK_EMPTY;
                curr.Length--;
            }
        }
    
        public int RightBoundary(int r, int c)
        {
            int c2 = c;
            while (c2 < maze.GetLength(1) - 1 && maze[r, c2 + 1] != 1 && !(r == hole[0] && c2 == hole[1]))
            {
                c2++;
            }
            return c2 - c;
        }
    
        public int LeftBoundary(int r, int c)
        {
            int c2 = c;
            while (c2 > 0 && maze[r, c2 - 1] != 1 && !(r == hole[0] && c2 == hole[1]))
            {
                c2--;
            }
            return c - c2;
        }
    
        public int UpBoundary(int r, int c)
        {
            int r2 = r;
            while (r2 > 0 && maze[r2 - 1, c] != 1 && !(r2 == hole[0] && c == hole[1]))
            {
                r2--;
            }
            return r - r2;
        }
    
        public int DownBoundary(int r, int c)
        {
            int r2 = r;
            while (r2 < maze.GetLength(0) - 1 && maze[r2 + 1, c] != 1 && !(r2 == hole[0] && c == hole[1]))
            {
                r2++;
            }
            return r2 - r;
        }
        
        public int[,] GetMatrix(int n, int m, int val)
        {
            int[,] matrix = new int[n,m];
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    matrix[i,j] = val;
                }
            }
            return matrix;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.