#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 50
#define MAXH 10
#define MAXT 100
#define MAXP 10

typedef struct { int x, y; } xy;
typedef char stav[MAXN][MAXN][MAXH+1];
int M, N, H, T;
xy S[MAXH+1];
int NP[MAXH+1];
xy P[MAXH+1][MAXP];

void start(stav s)
{
  for (int z=0; z<=H; z++)
    for (int x=0; x<M; x++)
      for (int y=0; y<N; y++)
	s[x][y][z] = (x == S[z].x && y == S[z].y);
}

int vpred(stav a, stav b, xy *out)
{
  for (int z=0; z<=H; z++)
    for (int x=0; x<M; x++)
      for (int y=0; y<N; y++)
	b[x][y][z] = 0;
  for (int z=0; z<=H; z++)
    for (int x=0; x<M; x++)
      for (int y=0; y<N; y++)
	if (a[x][y][z])
	  for (int p=0; p<NP[z]; p++)
	    {
	      int xx = x + P[z][p].x;
	      int yy = y + P[z][p].y;
	      if (xx >= 0 && xx < M && yy >= 0 && yy < N)
		b[xx][yy][z] = 1;
	      else if (!z && out)
		{
		  out->x = xx, out->y = yy;
		  return 1;
		}
	    }
  for (int x=0; x<M; x++)
    for (int y=0; y<N; y++)
      for (int z=1; z<=H; z++)
	if (b[x][y][z])
	  b[x][y][0] = 0;
  return 0;
}

int najdi_prase(stav s, xy *out)
{
  for (out->x=0; out->x<M; out->x++)
    for (out->y=0; out->y<N; out->y++)
      if (s[out->x][out->y][0])
	return 1;
  return 0;
}

void vzad(stav a, xy kam, xy *od)
{
  for (int x=0; x<M; x++)
    for (int y=0; y<N; y++)
      if (a[x][y][0])
	for (int p=0; p<NP[0]; p++)
	  if (x + P[0][p].x == kam.x && y + P[0][p].y == kam.y)
	    {
	      od->x = x, od->y = y;
	      return;
	    }
  puts("Pomooc!"); exit(1);
}

void zrave(void)
{
  stav S[MAXT+1];
  xy cesta[MAXT+1];
  start(S[0]);
  int t = 1;
  while (t <= T && !vpred(S[t-1], S[t], &cesta[t]))
    t++;
  if (t <= T)
    puts("Prasatko uteklo:");
  else if (najdi_prase(S[T], &cesta[T]))
    {
      puts("Prasatko behalo do setmeni:");
      t = T;
    }
  else
    {
      puts("Hrosi hoduji.");
      return;
    }
  for (int s=t; s > 0; s--)
    vzad(S[s-1], cesta[s], &cesta[s-1]);
  for (int s=0; s <= t; s++)
    printf("(%d,%d)\n", cesta[s].x, cesta[s].y);
}

void cesticka(xy *cesta, int t, int s, stav St)
{
  if (t == s)
    return;
  if (t+1 == s)
    {
      vzad(St, cesta[s], &cesta[t]);
      return;
    }
  stav S[2];
  memcpy(S[t%2], St, sizeof(stav));
  int u = t;
  while (u < (s+t)/2)
    {
      vpred(S[u%2], S[(u+1)%2], NULL);
      u++;
    }
  cesticka(cesta, u, s, S[u%2]);
  cesticka(cesta, t, u, St);
}

void nasel(int t, xy pos)
{
  stav S0;
  xy cesta[t+1];
  start(S0);
  cesta[t] = pos;
  cesticka(cesta, 0, t, S0);
  for (int s=0; s<=t; s++)
    printf("(%d,%d)\n", cesta[s].x, cesta[s].y);
}

void usporne(void)
{
  stav S[2];
  xy pos;
  start(S[0]);
  for (int t=1; t<=T; t++)
    if (vpred(S[(t-1)%2], S[t%2], &pos))
      {
	puts("Prasatko uteklo:");
	nasel(t, pos);
	return;
      }
  if (najdi_prase(S[T%2], &pos))
    {
      puts("Prasatko behalo do setmeni:");
      nasel(T, pos);
    }
  else
    puts("Hrosi hoduji.");
}

int main(void)
{
  M=4; N=4; H=2; T=5;
  S[0].x = 2; S[0].y = 2;
  S[1].x = 3; S[1].y = 2;
  S[2].x = 2; S[2].y = 3;
  NP[0] = 1; P[0][0].x = -1; P[0][0].y = 0;
  NP[1] = 1; P[1][0].x = -1; P[1][0].y = 0;
  NP[2] = 2; P[2][0].x = 0; P[2][0].y = -1; P[2][1].x = -1; P[2][1].y = 0;
  //zrave();
  usporne();
  return 0;
}