Rezolvare completă PbInfo #1049 Arrows

“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ța

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 și precizări

  • 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.

Exemplul 1

arrows.in

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

arrows.out

2000

Explicație

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.

Exemplul 2

arrows.in

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

arrows.out

23

Explicație

Cerinţa este 2: există 23 de poziţii favorabile.

Exemplul 3

arrows.in

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

arrows.out

16000

Explicație

Cerinţa este 3: punctajul maxim se poate obţine plasând jetonul în punctul de start de pe linia 3 şi coloana 1.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Arrows:

//Emanuela Cerchez - 100 puncte
#include <fstream>
#include <cassert>
#define NMAX 502

using namespace std;

int n, m, xs, ys, nr_fav, pct_max, cerinta;
char a[NMAX][NMAX];
int pct[NMAX][NMAX];
int dl[5]={0,0,-1,0,1};
int dc[5]={0,1,0,-1,0};

ifstream fin("arrows.in");
ofstream fout("arrows.out");

void citire();
int goxy(int, int);

int main()
{int i, j;
 citire();
 for (i=1; i<=n; i++)
      for (j=1; j<=m; j++)
          if (!pct[i][j])
             goxy(i,j);

if (cerinta==1) {
 if (pct[xs][ys]<0) fout<<-pct[xs][ys]<<'\n';
    else fout<<1000*pct[xs][ys]<<'\n';
}
else
{
 for (i=1; i<=n; i++)
      for (j=1; j<=m; j++)
           if (pct[i][j]>0)
                {
                    nr_fav++;
                    if (pct_max<1000*pct[i][j]) pct_max=1000*pct[i][j];
                }
                else
                {
                    if (pct_max<-pct[i][j]) pct_max=-pct[i][j];
                }
 if (cerinta==2)    
    fout<<nr_fav<<'\n';
    else 
    fout<<pct_max<<'\n';
} 
   fout.close();
   return 0;
}

void citire()
{int i, j, x;
 fin>>cerinta>>n>>m;
 assert(1<= cerinta && cerinta <=3);
 assert(0<n && n<501);
 assert(0<m && m<501);
 for (i=1; i<=n; i++)
     for (j=1; j<=m; j++)
        {
            assert(fin>>x);
            a[i][j]=x;
            assert(x>0 && x<5);
        }
  fin>>xs>>ys;
  assert(0<xs && xs<=n);
  assert(0<ys && ys<=m);
  assert(!(fin>>i));
}

int goxy(int x, int y)
{
int sum=0, dir, cx=x, cy=y, s;
while (a[x][y] && !pct[x][y])
       {pct[x][y]=1; sum++;
        dir=a[x][y];
        x+=dl[dir]; y+=dc[dir];
        }

//completarea punctajelor in pct
if (!a[x][y] || pct[x][y]<0) //pozitie nefavorabila
   {sum-=pct[x][y]; x=cx, y=cy; s=-sum;
    while (pct[x][y]==1)
       {pct[x][y]=s; s++;
        dir=a[x][y];
        x+=dl[dir]; y+=dc[dir];
       }
    return -sum; //pozitie nefavorabila
   }

if (pct[x][y]==1) //pozitie favorabila de pe acelasi traseu
   {
    //se formeaza un circuit care contine pozitia x,y
    //toate punctele de pe circuit se marcheaza cu acelasi punctaj
    s=sum;
    while (cx!=x || cy!=y)
          {
            pct[cx][cy]=s; s--;
            dir=a[cx][cy];
            cx+=dl[dir]; cy+=dc[dir];
          }
    //punctele de pe circuit le marchez cu s
    while (pct[x][y]==1)
          {pct[x][y]=s;
           dir=a[x][y];
           x+=dl[dir];  y+=dc[dir];
          }
   return sum;
   }
//pozitie favorabila care conduce catre un circuit
 s=sum+pct[x][y];
 while (cx!=x || cy!=y)
       {
        pct[cx][cy]=s; s--;
        dir=a[cx][cy];
        cx+=dl[dir]; cy+=dc[dir];
        }
return sum+pct[x][y];
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1049 Arrows

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1049 Arrows de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!