O tablă de joc cu n linii, numerotate de la 1 la n și m coloane, numerotate de la 1 la m conține n*m celule identice. Celula din colţul din stânga sus se află pe linia 1 şi coloana 1. O celulă poate fi: celulă liberă, celulă în care se află o piatră sau celulă de tip gaură.

Pietrele sunt numerotate cu valori începând de la 1. Numerotarea pietrelor pe tablă se face în ordinea în care sunt

Exemplu

pietre.in

5 4 6 2
1 1
1 2
2 2
3 2
3 3
4 1
3 4
5 3
VSE

pietre.out

5
4
1 1
1 2
2 2
5 1

Explicație

Piatra 1: nu poate efectua săritura V (deoarece ar părăsi tabla de joc), nici săritura S (pentru că nu există nicio piatră în celula vecină aflată în direcția sud), efectuează săritura E, deci configurația finală a tabelei va conține 5 pietre.
Pentru piatra 2 se obține configurația finală identică celei inițiale, deoarece nu poate efectua nicio săritură.
Piatra 3 poate efectua doar săritura S. Configurația finală conține 5 pietre.
Piatra 4 nu poate efectua nicio săritură. Configurația finală conține 6 pietre.
Piatra 5 poate efectua săriturile: V și dispare piatra 4, S și dispare piatra și nu poate efectua săritura E. Configurația finală are 4 pietre.
Piatra 6 nu poate efectua nicio săritură. Configurația finală conține 6 pietre.

# include <fstream>
using namespace std;

ifstream f("pietre.in");
ofstream g("pietre.out");

int dl[5]={0,-1,0,1,0}, dc[5]={0,0,1,0,-1}, a[102][102], b[102][102],c[102][102],x[10002][2];
int nrp,m,n,i,j,xx,minn,ii,jj,l,cl,k,t,d,piatra,p,q,p1,q1;
char s[256];
int main()
{
 f>>m>>n>>k>>t;
 for (i=1;i<=k;i++)
 { f>>l>>cl;
   a[l][cl]=1;
   x[i][0]=l;
   x[i][1]=cl;
 }
 for (i=1;i<=t;i++)
 { f>>l>>cl;
   a[l][cl]=-1;
 }
 i=0;
 while (f>>s[i])
    i++;
 xx=i;
 for(i=0;i<=m+1;i++)
 {  a[i][0]=-1;
    a[i][n+1]=-1;
 }
 for(j=1;j<=n;j++)
 {
   a[0][j]=-1;
   a[m+1][j]=-1;
 }
 minn=m*n+1;

 for(p=1;p<=k;p++)
    {i=x[p][0];j=x[p][1];
      for (ii=0;ii<=m+1;ii++)
        for(jj=0;jj<=n+1;jj++)
          b[ii][jj]=a[ii][jj];
     for (t=0;t<xx;t++)
    {
        if(s[t]=='N') d=1;
         else
            if (s[t]=='S') d=3;
              else
                if (s[t]=='E') d=2;
                   else
                    d=4;
        if (b[i+dl[d]][j+dc[d]]==1)
            if (i+2*dl[d]>=1 && i+2*dl[d]<=m && j+2*dc[d]>=1 && j+2*dc[d]<=n)
            if (b[i+2*dl[d]][j+2*dc[d]]==0)
          {
           b[i+2*dl[d]][j+2*dc[d]]=1;
           b[i+dl[d]][j+dc[d]]=0;
           b[i][j]=0;
           i=i+2*dl[d];
           j=j+2*dc[d];
          }
    }
      nrp=0;
      for (ii=1;ii<=m;ii++)
       for (jj=1;jj<=n;jj++)
         if (b[ii][jj]==1)
            nrp=nrp+1;
       if (nrp<minn)
              {
               minn=nrp;
               for (p1=1;p1<=m;p1++)
                 for (q1=1;q1<=n;q1++)
                    c[p1][q1]=b[p1][q1];

               piatra=p;
              }
    }
   g<<piatra<<endl<<minn<<endl;
   for (i=1;i<=m;i++)
    for (j=1;j<=n;j++)
     if (c[i][j]==1)
       g<<i<<" "<<j<<endl;
    return 0;
}