Speedrun

Time limit: 0.2s Memory limit: 16MB Input: speedrun.in Output: speedrun.outPoints by default: 10p

Andrei a primit de la Moș Crăciun o consolă nouă.

Pentru că știe că îi plac jocurile de tip puzzle, tatăl său i-a făcut cadou jocul Labyrinth. Jocul are două nivele ce pot fi descrise astfel:

  • Nivelul 1: Personajul se află într-un labirint cu NN linii și MM coloane și are misiunea de a ajunge dintr-o celulă specificată (L1,C1)(L_1, C_1) într-o altă celulă (L2,C2)(L_2, C_2) fără să treacă prin celulele în care se află monștri. La fiecare pas, personajul se poate deplasa doar în patru direcții: sus, jos, stânga, dreapta.
  • Nivelul 2: Misiunea personajului se păstrează și la acest nivel, însă apare o modificare. Astfel, în unele celule, care nu sunt ocupate de monștri, se găsește câte o cheie. La acest nivel, pentru a-și putea îndeplini misiunea de a se deplasa de la (L1,C1)(L_1, C_1) la (L2,C2)(L_2, C_2), personajul trebuie să treacă prin cel puțin o celulă ce conține o cheie.

Cerință

Cunoscând nivelul pe care îl joacă, determinați timpul minim în care Andrei poate termina misiunea știind că trecerea dintr-o celulă în alta durează o secundă.

Date de intrare

Pe prima linie a fișierului de intrare speedrun.in se vor afla patru numere naturale, date în ordine:

  • CC - nivelul pe care urmează să îl joace Andrei;
  • NN, MM - dimensiunile labirintului, respectiv numărul de linii și coloane;
  • PP - numărul de celule în care se găsesc chei.

Pe următoarea linie, vom găsi patru numere naturale L1L_1, C1C_1, L2L_2, C2C_2 cu semnificația din enunț.

Pe următoarele NN linii ale fișierului, se vor găsi câte MM valori de 00 sau 11 separate prin câte un spațiu cu semnificația următoare:

  • 00 - celula este liberă;
  • 11 - în celulă se găsește un monstru.

Pe următoarele PP linii, se va găsi câte o pereche de valori (X,Y)(X, Y) reprezentând linia și coloana unei celule în care se găsește o cheie.

Date de ieșire

Pe prima linie a fișierului de ieșire speedrun.out se va găsi, indiferent de nivelul jucat, un singur număr natural, reprezentând numărul minim de secunde pentru a finaliza misiunea.

Restricții și precizări

  • 1N,M1 0001 \le N, M \le 1\ 000
  • 00 \le numărul de monștri N×M\le N \times M
  • 0PN×M0 \le P \le N \times M
  • Pentru cerința 1, se garantează P=0P = 0, și pentru cerința 2 vom avea P1P \ge 1.
  • Va exista întotdeauna cel puțin o soluție.
  • Se garantează (L1,C1)(L2,C2)(L_1, C_1) \neq (L_2, C_2).
  • Cheile se vor afla mereu pe celule care nu conțin monștri.
  • Se oferă 1010 puncte din oficiu.

Exemplul 1

speedrun.in

1 6 6 0
1 1 5 6
0 0 1 1 1 1
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 1 0 0
1 1 0 0 0 0
1 1 1 0 1 1

speedrun.out

9

Explicație

Un posibil traseu pentru personaj ce conduce la soluție va trece prin celulele următoare: (L1,C1)(1,1)(L_1, C_1) \Leftrightarrow (1, 1), (1,2)(1, 2), (2,2)(2, 2), (3,2)(3, 2), (4,2)(4, 2), (4,3)(4, 3), (5,3)(5, 3), (5,4)(5, 4), (5,5)(5, 5), (5,6)(L2,C2)(5,6) \Leftrightarrow (L_2, C_2).

Exemplul 2

speedrun.in

2 6 6 1
1 1 5 6
0 0 1 1 1 1
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 1 0 0
1 1 0 0 0 0
1 1 1 0 1 1
4 6 

speedrun.out

11

Explicație

Un posibil traseu pentru personaj ce conduce la soluție va trece prin celulele următoare: (L1,C1)(1,1)(L_1, C_1) \Leftrightarrow (1, 1), (1,2)(1, 2), (2,2)(2, 2), (3,2)(3, 2), (3,3)(3,3), (3,4)(3,4), (2,4)(2,4), (2,5)(2,5), (2,6)(2,6), (3,6)(3,6), (4,6)(4,6), (5,6)(L2,C2)(5,6) \Leftrightarrow (L_2, C_2).

Log in or sign up to be able to send submissions!