Подразделы

Другие разделы

Дата и время

09/04/2025 13:48:52

Авторизация

Лето 6

A. Метрополитен B. Очень легкая задача C. Шахматная доска D. Интересный треугольник E. Galaxy F. Robot G. Schedule H. Ancestor I. Grid J. Hosting K. BitSort

F. Robot

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Robot has to patrol around a rectangular area which is in a form of

$m\ times\ n$ grid (

$m$ rows and

$n$ columns). The rows are labeled from 1 to

$m$ . The columns are labeled from 1 to

$n$ . A cell

$(i,\ j)$ denotes the cell in row

$i$ and column

$j$ in the grid. At each step, the robot can only move from one cell to an adjacent cell, i.e. from

$(x,\ y)$ to

$(x+1,\ y)$ ,

$(x,\ y+1)$ ,

$(x-1,\ y)$ or

$(x,\ y-1)$ . Some of the cells in the grid contain obstacles. In order to move to a cell containing obstacle, robot has to switch to turbo mode. Therefore, the robot cannot move continuously to more than

$k$ cells containing obstacles.

Your task is to write a program to find the shortest path (with the minimum number of cells) from cell

$(1,\ 1)$ to cell

$(m,\ n)$ . It is assumed that both the cells do not contain obstacles.

Input

The first line contains three positive integers

$m$ ,

$n$ and

$k$ (

$1\ ≤\ m,\ n\ ≤\ 100$ ,

$0\ ≤\ k\ ≤\ 100$ ). The

$i$ -th line of the next

$m$ lines contains

$n$ integer

$a_{ij}$ separated by space (

$i\ =\ 1,\ 2,\ …,\ m$ ;

$j\ =\ 1,\ 2,\ …,\ n$ ). The value of

$a_{ij}$ is 1 if there is an obstacle on the cell

$(i,\ j)$ , and is 0 otherwise.

Output

If there exists a way for the robot to reach the cell

$(m,\ n)$ , write the number of moves the robot has to make;

$-1$ otherwise.

Sample Input 1

2 5 0
0 1 0 0 0
0 0 0 1 0

Sample Output 1

Sample Input 2

4 6 1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0

Sample Output 2

Sample Input 3

2 2 0
0 1
1 0

Sample Output 3

-1

Источник: РГУ им. И.Канта, осенний командный турнир, 2007