C++ BFS
Intuition\nThis looks like BFS problem, where horizontal and vertical paths are independent (but can be transitioned to and from). So, we need to track \'visite
# Intuition\nThis looks like BFS problem, where horizontal and vertical paths are independent (but can be transitioned to and from). So, we need to track \'visited\' state independently for horizontal and vertical orientations.\n# Modified BFS\nThis type of problems is not hard, but it could be trickly to get the code right. I created three helper functions to make it a bit easier.\n\n1. Use a queue to store the tail coordinates and orientation.\n2. For every element in the queue, check the visited flag and move up, down or rotate, if possible.\n> Here, I am using second and third bit (2 and 4) to track the state directly in the grid.\n3. Return the number of steps in BFS if we reach the target; otherwise return ```-1```\n```\nbool canRotate(vector<vector<int>>& g, int i, int j) {\n  return i < g.size() - 1 && j < g[i].size() - 1\n    && (g[i + 1][j] & 1) == 0 && (g[i][j + 1] & 1) == 0 && (g[i + 1][j + 1] & 1) == 0;\n}\nbool canGoDown(vector<vector<int>>& g, int i, int j, bool vertical) {\n  if (vertical) return i < g.size() - 2 && (g[i + 2][j] & 1) == 0;\n  return i < g.size() - 1 && (g[i + 1][j] & 1) == 0 && (g[i + 1][j + 1] & 1) == 0;\n}\nbool canGoRight(vector<vector<int>>& g, int i, int j, bool vertical) {\n  if (!vertical) return j < g[i].size() - 2 && (g[i][j + 2] & 1) == 0;\n  return j < g[i].size() - 1 && (g[i][j + 1] & 1) == 0 && (g[i + 1][j + 1] & 1) == 0;\n}\nint minimumMoves(vector<vector<int>>& grid, int steps = 0) {\n  queue<array<int, 3>> q1, q2;\n  q1.push({ 0, 0, false }); // not vertical.\n  while (!q1.empty()) {\n    while (!q1.empty()) {\n      auto& a = q1.front();\n      if (a[0] == grid.size() - 1 && a[1] == grid[a[0]].size() - 2) return steps;\n      if ((grid[a[0]][a[1]] & (a[2] ? 2 : 4)) == 0) {\n        grid[a[0]][a[1]] = grid[a[0]][a[1]] | (a[2] ? 2 : 4);\n        if (canGoDown(grid, a[0], a[1], a[2])) q2.push({ a[0] + 1, a[1], a[2] });\n        if (canGoRight(grid, a[0], a[1], a[2])) q2.push({ a[0], a[1] + 1, a[2] });\n        if (canRotate(grid, a[0], a[1])) q2.push({ a[0], a[1], a[2] ? false : true });\n      }\n      q1.pop();\n    }\n    ++steps;\n    swap(q1, q2);\n  }\n  return -1;\n}\n```
[]