[C++] DP+BFS, non-Overflowing Solution Explained, ~97% Time, ~80% Space
Premise: I love a good challenge. But that is usually properly specced, not just letting people submit until they figure out what is expected.\n\nAs it was the 
Premise: I love a good challenge. But that is usually properly specced, not just letting people submit until they figure out what is expected.\n\nAs it was the case here, since we are not given any information about the maximum size of the map, number of obstacles, etc. All things that in an interview you would not be told initially, since they are also assessing you on how much and how soon you ask about the constraint. While here you will just have to go through a pointless trial and error.\n\nSad.\n\nOkay, enough with the ranting.\n\nI decided to have a DP-BFS hybrid approach to solve it (after my plain DFS solution failed miserably, see the extra goodie at the bottom).\n\nSo, first of all I check if I am getting either empty columns or empty rows - because nobody bothered to tell us if we would, but okay, I will cut it now -, and in case return `0`.\n\nIf not we set down a few helper variables:\n* `x` and `y`, matching our destination goal;\n* `qLen`, that we will use soon after, but can confidently initialise to `1`.\n\nOther edge case (last one!), and we exit if either the starting or the finishing point are blocked, again returning `0`.\n\nIf we are still in the game, we need to clone `grid` into another container made of `long`s, because reasons and because so some languages get a "fair" extra challenge, in order to avoid overflow.\n\nAfter all this unrequested chores, we can finally start doing something more substantial, like declaring our queue `nextLayer`, made of pairs of `int`s to store the coordinate of the next points we are going to visit and then push up inside `x` and `y`, our starting point (I decide to take this problem bottom-up, also because I found it nicer to handle with the conditionals later).\n\nAlso note that I set the initial value of our starting point to `-1`: this way we do not have to be concerned about the `1`s we will find, as obstacles, otherwise wasting more memory to switch values while filling in `dp`.\n\nAnd then the BFS begins: we are going to loop until `qLen` is truthy, which means until we have at least one more cell to visit.\n\nWe will then loop `qLen` times, doing this:\n* getting updated `x` and `y` values from the front of the queue;\n* popping the used node out of the queue;\n* then we move left, checking if we did not go off the bonds (`x > 0`) and if it is a valid, unblocked cell (`dp[y][x] < 1`, see note above about using negative values to represent our potential paths); if so, we push the new coordinates into the queue only if the cell was not visited before (ie: still at value `0`), in order to avoid duplicates, and update its value with the value of all the possible paths we inherited from the previous one;\n* same logic for the `y` coordinate moving up, but this time always inserting the values in the queue (we already checked left, so we cannot put a duplicate just moving up).\n\nAfter this is all done, we update `qLen` and are ready for the next loop.\n\nIn the end we return `-dp[0][0]` (remember we used the trick to store the results as negative numbers) and are done :)\n\nTo help you visualise how the DP part would work, a visual example with this starting situation (remember that `1` are walls, while we keep track of the possible paths up to a specific cells with its negative value):\n\n```cpp\n// initial map\n0  1  0  0  1  0\n0  0  0  0  0  0\n0  0  1  0  0  0\n```\n\nLet\'s flag our starting point with `-` the amount of paths up to that cell, by definition `1` for the first step:\n\n```cpp\n// we start\n 0  0  0  0  1  0\n 1  0  0  0  0  0\n 0  0  1  0  0 -1\n```\n\nAnd then let\'s proceed with our BFS approach:\n\n```cpp\n// second step\n 0  0  0  0  1  0\n 1  0  0  0  0 -1\n 0  0  1  0 -1 -1\n\n// third step\n 0  0  0  0  1 -1\n 1  0  0  0 -2 -1 //note: first cell we can reach from 2 different paths\n 0  0  1 -1 -1 -1\n\n// fourth step\n 0  0  0  0  1 -1\n 1  0  0 -3 -2 -1 //note: first cell we can reach from 3 different paths and first paths blocked\n 0  0  1 -1 -1 -1\n\n// fifth step\n 0  0  0 -3  1 -1\n 1  0 -3 -3 -2 -1\n 0  0  1 -1 -1 -1\n\n// sixth step\n 0  0 -3 -3  1 -1\n 1 -3 -3 -3 -2 -1\n 0  0  1 -1 -1 -1\n\n// seventh step\n 0 -6 -3 -3  1 -1\n 1 -3 -3 -3 -2 -1\n 0  0  1 -1 -1 -1\n\n// eight and last step\n-6 -6 -3 -3  1 -1\n 1 -3 -3 -3 -2 -1\n 0  0  1 -1 -1 -1\n\n// we would then return -dp[0][0] == 6 possible paths!\n```\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& grid) {\n        // edge case - empty columns or rows\n        if (!grid.size() || !grid[0].size()) return 0;\n        int x = grid[0].size() - 1, y = grid.size() - 1, qLen = 1;\n        // edge cases - destination or starting point blocked\n        if (grid[y][x] || grid[0][0]) return 0;\n        // annoyingly necessarily cloned grid here\n        long dp[y + 1][x + 1];\n        for (int _y = 0; _y <= y; _y++) {\n            for (int _x = 0; _x <= x; _x++) dp[_y][_x] = grid[_y][_x];\n        }\n        queue<pair<int, int>> nextLayer;\n        nextLayer.push({x, y});\n        dp[y][x] = -1;\n        while (qLen) {\n            for (int i = 0; i < qLen; i++ ) {\n                x = nextLayer.front().first;\n                y = nextLayer.front().second;\n                // removing the used cell\n                nextLayer.pop();\n                // checking the cell on left of the current one\n                if (x > 0 && dp[y][x - 1] < 1) {\n                    if (dp[y][x - 1] == 0) nextLayer.push({x - 1, y});\n                    dp[y][x - 1] += dp[y][x];\n                }\n                // checking the cell on top of the current one\n                if (y > 0 && dp[y - 1][x] < 1) {\n                    nextLayer.push({x, y - 1});\n                    dp[y - 1][x] += dp[y][x];\n                }\n            }\n            // preparing for the next run\n            qLen = nextLayer.size();\n        }\n        return -dp[0][0];\n    }\n};\n```\n\nExtra goodie - my original DFS code, not passing because the author of this problem did not bother putting a single number about the limits we were going to face, but still good for smaller maps:\n\n```cpp\nclass Solution {\npublic:\n    int xLen, yLen, res = 0;\n    void dfs(vector<vector<int>> &grid, int x = 0, int y = 0) {\n        // exit for out of bonds cases or obstacle found\n        if (x < 0 || y < 0 || x > xLen || y > yLen || grid[y][x]) return;\n        // goal reached\n        if (x == xLen && y == yLen) {\n            res++;\n            return;\n        }\n        // marking the cell as visited\n        grid[y][x] = 1;\n        // exploring north, east, south, west\n        dfs(grid, x + 1, y);\n        dfs(grid, x, y + 1);\n        // backtracking the cell as visitable\n        grid[y][x] = 0;\n    }\n    int uniquePathsWithObstacles(vector<vector<int>>& grid) {\n        // edge case\n        if (!grid.size() || !grid[0].size()) return res;\n        // updating class variables\n        xLen = grid[0].size() - 1;\n        yLen = grid.size() - 1;\n        dfs(grid);\n        return res;\n    }\n};\n```
['Dynamic Programming', 'Breadth-First Search', 'C', 'C++']