[C#] BFS + Top-down DP (explained)
Intuition\nPorted from C++: [1] https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solutions/431144/cpp-bfs-dfs-solution/\n# BFS
# Intuition\nPorted from C++: [1] https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solutions/431144/cpp-bfs-dfs-solution/\n# BFS\nFirst we sweep the given grid for finding and storing the locations of the person, the box and the target.\nNext we initialize a queue and a hashSet with the locations of the person and of the box.\n```\nQueue<PII> q = new();\nHashSet<PII> visited = new();\nq.Enqueue(new PII(new PI(px, py), new PI(bx, by)));\nvisited.Add(new PII(new PI(px, py), new PI(bx, by)))\n```\nNext, we use that queue to do BFS traversal of the 2d grid. \nEach queue element will have new box and person locations. Once an element is dequeued, the box location is updated on the grid to be maked as #.\n```\nvar f = q.Dequeue();\n(px, py) = f.Item1;\n(bx, by) = f.Item2;\ngrid[bx][by] = \'#\';\n```\nBFS will find the shortest distance simply because of its radial-search pattern which considers nodes in order of their distance from the starting point [2]. It can be shown that, for unweighted graphs, the BFS is equivalent to Dijkstra\'s algorithm and thus finds the shortest path in this circumstance. Thus the first path found will be the shortest path.\n```\nif(nbx == gx && nby == gy) {\n    return ans;\n}\n```\nValid() is used for validating a person location or a box location.\n\nOne smart feature of this implementation is the use of a HashSet for keeping track of visited cells. The HashSet keeps track of "states", not of visits. The HashSet has the location of a box and of person by the time the an element got into the queue, not simply if the grid cell was visited. That allows us to re-visit a certain cell if the "state" is different. \n```\nif(Valid(grid, nbx, nby)) {\n    PII newState = new PII(new PI(bx, by), new PI(nbx, nby));\n    if(!visited.Contains(newState)) {\n        visited.Add(newState);\n        q.Enqueue(newState);\n    }\n}\n```\n# Top-Down DP\nCanReach() is the DFS part of this solution. It will find if a person can get to the "back" of the box. pplLoc is our memoization array (turning this into top-down dp).\n```\n bool CanReach(char[][] g, bool[,] pplLoc, int x, int y, int bx, int by) {\n        if(!Valid(g, x, y) || pplLoc[x,y]) {\n            return false;\n        }\n        if(bx == x && by == y) {\n            return true;\n        }\n        pplLoc[x,y] = true;\n        foreach(var d in Dirs) {\n            if(CanReach(g, pplLoc, x + d[0], y + d[1], bx, by)) {\n                return true;\n            }\n        }\n        return false;\n    }\n```\n# Code\n```\npublic class Solution {\n    public record class PI(int Item1, int Item2);\n    public record class PII(PI Item1, PI Item2);\n    public static int[][] Dirs = new int[][]{new int[]{0,1},\n        new int[]{1,0}, new int[]{-1,0}, new int[]{0,-1}};\n    public static int m,n;\n    public int MinPushBox(char[][] grid) {\n        m = grid.Length;\n        n = grid[0].Length;\n        int px=0, py=0, bx=0, by=0, gx=0, gy=0;\n        for(int x = 0; x < m; ++x) \n        {\n            for(int y = 0; y < n; ++y) \n            {\n                if(grid[x][y] == \'S\') {\n                    px = x; \n                    py = y;\n                }else if(grid[x][y] == \'B\') {\n                    bx = x; \n                    by = y;\n                }else if(grid[x][y] == \'T\') {\n                    gx = x; \n                    gy = y;\n                }\n            }\n        }\n        Queue<PII> q = new();\n        HashSet<PII> visited = new();\n        q.Enqueue(new PII(new PI(px, py), new PI(bx, by)));\n        visited.Add(new PII(new PI(px, py), new PI(bx, by)));\n        int ans = 0;\n        while(q.Count > 0) {\n            ans++;\n            for(int l = q.Count; l > 0; --l) {\n                var f = q.Dequeue();\n                (px, py) = f.Item1;\n                (bx, by) = f.Item2;\n                grid[bx][by] = \'#\';\n                foreach(var d in Dirs) {\n                    var pplLoc = new bool[m,n];\n                    if(CanReach(grid, pplLoc, px, py, bx - d[0], by - d[1])) {\n                        int nbx = bx + d[0], nby = by + d[1];\n                        if(nbx == gx && nby == gy) {\n                            return ans;\n                        }\n                        if(Valid(grid, nbx, nby)) {\n                            PII newState = new PII(new PI(bx, by), new PI(nbx, nby));\n                            if(!visited.Contains(newState)) {\n                                visited.Add(newState);\n                                q.Enqueue(newState);\n                            }\n                        }\n                    }\n                }\n                grid[bx][by] = \'.\';\n            }\n        }\n        return -1;\n    }\n  bool CanReach(char[][] g, bool[,] pplLoc, int x, int y, int bx, int by) {\n        if(!Valid(g, x, y) || pplLoc[x,y]) {\n            return false;\n        }\n        if(bx == x && by == y) {\n            return true;\n        }\n        pplLoc[x,y] = true;\n        foreach(var d in Dirs) {\n            if(CanReach(g, pplLoc, x + d[0], y + d[1], bx, by)) {\n                return true;\n            }\n        }\n        return false;\n    }\n  bool Valid(char[][] g, int x, int y) {\n        if(x < 0 || x >= m || y < 0 || y >= n || g[x][y] == \'#\') {\n            return false;\n        }\n        return true;\n    }\n}\n```\n# References\n[1] https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solutions/431144/cpp-bfs-dfs-solution/\n[2] https://stackoverflow.com/questions/8379785/how-does-a-breadth-first-search-work-when-looking-for-shortest-path
['Depth-First Search', 'Breadth-First Search', 'C#']