C++ DFS+memo beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s generally better to use BFS for search problems like this. However, given the con
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s *generally* better to use BFS for search problems like this. However, given the constraints for this problem, DFS+memo is more than adequate; in fact it is both simpler and faster.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDFS with two 2D arrays for memoization: `hmemo` for when we\'re horizontal, and `vmemo` for when we\'re vertical. While we\'re running DFS on a point, we can set its memo to `INT_MAX-1` so the code will short-circuit if we attempt anything that could cause a cycle. I also return `INT_MAX-1` if the target is unreachable. (`INT_MAX-1` avoids overflow when doing `1+dfs(...)`).\n\n# Complexity\n- Time complexity: $$O(n^2)$$, 17ms beats 100% apparently!\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    int n;\n    vector<vector<int>> hmemo, vmemo;\n    vector<vector<int>> *gridp;\n\n    int dfs(bool h, int r, int c) {\n        vector<vector<int>> & grid = *gridp;\n        if (h && r == n-1 && c == n-2)\n            return 0;\n        int res = INT_MAX-1;\n        if (h) {\n            if (hmemo[r][c] > 0) {\n                return hmemo[r][c];\n            }\n            hmemo[r][c] = INT_MAX-1;\n            if (c+2 < n && grid[r][c+2] == 0) {\n                // move right\n                res = min(res, 1+dfs(true, r, c+1));\n            }\n            if (r+1 < n && grid[r+1][c] == 0 && grid[r+1][c+1] == 0) {\n                // move down\n                res = min(res, 1+dfs(true, r+1, c));\n                // rotate clockwise\n                res = min(res, 1+dfs(false, r, c));\n            }\n            hmemo[r][c] = res;\n            return res;\n        } else {\n            if (vmemo[r][c] > 0) {\n                return vmemo[r][c];\n            }\n            vmemo[r][c] = INT_MAX-1;\n            if (r+2 < n && grid[r+2][c] == 0) {\n                // move down\n                res = min(res, 1+dfs(false, r+1, c));\n            }\n            if (c+1 < n && grid[r][c+1] == 0 && grid[r+1][c+1] == 0) {\n                // move right\n                res = min(res, 1+dfs(false, r, c+1));\n                // rotate counterclockwise\n                res = min(res, 1+dfs(true, r, c));\n            }\n            vmemo[r][c] = res;\n            return res;\n        }\n    }\n\npublic:\n    int minimumMoves(vector<vector<int>>& grid) {\n        this->gridp = &grid;\n        n = grid.size();\n        hmemo = vector<vector<int>>(n, vector<int>(n, -1));\n        vmemo = vector<vector<int>>(n, vector<int>(n, -1));\n        int res = dfs(true, 0, 0);\n        return res < INT_MAX-1 ? res : -1;\n    }\n};\n```
['C++']