Heist

Time limit: 2s Memory limit: 32MB Input: heist.in Output: heist.out

Ștefan și Tudor nu erau hoți obișnuiți. Ei erau genii în informatică și matematică, pasionați de provocări logice și labirinturi criptate. Într-o seară misterioasă, au primit un mesaj anonim:

Banca Centrală din Matrizopolis păstrează în seiful său cel mai valoros artefact digital: Cheia Primă, o secvență binară ce poate decripta orice algoritm. Seiful este protejat de un sistem de securitate sub formă de... matrice.

Matricea avea dimensiunea N×NN\times N, iar fiecare celulă reprezenta un pas posibil prin bancă. Sistemul avea o particularitate:

  • Dacă valoarea unei celule era un număr prim, însemna că zona respectivă era plină de lasere invizibile – deci necesita efort și timp (cost 1).
  • Dacă nu era prim, zona era sigură – fără riscuri (cost 0).

Pentru a ajunge la artefact, cei doi trebuiau să răspundă mai multor interogări transmise de sistemul bancar:

Care este drumul de efort minim de la celula (i,j)(i,j) la celula (k,l)(k,l)?

Orice pas într-o celulă primă le consuma timp prețios, deci trebuiau să evite cât mai multe astfel de celule. Mișcările erau permise în cele 4 direcții: sus, jos, stânga și dreapta.

Pe măsură ce răspundeau la fiecare întrebare, ușile băncii se deschideau una câte una. Dar sistemul nu ierta greșeli: o alegere neinspirată într-o celulă primă le putea declanșa alarma.

Sarcina ta este să fii creierul din spatele operațiunii și să-i ajuți pe Ștefan și Tudor să:

  • Calculeze drumul optim dintre două puncte din matrice, evitând cât mai multe numere prime.
  • Răspundă la toate interogările sistemului pentru a ajunge la Cheia Primă fără a fi prinși.

Cerință

Dându-se o matrice AA cu NN linii și NN coloane, determinați pentru fiecare interogare drumul de cost minim din celula Ai,jA_{i, j} la celula Ak,lA_{k, l}. Costul unei celule e:

  • 11, dacă valorea celulei e număr prim;
  • 00, altfel.

Date de intrare

Fișierul de intrare heist.in conține:

  • pe prima linie un singur număr natural, NN, cu semnificația din enunț;
  • pe următoarele NN linii câte NN numere naturale, reprezentând numerele asociate zonelor în ordinea corespunzătoare elementelor din matrice, linie cu linie, de sus în jos, și de la stânga la dreapta pe fiecare linie;
  • pe următoarea linie numărul QQ, cu semnificația din enunț;
  • pe următoarele QQ linii câte patru numere naturale, i,j,k,li, j, k, l, cu semnificația din enunț;
    Numerele aflate pe aceeași linie a fişierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire heist.out conține pe QQ linii costul drumului de cost minim între celulele date, câte un singur număr pe linie, în ordinea citirii.

Restricții și precizări

  • 1N901 \leq N \leq 90;
  • 1Q1061 \leq Q \leq 10^{6};
  • 0Ai,j2109,1i,jN0 \leq A_{i, j} \leq 2 \cdot 10^{9}, 1\leq i, j \leq N.
# Punctaj Restricții
1 20 1N10,1Q104,0Ai,j2106,1i,jN1 \leq N \leq 10, 1 \leq Q \leq 10^{4}, 0 \leq A_{i, j} \leq 2 \cdot 10^{6}, 1\leq i, j \leq N
2 25 1N30,1Q104,0Ai,j2107,1i,jN1 \leq N \leq 30, 1 \leq Q \leq 10^{4}, 0 \leq A_{i, j} \leq 2 \cdot 10^{7}, 1\leq i, j \leq N
3 20 1N50,1Q105,0Ai,j2108,1i,jN1 \leq N \leq 50, 1 \leq Q \leq 10^{5}, 0 \leq A_{i, j} \leq 2 \cdot 10^{8}, 1\leq i, j \leq N
4 20 1N60,1Q105,0Ai,j2109,1i,jN1 \leq N \leq 60, 1 \leq Q \leq 10^{5}, 0 \leq A_{i, j} \leq 2 \cdot 10^{9}, 1\leq i, j \leq N
5 5 1N75,1Q106,0Ai,j2109,1i,jN1 \leq N \leq 75, 1 \leq Q \leq 10^{6}, 0 \leq A_{i, j} \leq 2 \cdot 10^{9}, 1\leq i, j \leq N
6 5 1N90,1Q106,0Ai,j2106,1i,jN1 \leq N \leq 90, 1 \leq Q \leq 10^{6}, 0 \leq A_{i, j} \leq 2 \cdot 10^{6}, 1\leq i, j \leq N
7 5 Fără restricții suplimentare

Exemplu

heist.in

3
4 3 6
1 2 7
4 3 9
1
1 1 3 3

heist.out

1

Explicație

Vom merge jos, jos, dreapta, dreapta.

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