CF1721B Deadly Laser

标签：sy sx Laser CF1721B int Deadly right 辐射 边界

题链：cf luogu

分类讨论？

Description

给一张 \(n\times m\) 的地图，有一个点 \(\left(sx,sy\right)\) 有辐射，辐射半径为 \(d\)，问能否从 \(\left(1,1\right)\) 走到 \(\left(n,m\right)\)，如果能走最少几步。

Analysis

我们把辐射点记作点 \(A\)。

倘若 \(A\) 点能够阻断从左上角到右下角的路径，共有 \(4\) 种可能情况：

1. 左上角阻断，即从 \(A\) 点可以辐射到上边界和左边界；
2. 右下角阻断，即从 \(A\) 点可以辐射到下边界和右边界；
3. 横断，即从 \(A\) 点可以辐射到左边界和右边界；
4. 纵断，即从 \(A\) 点可以辐射到上边界和左边界。

这四种情况都无合法路径，即输出 -1。

如果有合法路径，因为只有 \(1\) 个辐射点，向左或向上走都是浪费的。因此最小步骤一定是向右向下走，易得最小步数为 \(n + m - 2\)。

Code

#include <stdio.h>
int n, m, sx, sy, d;
int main(void) {
    int t; for (scanf("%d", &t); t--; ) {
        scanf("%d %d %d %d %d", &n, &m, &sx, &sy, &d);
        if (sx - d <= 1 && sy - d <= 1 ||
			sx + d >= n && sy + d >= m ||
			sx - d <= 1 && sx + d >= n ||
			sy - d <= 1 && sy + d >= m) puts("-1"); //四种不合法情况
        else printf("%d\n", n + m - 2); //直接向右向下走
    }
    return 0;
}

The end. Thanks.

（小手点点

标签：sy,sx,Laser,CF1721B,int,Deadly,right,辐射,边界
From： https://www.cnblogs.com/dry-ice/p/cf1712b.html