Pond Skater

AtCoder

IDabc170_f

Time3000ms

Memory256MB

Difficulty—

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with $H$ east-west rows and $W$ north-south columns. Let $(i,j)$ be the square at the $i$\-th row from the north and $j$\-th column from the west. Some of the squares have a lotus leaf on it and cannot be entered. The square $(i,j)$ has a lotus leaf on it if $c_{ij}$ is `@`, and it does not if $c_{ij}$ is `.`. In one stroke, Snuke can move between $1$ and $K$ squares (inclusive) toward one of the four directions: north, east, south, and west. The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden. Find the minimum number of strokes Snuke takes to travel from the square $(x_1,y_1)$ to $(x_2,y_2)$. If the travel from $(x_1,y_1)$ to $(x_2,y_2)$ is impossible, point out that fact. ## Constraints * $1 \leq H,W,K \leq 10^6$ * $H \times W \leq 10^6$ * $1 \leq x_1,x_2 \leq H$ * $1 \leq y_1,y_2 \leq W$ * $x_1 \neq x_2$ or $y_1 \neq y_2$. * $c_{i,j}$ is `.` or `@`. * $c_{x_1,y_1} =$ `.` * $c_{x_2,y_2} =$ `.` * All numbers in input are integers. ## Input Input is given from Standard Input in the following format: $H$ $W$ $K$ $x_1$ $y_1$ $x_2$ $y_2$ $c_{1,1}c_{1,2}$ $..$ $c_{1,W}$ $c_{2,1}c_{2,2}$ $..$ $c_{2,W}$ $:$ $c_{H,1}c_{H,2}$ $..$ $c_{H,W}$ [samples]

Samples

Input #1

3 5 2
3 2 3 4
.....
.@..@
..@..

Output #1

5

Initially, Snuke is at the square $(3,2)$. He can reach the square $(3, 4)$ by making five strokes as follows:

*   From $(3, 2)$, go west one square to $(3, 1)$.
    
*   From $(3, 1)$, go north two squares to $(1, 1)$.
    
*   From $(1, 1)$, go east two squares to $(1, 3)$.
    
*   From $(1, 3)$, go east one square to $(1, 4)$.
    
*   From $(1, 4)$, go south two squares to $(3, 4)$.

Input #2

1 6 4
1 1 1 6
......

Output #2

Input #3

3 3 1
2 1 2 3
.@.
.@.
.@.

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "Pond Skater",
    "description": {
      "content": "Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with $H$ east-west rows and $W$ north-south columns. Let $(i,j)$ be the square at the $i$\\-th row from the north and $j$\\",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc170_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with $H$ east-west rows and $W$ north-south columns. Let $(i,j)$ be the square at the $i$\\-th row from the north and $j$\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments