Runtime- Beats 100.00%
\n# Intuition\nThis function minimumMoves calculates the minimum number of moves needed to move a body of a 2D grid from one position to another. The body can b
\n# Intuition\nThis function `minimumMoves` calculates the minimum number of moves needed to move a body of a 2D grid from one position to another. The body can be moved horizontally, vertically, or rotated 90 degrees clockwise or counterclockwise.\n\n# Approach:\n- The function uses a breadth-first search (BFS) approach to explore possible moves.\n- It maintains a queue `q` to store the positions to be explored.\n- It initializes a 2D array `vis` to keep track of visited positions to avoid revisiting.\n- The `move` function is defined to check if a move is valid and enqueue the new position if it hasn\'t been visited.\n- The function iterates through the queue, exploring possible moves until the target position is reached.\n\n# Complexity:\n- **Time Complexity:** The time complexity of this approach is O(n^2), where n is the size of the grid.\n- **Space Complexity:** The space complexity is O(n^2) due to the queue and the visited array.\n\n# Code\n```\nfunc minimumMoves(grid [][]int) int {\n\tn := len(grid)\n\ttype pair struct{ a, b int }\n\ttarget := pair{n*n - 2, n*n - 1}\n\tq := []pair{pair{0, 1}}\n\tvis := make([][2]bool, n*n)\n\tvis[0][0] = true\n\n\tmove := func(i1, j1, i2, j2 int) {\n\t\tif i1 >= 0 && i1 < n && j1 >= 0 && j1 < n && i2 >= 0 && i2 < n && j2 >= 0 && j2 < n {\n\t\t\ta, b := i1*n+j1, i2*n+j2\n\t\t\tstatus := 1\n\t\t\tif i1 == i2 {\n\t\t\t\tstatus = 0\n\t\t\t}\n\t\t\tif !vis[a][status] && grid[i1][j1] == 0 && grid[i2][j2] == 0 {\n\t\t\t\tq = append(q, pair{a, b})\n\t\t\t\tvis[a][status] = true\n\t\t\t}\n\t\t}\n\t}\n\n\tans := 0\n\tfor len(q) > 0 {\n\t\tfor k := len(q); k > 0; k-- {\n\t\t\tp := q[0]\n\t\t\tq = q[1:]\n\t\t\tif p == target {\n\t\t\t\treturn ans\n\t\t\t}\n\t\t\ta, b := p.a, p.b\n\t\t\ti1, j1 := a/n, a%n\n\t\t\ti2, j2 := b/n, b%n\n\t\t\t\n\t\t\tmove(i1, j1+1, i2, j2+1)\n\t\t\t\n\t\t\tmove(i1+1, j1, i2+1, j2)\n\t\t\t\n\t\t\tif i1 == i2 && i1+1 < n && grid[i1+1][j2] == 0 {\n\t\t\t\tmove(i1, j1, i1+1, j1)\n\t\t\t}\n\t\t\n\t\t\tif j1 == j2 && j1+1 < n && grid[i2][j1+1] == 0 {\n\t\t\t\tmove(i1, j1, i1, j1+1)\n\t\t\t}\n\t\t}\n\t\tans++\n\t}\n\treturn -1\n}\n```
['Go']