Fişierul intrare/ieşire:arrows.in, arrows.outSursăOJI 2014 clasa a 8-a
AutorEmanuela CerchezAdăugată deIsabela_comanComan Isabela Patricia Isabela_coman
Timp execuţie pe test0.5 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Arrows (clasa a 8-a)

"Arrows" este un joc care se joacă pe o tablă dreptunghiulară a cărei suprafaţă este împărţită în NxM celule, aranjate pe N linii şi M coloane. În fiecare celulă se află o săgeată (sus, jos, stânga sau dreapta), ca în figura de mai jos:

Când este la mutare, un jucător poate alege o poziţie de start pe care plasează un jeton, apoi deplasează jetonul la celula învecinată în sensul indicat de săgeată. Deplasarea continuă până când jetonul părăseşte tabla de joc, caz în care jucătorul obţine un punctaj egal cu numărul de celule parcurse de jetonul său.
Există însă poziţii de start denumite favorabile, pentru care jetonul nu va părăsi niciodată tabla de joc. De exemplu, toate poziţiile din figură cu fundal gri sunt favorabile. Jucătorul care alege o poziţie de start favorabilă obţine un punctaj egal cu numărul de celule distincte vizitate înmulţit cu 1000.

Cerinţă

Scrieţi un program care, cunoscând configuraţia tablei de joc, rezolvă una dintre următoarele cerinţe:
1. determină punctajul pe care îl obţine un jucător care plasează jetonul său pe o poziţie de start specificată;
2. determină numărul de celule favorabile de pe tabla de joc;
3. determină punctajul maxim pe care jucătorul îl poate obţine la o mutare, alegând convenabil poziţia de start.

Date de intrare

Fişierul de intrare arrows.in conţine pe prima linie cerinţa care trebuie să fie rezolvată (1, 2 sau 3). Pe a doua linie se află numerele naturale N M, care reprezintă numărul de linii şi respectiv de coloane de pe tabla de joc. Pe următoarele N linii se află câte M numere din mulţimea {1,2,3,4} reprezentând săgeţile aflate în celulele de pe tabla de joc (1 semnificând săgeata la dreapta, 2 săgeata în sus, 3 săgeata la stânga şi 4 săgeata în jos). Pe ultima linie sunt scrise numerele naturale lin col, reprezentând linia şi coloana pe care se află poziţia de start specificată. Valorile scrise pe aceeaşi linie în fişierul de intrare sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire arrows.out va conţine o singură linie pe care va fi scris un număr natural reprezentând răspunsul pentru cerinţa specificată pe prima linie a fişierului de intrare.

Restricţii

  • 1 ≤N, M ≤ 500
  • Liniile sunt numerotate de la 1 la N, iar coloanele de la 1 la M.
  • Punctaj. Pentru teste valorând 20 de puncte cerinţa este 1. Pentru teste valorând 40 de puncte cerinţa este 2. Pentru celelalte teste, valorând de asemenea 40 de puncte, cerinţa este 3.
  • Dimensiunea maximă a sursei 10 KB.

Exemplu

arrows.inarrows.outExplicaţii
1
6 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
5 5
2000
Exemplul corespunde tablei de joc din figură.
Punctajele pentru fiecare poziţie sunt:
1 14000 14000 14000  1
15000 14000 14000 14000  1
16000 14000 14000 14000 14000
15000 14000 14000 14000 14000
1 4000 4000  2 2000
2 4000 4000  1 2000
Cerinţa este 1: punctajul care se obţine plecând din poziţia de start aflată pe linia 5 şi coloana 5 este 2000.
2
6 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
5 5
23
Cerinţa este 2: există 23 de poziţii favorabile.
3
6 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
5 5
16000
Cerinţa este 3: punctajul maxim se poate obţine plasând jetonul în punctul de start de pe linia 3 şi coloana 1.
Trebuie sa te autentifici pentru a trimite solutii. Click aici