作者推荐
本文涉及知识点
动态规划汇总
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LCP 57. 打地鼠
勇者面前有一个大小为3*3 的打地鼠游戏机，地鼠将随机出现在各个位置，moles[i] = [t,x,y] 表示在第 t 秒会有地鼠出现在 (x,y) 位置上，并于第 t+1 秒该地鼠消失。
勇者有一把可敲打地鼠的锤子，初始时刻（即第 0 秒）锤子位于正中间的格子 (1,1)，锤子的使用规则如下：
锤子每经过 1 秒可以往上、下、左、右中的一个方向移动一格，也可以不移动
锤子只可敲击所在格子的地鼠，敲击不耗时
请返回勇者最多能够敲击多少只地鼠。
注意：
输入用例保证在相同时间相同位置最多仅有一只地鼠
示例 1：
输入： moles = [[1,1,0],[2,0,1],[4,2,2]]
输出： 2
解释： 第 0 秒，锤子位于 (1,1) 第 1 秒，锤子移动至 (1,0) 并敲击地鼠 第 2 秒，锤子移动至 (2,0) 第 3 秒，锤子移动至 (2,1) 第 4 秒，锤子移动至 (2,2) 并敲击地鼠 因此勇者最多可敲击 2 只地鼠
示例 2：
输入：moles = [[2,0,2],[5,2,0],[4,1,0],[1,2,1],[3,0,2]]
输出：3
解释： 第 0 秒，锤子位于 (1,1) 第 1 秒，锤子移动至 (2,1) 并敲击地鼠 第 2 秒，锤子移动至 (1,1) 第 3 秒，锤子移动至 (1,0) 第 4 秒，锤子在 (1,0) 不移动并敲击地鼠 第 5 秒，锤子移动至 (2,0) 并敲击地鼠 因此勇者最多可敲击 3 只地鼠
示例 3：
输入：moles = [[0,1,0],[0,0,1]]
输出：0
解释： 第 0 秒，锤子初始位于 (1,1)，此时并不能敲击 (1,0)、(0,1) 位置处的地鼠
提示：
1 *seft = max(*seft, other); } class Solution { public: int getMaximumNumber(vector m_c = moles.size(); sort(moles.begin(), moles.end()); vector const int dis = abs(moles[i][1] - x) + abs(moles[i][2] - y); return moles[i][0] - preTime = dis; }; for (int i = 0, j = 0; i
测试用例
template
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i
2023年4月
class Solution {
public:
int getMaximumNumber(vector& moles) {
vector vMoves(5,vector(9));
for (int i = 0; i
{
const int r = i / 3;
const int c = i % 3;
vector& v = vMoves[1][i];
if (r > 0)
{
v.emplace_back(i - 3);
}
if (r + 1
{
v.emplace_back(i + 3);
}
if (c > 0)
{
v.emplace_back(i - 1);
}
if (c + 1
{
v.emplace_back(i + 1);
}
v.emplace_back(i);
}
for (int iMove = 2; iMove
