Cei care au văzut filmul Nemuritorul, ştiu că fraza cu care nemuritorii încep lupta este “Nu poate să rămână decât unul singur”. Să încercăm să simulăm povestea nemuritorilor.

Într-o zonă dreptunghiulară formată din n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m) se află maxim n•m-1 nemuritori. Doi nemuritori vecini se “luptă” între ei şi cel care pierde lupta este eliminat. “Lupta” constă în săritura unuia dintre nemuritori peste celălalt, dacă această săritură se poate face. Săritura se poate face pe orizontală sau verticală şi nemuritorul peste care s-a sărit dispare. Prin vecin al nemuritorului din poziţia (i,j) înţelegem un nemuritor din una dintre poziţiile (i-1,j), (i+1,j), (i,j-1), (i,j+1). Deci, după luptă nemuritorul din câmpul (i,j) se va găsi în una dintre poziţiile: (i-2,j), (i+2,j), (i,j-2) sau (i,j+2), dacă această poziţie este liberă şi este în interiorul zonei.

Cerinţă

Se cere să se determine o succesiune a luptelor ce pot fi purtate, astfel încât la final să rămână un singur nemuritor.

Date de intrare

Fișierul de intrare immortal.in conține pe prima linie trei valori naturale n m I, separate prin câte un spaţiu, reprezentând numărul de linii, numărul de coloane ale zonei descrise şi respectiv numărul de nemuritori existenţi iniţial. Următoarele I linii conţin fiecare câte două numere naturale x y separate printr-un spaţiu, reprezentând poziţiile unde se găsesc iniţial cei I nemuritori (linia şi coloana).

Date de ieșire

Fișierul de ieșire immortal.out va conține I-1 linii, fiecare linie descriind o “luptă”. Luptele vor fi scrise în ordinea în care au avut loc. O linie va conţine 4 numere naturale care indică: primele două poziţia de pe care pleacă un nemuritor la “luptă”, ultimele două poziţia pe care acesta ajunge după “luptă”. Pentru ca “lupta” să fie corectă, în poziţia peste care nemuritorul “sare” trebuie să existe un nemuritor care va “muri”. O poziţie va fi specificată prin indicele de linie urmat de indicele de coloană. Valorile scrise pe aceeaşi linie vor fi separate prin spaţii.

Restricții și precizări

1 < n, m ≤ 20
1 < I ≤ min{15, n*m-1}
Pentru datele de test există întotdeauna soluţie.

Exemplu

immortal.in

immortal.out

3 3 3 1
3 1 1 1
1 1 1 3

Explicație

  1   2   3   4
 =================    (3,3) --> (3,1)  dispare (3,2)
1|   | * |   |   |    (3,1) --> (1,1)  dispare (2,1)
 |---------------|    (1,1) --> (1,3)  dispare (1,2)
2| * |   |   |   |
 |---------------|
3|   | * | * |   |
 =================

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 Immortal:

//Emanuela Cerchez
//timp maxim: 0.17
#include <stdio.h>
#define InFile  "immortal.in"
#define OutFile "immortal.out"
#define NMax 54
#define LgMax NMax * NMax

int T[NMax][NMax];
int n, m, nr;
struct Poz   {int x, y;}        P[LgMax];
struct Lupta {struct Poz v, m;} sol[LgMax];

int ok=0;
int mort[LgMax];
int dx[]={-1, 0, 1,  0};
int dy[]={ 0, 1, 0, -1};

void citire(void);
void bkt(int);
void afisare(void);

int main()
{
citire();
bkt(0);
return 0;
}


void citire()
{
int i, j, x, y, k=0;
FILE * fin=fopen(InFile,"r");
fscanf(fin,"%d %d %d", &n, &m, &nr);
for (i=1; i<=nr; i++)
    {fscanf(fin,"%d %d", &x, &y);
     T[x+1][y+1]=i;}
for (i=2; i<=n+1; i++)
    for (j=2; j<=m+1; j++)
        if (T[i][j])
           {P[++k].x=i; P[k].y=j; T[i][j]=k;}
for (i=0; i<n+4; i++) T[i][0]=T[i][1]=T[i][m+3]=T[i][m+2]=-1;
for (i=0; i<m+4; i++) T[0][i]=T[1][i]=T[n+2][i]=T[n+3][i]=-1;
}

void bkt(int k)
//s-au desfasurat k lupte sol[0], ..., sol[k-1]
{
int i, d, x, y, moare;
if (!ok)
   if (k==nr-1)
      {ok=1; afisare();}
      else
      for (i=1; i<=nr; i++)
          if (!mort[i])
             {
              //poate sari i?
              x=P[i].x; y=P[i].y;
              for (d=0; d<4; d++)
                 if (T[x+dx[d]][y+dy[d]]>0 && T[x+2*dx[d]][y+2*dy[d]]==0)
                     {
                      //un vecin peste care poate sari
                      moare=T[x+dx[d]][y+dy[d]];
                      sol[k].m.x=x+2*dx[d]; sol[k].m.y=y+2*dy[d];
                      sol[k].v.x=x; sol[k].v.y=y;
                      P[i].x=x+2*dx[d]; P[i].y=y+2*dy[d];
                      T[x][y]=0; T[x+2*dx[d]][y+2*dy[d]]=i;
                      mort[T[x+dx[d]][y+dy[d]]]=1;
                      T[x+dx[d]][y+dy[d]]=0;

                      bkt(k+1);

                      P[i].x=x; P[i].y=y;
                      T[x][y]=i; T[x+2*dx[d]][y+2*dy[d]]=0;
                      T[x+dx[d]][y+dy[d]]=moare;
                      mort[T[x+dx[d]][y+dy[d]]]=0;

                     }
             }
}

void afisare()
{
int i;
FILE * fout=fopen(OutFile,"w");
for (i=0; i<nr-1; i++)
    fprintf(fout,"%d %d %d %d
",sol[i].v.x-1,sol[i].v.y-1,sol[i].m.x-1,sol[i].m.y-1);
fclose(fout);
}

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 #1094 Immortal

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1094 Immortal 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!

Rezolvare completă PbInfo #1094 Immortal