题目描述： 你还记得那条风靡全球的贪吃蛇吗？
我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和 (0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2) 和 (n-1, n-1)）。
每次移动，蛇可以这样走：
如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。 如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。 如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。
输入：grid = [[0,0,0,0,0,1], [1,1,0,0,1,0], [0,0,0,0,1,1], [0,0,1,0,1,0], [0,1,1,0,0,0], [0,1,1,0,0,0]] 输出：11 解释： 一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。 示例 2：
输入：grid = [[0,0,1,1,1,1], [0,0,0,0,1,1], [1,1,0,0,0,1], [1,1,1,0,0,1], [1,1,1,0,0,1], [1,1,1,0,0,0]] 输出：9
提示：
2 <= n <= 100 0 <= grid[i][j] <= 1 蛇保证从空单元格开始出发。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-moves-to-reach-target-with-rotations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
用DFS失败了。。。 看看别人实现的代码；
class Solution { public int minimumMoves(int[][] grid) { final int BLOCK = -1; final int WHITE = 0; final int GRAY = 1; final int BLACK = 2; int rows = grid.length, columns = grid[0].length; int[][][] colors = new int[rows][columns][2]; int[][][] distances = new int[rows][columns][2]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { distances[i][j][0] = Integer.MAX_VALUE; distances[i][j][1] = Integer.MAX_VALUE; } } for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (grid[i][j] == 1) { colors[i][j][0] = BLOCK; colors[i][j][1] = BLOCK; distances[i][j][0] = -1; distances[i][j][1] = -1; if (i > 0) { colors[i - 1][j][1] = BLOCK; distances[i - 1][j][1] = -1; } if (j > 0) { colors[i][j - 1][0] = BLOCK; distances[i][j - 1][0] = -1; } } if (i == rows - 1) { colors[i][j][1] = BLOCK; distances[i][j][1] = -1; } if (j == columns - 1) { colors[i][j][0] = BLOCK; distances[i][j][0] = -1; } } } distances[0][0][0] = 0; Queue<int[]> queue = new LinkedList<int[]>(); queue.add(new int[]{0, 0, 0}); while (!queue.isEmpty()) { int[] status = queue.poll(); int row = status[0], column = status[1], direction = status[2]; int distance = distances[row][column][direction]; if (row < rows - 1) { int rowDown = row + 1; if (colors[rowDown][column][direction] == WHITE) { colors[rowDown][column][direction] = GRAY; distances[rowDown][column][direction] = distance + 1; queue.offer(new int[]{rowDown, column, direction}); } } if (column < columns - 1) { int columnRight = column + 1; if (colors[row][columnRight][direction] == WHITE) { colors[row][columnRight][direction] = GRAY; distances[row][columnRight][direction] = distance + 1; queue.offer(new int[]{row, columnRight, direction}); } } int newDirection = 1 - direction; if (colors[row][column][newDirection] == WHITE && row < rows - 1 && column < columns - 1 && grid[row + 1][column + 1] == 0) { colors[row][column][newDirection] = GRAY; distances[row][column][newDirection] = distance + 1; queue.offer(new int[]{row, column, newDirection}); } colors[row][column][direction] = BLACK; } int retDistance = distances[rows - 1][columns - 2][0]; if (retDistance == Integer.MAX_VALUE) retDistance = -1; return retDistance; } }