文章目录
1. 题目2. 解题
1. 题目
你还记得那条风靡全球的贪吃蛇吗？
我们在一个 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)）。
如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。
返回蛇抵达目的地所需的最少移动次数。
如果无法到达目的地，请返回 -1。
示例 1：
输入：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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
把尾巴的坐标 x,y 还有方向 d，三个信息编码成101进制数然后蛇可以三种走法：前进、整体平移、绕尾巴旋转
class Solution {
vector
<vector
<int>> dir
= {{0,1}, {1,0}};
int n
;
public:
int minimumMoves(vector
<vector
<int>>& grid
) {
n
= grid
.size();
if(grid
[n
-1][n
-2] || grid
[n
-1][n
-1])
return -1;
int state
, nt
, pos
, d
, nd
, i
, j
, k
, x
, y
, x1
, y1
, x2
, y2
;
queue
<int> q
;
unordered_set
<int> vis
;
q
.push(0);
int step
= 0, size
;
int target
= (101*(n
-1)+(n
-2))*101;
while(!q
.empty())
{
size
= q
.size();
while(size
--)
{
state
= q
.front();
q
.pop();
if(state
== target
)
return step
;
d
= state
%101;
pos
= state
/101;
i
= pos
/101;
j
= pos
%101;
x
= i
+dir
[d
][0];
y
= j
+dir
[d
][1];
x1
= i
+dir
[d
][0];
y1
= j
+dir
[d
][1];
x2
= x
+ dir
[d
][0];
y2
= y
+ dir
[d
][1];
nt
= (101*x1
+y1
)*101+d
;
if(ok(x2
, y2
) && grid
[x2
][y2
]== 0
&& !vis
.count(nt
))
{
vis
.insert(nt
);
q
.push(nt
);
}
nd
= d
== 0 ? 1 : 0;
x1
= i
+dir
[nd
][0];
y1
= j
+dir
[nd
][1];
x2
= x
+ dir
[nd
][0];
y2
= y
+ dir
[nd
][1];
nt
= (101*x1
+y1
)*101+d
;
if(ok(x1
, y1
) && grid
[x1
][y1
]==0
&& ok(x2
, y2
) && grid
[x2
][y2
]== 0
&& !vis
.count(nt
))
{
vis
.insert(nt
);
q
.push(nt
);
}
nt
= state
/101*101 + nd
;
if(ok(x1
, y1
) && grid
[x1
][y1
]==0
&& ok(x2
, y2
) && grid
[x2
][y2
]== 0
&& !vis
.count(nt
))
{
vis
.insert(nt
);
q
.push(nt
);
}
}
step
++;
}
return -1;
}
bool ok(int x
, int y
)
{
return x
>=0 && x
< n
&& y
>=0 && y
<n
;
}
};
132 ms 17.5 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
