class Robot extends TreasureSeeker {
  private Battery b; 
  
  public Robot () { b = new Battery(); }

  public void visitDeadEnd (DeadEnd r) throws VisitorStuck {
    try {
      System.out.println("Heading towards " + r.toString());
      b.use();
      super.visitDeadEnd(r);
    }
    catch (NoPower e) { 
      if (r.hasElectricOutlet()) {
	System.out.println("Recharging");
	b.recharge();
	visitDeadEnd(r);
      }
      else {
	System.out.println("Can't reach " + r.toString());
	throw new VisitorStuck(true);
      }
    }
  }

  public void visitHall (Hall r) throws VisitorStuck {
    try {
      System.out.println("Heading towards " + r.toString());
      b.use();
      super.visitHall(r);
    }
    catch (NoPower e) { 
      if (r.hasElectricOutlet()) {
	System.out.println("Recharging");
	b.recharge();
	visitHall(r);
      }
      else {
	System.out.println("Can't reach " + r.toString());
	throw new VisitorStuck(true);
      }
    }
  }
}

//////////////////////////////////////////////////////////////////////////////

class TestRobot {
  public static void main (String[] args) {
    try {
      Maze r1 = new DeadEnd("R1", false, false);
      Maze r2 = new DeadEnd("R2", false, false);
      Maze r6 = new DeadEnd("R6", true, true);
      Maze r4 = new Hall("R4", r2,r6);
      Maze r3 = new Hall("R3", r1,r1);
      Maze r5 = new Hall("R5", r3,r4);
      
      Robot rob = new Robot();
      
      r5.accept(rob);
      System.out.println("Found treasure in " + rob.treasureLocation);
    }
    catch (VisitorStuck e) { 
      System.out.println("Stuck");
    }
  }
}

//////////////////////////////////////////////////////////////////////////////

interface BatteryI {
  final int MAX_CHARGE = 5;
  void recharge ();
  void use () throws NoPower;
}

class NoPower extends Exception {}

class Battery implements BatteryI {
  private int charge;

  public Battery () { this(MAX_CHARGE); }
  public Battery (int c) { charge=c; }

  public void recharge () { charge=MAX_CHARGE; }

  public void use () throws NoPower {
    if (charge == 0) {
      System.out.println("No power");
      throw new NoPower();
    }
    else charge--;
  }
}

//////////////////////////////////////////////////////////////////////////////

interface MazeI {
  boolean hasElectricOutlet();
  boolean hasTreasure();
  void accept (MazeVisitor rv) throws VisitorStuck;
  String toString();
}

interface MazeVisitor {
  void visitDeadEnd (DeadEnd r) throws VisitorStuck;
  void visitHall (Hall r) throws VisitorStuck;
}

class VisitorStuck extends Exception {
  boolean fatal;
  VisitorStuck (boolean f) { fatal = f; }
}

abstract class Maze implements MazeI {
  protected boolean outlet = false; 
  protected boolean treasure = false; 
  protected String name;

  public boolean hasElectricOutlet() { return outlet; }
  public boolean hasTreasure() { return treasure; }

  abstract public void accept (MazeVisitor rv) throws VisitorStuck;
}

//////////////////

class DeadEnd extends Maze {
  public DeadEnd (String name) { this.name = name; }
  public DeadEnd (String name, boolean o, boolean t) { 
    this.name = name; 
    outlet=o; 
    treasure=t; 
  }

  public void accept (MazeVisitor rv) throws VisitorStuck {
    rv.visitDeadEnd(this);
  }

  public String toString () { 
    return "DeadEnd " + name;
  }
}

//////////////////

class Hall extends Maze {
  public Maze leftExit, rightExit;

  public Hall (String name, Maze l, Maze r) { 
    this.name = name; 
    leftExit=l; 
    rightExit=r; 
  }

  public Hall (String name, boolean o, boolean t, Maze l, Maze r) {
    leftExit = l; 
    rightExit = r; 
    outlet = o;
    treasure = t;
  }

  public void accept (MazeVisitor rv) throws VisitorStuck {
    rv.visitHall(this);
  }

  public String toString() { 
    return "Hall " + name;
  }
}

class TreasureSeeker implements MazeVisitor {
  Maze treasureLocation;

  public TreasureSeeker () {}

  public void visitDeadEnd (DeadEnd r) throws VisitorStuck {
    System.out.println("Visiting " + r.toString());
    if (r.hasTreasure()) treasureLocation=r;
    else {
      System.out.println("Backtracking from " + r);
      throw new VisitorStuck(false);
    }
  }

  public void visitHall (Hall r) throws VisitorStuck {
    System.out.println("Visiting " + r.toString());
    if (r.hasTreasure()) { treasureLocation=r; return; }
    Maze left = r.leftExit;
    Maze right = r.rightExit;
    try {
      left.accept(this);
    }
    catch (VisitorStuck e) {
      if (e.fatal) throw e;
      else right.accept(this);
    }
  }
}