MisjonarzeLudozercyGT

class MisjonarzeLudozercyGT
{
  final static int MAX_DLUGOSC_DROGI = 15; // max długość drogi + 1
  static Stan[] droga = new Stan[MAX_DLUGOSC_DROGI];
  static Stan[] minDroga = new Stan[MAX_DLUGOSC_DROGI];
  static int minDlugoscDrogi = MAX_DLUGOSC_DROGI;

  public static void main(String[] args)
  {
    przewiez(false,0,0,0);
    for (int i = 0; i < minDlugoscDrogi; i++) minDroga[i].wypiszStan();
    System.out.println();
  }

  static void przewiez(boolean prawa, int m, int l, int i)
  {
    if (m != 0 && m != l && m != 3) return; // gdy nieprawidłowy stan

    if (i+1 == minDlugoscDrogi) return; // i+1 -- długość drogi

    droga[i] = new Stan(prawa,m,l);

    if (m == 3 && l == 3)
    {
      if (minDlugoscDrogi > i+1)
      {
        minDlugoscDrogi = i+1;
        for (int j = 0; j < minDlugoscDrogi; j++) minDroga[j] = droga[j];
      }
    }
    else
    {
      if (!prawa && m < 3)          // przepłynięcie misjonarza na prawy brzeg
        przewiez(!prawa,m+1,l,i+1);
      if (prawa && m > 0)           // przepłynięcie misjonarza na lewy brzeg
        przewiez(!prawa,m-1,l,i+1);
      if (!prawa && l < 3)          // przepłynięcie ludożercy na prawy brzeg
        przewiez(!prawa,m,l+1,i+1);
      if (prawa && l > 0)           // przepłynięcie ludożercy na lewy brzeg
        przewiez(!prawa,m,l-1,i+1);
      if (!prawa && m < 2)          // przepłynięcie 2 misjonarzy na prawy brzeg
        przewiez(!prawa,m+2,l,i+1);
      if (prawa && m > 1)           // przepłynięcie 2 misjonarzy na lewy brzeg
        przewiez(!prawa,m-2,l,i+1);
      if (!prawa && l < 2)          // przepłynięcie 2 ludożerców na prawy brzeg
        przewiez(!prawa,m,l+2,i+1);
      if (prawa && l > 1)           // przepłynięcie 2 ludożerców na lewy brzeg
        przewiez(!prawa,m,l-2,i+1);
      if (!prawa && m < 3 && l < 3) // przepłynięcie misjonarza i ludożercy na prawy b.
        przewiez(!prawa,m+1,l+1,i+1);
      if (prawa && m > 0 & l > 0)   // przepłynięcie misjonarza i ludożercy na lewy b.
        przewiez(!prawa,m-1,l-1,i+1);
    }
  }
}
class Stan
{
  boolean prawa; // strona po której znajduje się łódka
  int m, l;      // liczba misjonarzy i ludożerców po prawej stronie rzeki

  Stan(boolean prawa, int m, int l)
  {
    this.prawa = prawa;
    this.m = m;
    this.l = l;
  }

  void wypiszStan()
  {
    System.out.println((3-m) + " " + (3-l) + (prawa ? "  \21 " : " \20  ") + m + " " + l);
  }
}