题目描述
据说每一个走进Gree哥哥心房的小姑娘都没有能够再走出来……
我们将Gree哥哥的心房抽象成一个n imes mn×m的地图，初始所有点均为空。当小姑娘走入他的心房时(此时小姑娘的位置为 (1,1)(1,1) 点)，他会将kk 个 1 imes 11×1 障碍物放入地图来阻止小姑娘的行动，每个位置最多只能放置一个障碍物（即不能叠加放置）。但由于Gree哥哥被小姑娘的美貌所捕获，并没有一套很好的策略去放置这些障碍物，于是就随机放置这些障碍物。
在Gree随机地把所有障碍物放置好之后，小姑娘要从地图的左上角 (1,1)(1,1) 走到右下角 (n,m)(n,m)。（起点和终点不能放置障碍物）
小姑娘每一步可以往上下左右的任意一个方向移动一个单位，在所有的障碍物放置方案中，小姑娘从左上角走到右下角需要的最少步数是多少？（小姑娘会尽量走最短的路线）
如果没有一个合理的放置方案，或无论怎样放置障碍物小姑娘都无法到达右下角，输出 -1−1.
输入描述
输入包含三个正整数 n,m,kn,m,k。 (1 le n, m, k le 10^{5}1≤n,m,k≤105)
输出描述
输出一个整数表示答案。
样例输入 1
3 3 2
样例输出 1
4
提示
若用 0 表示空地，1 表示此地被放置了障碍物。则其中的一种放置方案为：
0 0 1
1 0 0
0 0 0
在这种情况下，从左上角到右下角的步数为 4。且这种方案是小姐姐需要步数最少的方案。（当然也有其他方案也可以让小姐姐4步就能到达终点）
思路：起点到终点的最短步数为n-1+m-1（即n+m-2）,加上起点和终点两个格子，小姑娘要从起点走到终点共需要n+m-1个格子，所以障碍物最多占据n*m-(n+m-1)个格子 即(n*m+1-(n+m))
注意：n*m都是1e5的范围 会爆int,将变量设置为long long 即可
#include <cstdio> #include <iostream> using namespace std; int main() { long long n,m,k; while(cin >> n >> m>>k){ if(k > n*m-(n+m-1)) cout << "-1" << endl; else cout << (n+m-2) <<endl; } return 0; }