做汽车网站,深圳建设集团招标,广州开发区投资集团有限公司招聘,门户模板1
给定一个 R 行C 列的二维数组 M 表示一张棋盘地图 数组元素取值为 0或者 1,1 表示对于的地图格子里有一颗炸弹,如下示例
游戏规则如下: 1)当点击格子时,如果格子有炸弹(数值1),则炸弹发生爆炸 2)当一个格子中的炸弹爆炸时,其周围的8个格子(上,下,左,右,左上,左下,右上,右下…1
给定一个 R 行C 列的二维数组 M 表示一张棋盘地图 数组元素取值为 0或者 1,1 表示对于的地图格子里有一颗炸弹,如下示例
游戏规则如下: 1)当点击格子时,如果格子有炸弹(数值1),则炸弹发生爆炸 2)当一个格子中的炸弹爆炸时,其周围的8个格子(上,下,左,右,左上,左下,右上,右下)里如果有炸弹则会发生连锁反应一起爆炸 请问:最少需要点击几次可以清理完地图中所有炸弹?(如上图示例需要3次) 示例输入
[[1, 0, 0, 1],[0, 1, 1, 0],[0, 0, 1, 0],[1, 0, 0, 1]]示例输出
2解答
DFS 对于棋盘上的每一个格子如果它包含炸弹即值为1我们就执行一次DFS以模拟炸弹爆炸导致的连锁反应。DFS的过程中我们会标记所有被连锁反应引父的炸弹以确保每个炸弹只被计算一次。 void dfs(vectorvectorint M, int r, int c) {int R M.size();int C M[0].size();// 如果越界或者当前格子不含炸弹则停止当前方向的搜索if (r 0 || r R || c 0 || c C || M[r][c] ! 1) {return;}// 标记当前格子的炸弹已经爆炸或者说已经处理过以避免重复计算M[r][c] 0;// 搜索当前格子周围的8个方向dfs(M, r-1, c); // 上dfs(M, r1, c); // 下dfs(M, r, c-1); // 左dfs(M, r, c1); // 右dfs(M, r-1, c-1); // 左上dfs(M, r-1, c1); // 右上dfs(M, r1, c-1); // 左下dfs(M, r1, c1); // 右下}int minClicks(vectorvectorint M) {int R M.size();int C M[0].size();int clicks 0;for (int r 0; r R; r) {for (int c 0; c C; c) {if (M[r][c] 1) {// 对于每一个未被爆炸的炸弹执行一次DFSdfs(M, r, c);clicks; // 每次DFS都代表了一次点击}}}return clicks;}2
1)假如有A,B两个任务,如果要完成任务B必须先完成任务A,我们称A为B的 前置 任务, B为A的 后置 任务. 2)一个任务可以有最多2个(0个,1个,或者2个)的后置任务 3)后置任务不会再有后置任务 4)所有任务只能完成一次 问题:在给定玩家当前活力值 V,和当前游戏可做任务列表T的情况下,求通玩家过完成任务能获取的最高奖励. 输入描述 int V;玩家当前活力值vectorvectorT;当前游戏可做任务列表列表中的每一项为一个长度为 3的 vector表示一个任务的 3 个属性:[消耗活力值,任务奖励,其依赖的前置任务序号(序号-1表示无依赖前置任务)] 如: 0:[20,604]// 任务0,需要活力值20,完成任务可获得奖励60依赖任务4 1:[20,604]// 任务1,需要活力值20,完成任务可获得奖励60依赖任务4 2:[10,30-1]// 任务2,需要活力值10,完成任务可获得奖励30无依赖任务 3:[10,20-1]// 任务3,需要活力值20,完成任务可获得奖励60无依赖任务 4:[10,10-1]// 任务4,需要活力值20,完成任务可获得奖励60无依赖任务 示例输入
50,[[20,60,4],[20,60,4],[10,30,-1],[10,20,-1],[10,10,-1]]示例输出
130解答存疑
1、贪心-》寻找可能最优解
// 自定义排序函数优先比较奖励其次比较消耗活力值
bool compare(const vectorint a, const vectorint b) {double ratioA (double)a[1] / a[0];double ratioB (double)b[1] / b[0];return ratioA ratioB;
}int getMaxReward(int V, vectorvectorint T) {vectorbool completed(T.size(), false); // 标记任务是否完成int totalReward 0;// 分两轮处理任务第一轮处理无依赖任务第二轮处理有依赖的任务for (int round 0; round 2; round) {// 根据奖励/消耗比进行排序sort(T.begin(), T.end(), compare);for (int i 0; i T.size(); i) {if (completed[i]) continue; // 跳过已完成的任务int cost T[i][0], reward T[i][1], dependency T[i][2];// 检查是否可以执行当前任务if (V cost (dependency -1 || completed[dependency])) {V - cost; // 消耗活力值totalReward reward; // 增加奖励completed[i] true; // 标记任务为已完成}}}return totalReward;
}2、回溯搜索比较所有情况获得确定的最优解
int calculateMaxReward(const int V, vectorvectorint tasks, vectorbool visited, int currentReward, int index, vectorint dependencyCounter) {if (index tasks.size()) {// 所有任务都尝试过返回当前奖励return currentReward;}// 直接跳过当前任务看下一个任务的选择会如何int maxReward calculateMaxReward(V, tasks, visited, currentReward, index 1, dependencyCounter);// 尝试选择当前任务if (!visited[index] V tasks[index][0] (tasks[index][2] -1 || (tasks[index][2] ! -1 visited[tasks[index][2]]))) {visited[index] true; // 标记为已访问// 更新依赖计数器对于任何依赖此任务的任务减少它们的依赖计数for (int i 0; i tasks.size(); i) {if (tasks[i][2] index) {dependencyCounter[i]--;}}// 选择当前任务并递归尝试后续任务maxReward max(maxReward, calculateMaxReward(V - tasks[index][0], tasks, visited, currentReward tasks[index][1], index 1, dependencyCounter));// 回溯撤销当前选择visited[index] false;for (int i 0; i tasks.size(); i) {if (tasks[i][2] index) {dependencyCounter[i];}}}return maxReward;
}int getMaxReward(int V, vectorvectorint tasks) {vectorbool visited(tasks.size(), false); // 记录任务是否已完成vectorint dependencyCounter(tasks.size(), 0); // 记录每个任务有依赖的次数for (auto task : tasks) {if (task[2] ! -1) {dependencyCounter[task[2]];}}return calculateMaxReward(V, tasks, visited, 0, 0, dependencyCounter);
}
3
能量站初始能量为0。 初始存在12个充能电池每个电池具有各自的电能X(X为整数,4 X15) 每次给能量站注入能量需使用3个电池同时要求3个电池的电能总和为4的整数倍 每天最多给能量站注入一次能量,单次注入的能量为(3个电池电能总和/4)的平方 电池使用后电能耗尽,同时不可再次使用 从今天开始每天使用电池给能量站注入能量允许当天不使用任何电池给能量站注入能量当天未使用的电池,若电能大于4则电能将减少1请输出在所有电池电能耗尽的情况下给能量站注入的最大的能量总和 输入描述 输入12个整数空格隔开表示12个电池各自的初始电能 4 X 15 输出描述 给能量站注入的能量总和的最大值 示例输入
12 10 9 15 15 14 6 5 4 7 7 7示例输出
188解答(暂时不会
动态规划组合遍历二进制方法
