经典算法 青蛙跳杯子

青蛙跳杯子

题目描述

桌子上有n行m列的杯子，每个杯子与相邻杯子之间的距离为1，已知青蛙的跳跃半径为d，青蛙现在在第一行第一列的杯子上，它跳到最后一行最后一列的杯子上，最少需要跳几次？

输入描述

输入只有一行，分别为整数n, m和实数d。

输出描述

直接输出青蛙跳的最小步数。

输入示例

3 4 1.5

输出示例

3

样例解释

，表示青蛙的一条可能路径，只要再跳3步就行。

，。。。
。，。。
。。，，

c++代码(暴力bfs) 大约O(m * n * d)

#include<bits/stdc++.h>using namespace std;int n, m, ans = INT_MAX;
double d;
vector<vector<int>> dp;class node{
public:int i, j, recoder;
};void bfs() {dp[0][0] = 0;queue<node> q;node k, w;k.i = 0, k.j = 0;q.push(k);while(!q.empty()) {k = q.front(), q.pop();for (int i = 0; i <= (int)(d) && k.i + i < n; i++) {for (int j = 0; j <= (int)(d) && k.j + j < m && i * i + j * j <= d * d; j++) {if (dp[k.i][k.j] + 1 < dp[k.i + i][k.j + j]) {w.i = k.i + i, w.j = k.j + j;dp[w.i][w.j] = dp[k.i][k.j] + 1;q.push(w);}}}}
}int main() {cin >> n >> m >> d;dp = vector<vector<int>>(n, vector<int>(m, INT_MAX));bfs();cout << dp[n - 1][m - 1];return 0;
}

c++代码(贪心法) 大约等于O(min(m, n) * d)

#include<bits/stdc++.h>using namespace std;int n, m, x, y, cont = 0, a, b;
double d, z;int main() {cin >> n >> m >> d;a = 0, b = 0;while(a != n - 1 || b != m - 1) {z = DBL_MAX;for (int i = 0; i <= (int)(d) && a + i < n; i++) {for (int j = 0; j <= (int)(d) && b + j < m && i * i + j * j <= d * d; j++) {int delta = (n - 1 - (a + i)) * (n - 1 - (a + i)) + (m - 1 - (b + j)) * (m - 1 - (b + j));if (delta < z) z = delta, x = a + i, y = b + j;}}a = x, b = y;cont++;}cout << cont;return 0;
}//by wqs

题目解析

暴力法

暴力法的思路很简单，我们定义dp[i][j]表示从(0, 0)到(i, j)最少需要多少步
从队列取出dp[i][j]
遍历dp[i ~ i + int(d)][j ~ j + int[d]]如果两点距离小于d则更新
dp[i ~ i + int(d)][j ~ j + int[d]] = min(dp[i ~ i + int(d)][j ~ j + int[d]], dp[i][j] + 1);
然后把dp[i ~ i + int(d)][j ~ j + int[d]]加入队列，
循环这个步骤就行。

贪心法

贪心法的思路是我们没必要将所有状态加入队列。
我们只需要把与终点直线距离最小的那个点加入就行了。
怎么证明我不会，自己去搜搜吧。
事实上，有一种情况是有2个点同时距离终点最小。
因为这些坐标都是整数，所以这两个状态是对称的你只要选择其中一个就好了。
也因为这些坐标都是整数，实际上不可能会出现3个点或者更多点了。
因为每次只加入一个点，所以干脆可以把队列改成循环了。循环末尾改变下状态就行。