Comet OJ 夏季欢乐赛 Gree的心房

题目描述

据说每一个走进Gree哥哥心房的小姑娘都没有能够再走出来……

我们将Gree哥哥的心房抽象成一个n \times mn×m的地图，初始所有点均为空。当小姑娘走入他的心房时(此时小姑娘的位置为 (1,1)(1,1) 点)，他会将kk 个 1 \times 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

提示

若用 0 表示空地，1表示此地被放置了障碍物。则其中的一种放置方案为：

0 0 1

1 0 0

0 0 0

在这种情况下，从左上角到右下角的步数为 4。且这种方案是小姐姐需要步数最少的方案。（当然也有其他方案也可以让小姐姐4步就能到达终点）

是这样，我们发现，如果从左上跑到右下，在最理想情况下，只需要跑n+m-2步（减去的2是起点和终点）。

题目没有给怎么放，只是给了障碍物的个数，那么我们完全可以默认把障碍物按照最理想的方案来放。

然后我们只需要判断一下，k的个数是否足够把这条最优路线堵死。

是的话就没商量输出-1.

不是的话就直接输出n+m-2。

最后我们发现这道题水的要命。

然后得出AC代码，不开long long 会WA一个点。

#include<cstdio>

using namespace std;

typedef long long ll;

ll n,m,k;

int main()

{

	scanf("%lld%lld%lld",&n,&m,&k);

	if(k>(n-1)*(m-1))

	{

		printf("-1");

		return 0;

	}

	else

	{

		printf("%d",n+m-2);

		return 0;

	}

}

巴特西

Comet OJ 夏季欢乐赛 Gree的心房

Comet OJ 夏季欢乐赛 Gree的心房

最新文章

热门文章