Имя: Пароль: Зарегистрироваться Восстановить пароль
08/09/2024 12:19:43

# Рабочее место участника

## Задачи

980. Robot

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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

7


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

10


Sample Input 3

2 2 0
0 1
1 0


Sample Output 3

-1

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