codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1721B.md (2101B)


      1 Source: https://codeforces.com/problemset/problem/1721/B
      2 
      3 B. Deadly Laser
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The robot is placed in the top left corner of a grid, consisting of $n$ rows and $m$ columns, in a cell $(1, 1)$.
     22 
     23 In one step, it can move into a cell, adjacent by a side to the current one:
     24 
     25 * $(x, y) \rightarrow (x, y + 1)$;
     26 * $(x, y) \rightarrow (x + 1, y)$;
     27 * $(x, y) \rightarrow (x, y - 1)$;
     28 * $(x, y) \rightarrow (x - 1, y)$.
     29 
     30 The robot can't move outside the grid.
     31 
     32 The cell $(s_x, s_y)$ contains a deadly laser. If the robot comes into some cell that has distance less than or equal to $d$ to the laser, it gets evaporated. The distance between two cells $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.
     33 
     34 Print the smallest number of steps that the robot can take to reach the cell $(n, m)$ without getting evaporated or moving outside the grid. If it's not possible to reach the cell $(n, m)$, print -1.
     35 
     36 The laser is neither in the starting cell, nor in the ending cell. The starting cell always has distance greater than $d$ to the laser.
     37 
     38 Input
     39 
     40 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     41 
     42 The only line of each testcase contains five integers $n, m, s_x, s_y, d$ ($2 \le n, m \le 1000$; $1 \le s_x \le n$; $1 \le s_y \le m$; $0 \le d \le n + m$) — the size of the grid, the cell that contains the laser and the evaporating distance of the laser.
     43 
     44 The laser is neither in the starting cell, nor in the ending cell ($(s_x, s_y) \neq (1, 1)$ and $(s_x, s_y) \neq (n, m)$). The starting cell $(1, 1)$ always has distance greater than $d$ to the laser ($|s_x - 1| + |s_y - 1| \gt d$).
     45 
     46 Output
     47 
     48 For each testcase, print a single integer. If it's possible to reach the cell $(n, m)$ from $(1, 1)$ without getting evaporated or moving outside the grid, then print the smallest amount of steps it can take the robot to reach it. Otherwise, print -1.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 3
     56 
     57 2 3 1 3 0
     58 
     59 2 3 1 3 1
     60 
     61 5 5 3 4 1
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 3
     68 -1
     69 8
     70 ```