import java.io.*;

public class Cliente {

  //cerca un cammino attraverso la palude a partire dalla posizione <r,c>;
  //se il cammino esiste, restituisce true e aggiorna le componenti del cammino
  //  a partire dalla c-esima con il cammino trovato;
  //se il cammino non esiste, restituisce false
  private static boolean cercaCammino(Palude p, int r, int c, int[] camm) {
    if (c == p.getNumColonne()) return true;
    else if (!p.terra(r,c)) return false;
    else {
      camm[c] = r;
      if (r-1 >= 0 && cercaCammino(p, r-1, c+1, camm)) 
        return true;
      else if (cercaCammino(p, r,   c+1, camm)) 
        return true;
      else if (r+1 < p.getNumRighe() && cercaCammino(p, r+1, c+1, camm))
        return true;
      else return false;
    }
  }


  //cerca il primo cammino attraverso la palude;
  //se il cammino esiste, restituisce true e camm contiene il cammino
  //se il cammino non esiste, restituisce false
  private static boolean attraversaPalude(Palude p, int[] camm) {
    for (int riga = 0; riga < p.getNumColonne(); riga++)
      if (cercaCammino(p, riga, 0, camm)) return true;
    return false;
  }


  //restituisce una stringa che rappresenta il cammino attraverso la palude, se
  //questo esiste, e un messaggio se il cammino non esiste
  public static String stringaCammino(Palude p, int[] camm) {
    String ris = "";
    for (int riga = 0; riga < p.getNumRighe(); riga++) {
      for (int col = 0; col < p.getNumColonne(); col++)
        if (!p.terra(riga,col))
          ris = ris + "o";
        else if (camm[col] == riga)
          ris = ris + "#";
        else
          ris = ris + "*";
      ris = ris + "\n";
    }
    return ris;
  }


  public static void main (String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    System.out.print("Numero di righe della palude? ");
    int righe = Integer.parseInt(br.readLine());
    System.out.print("Numero di colonne della palude? ");
    int colonne = Integer.parseInt(br.readLine());
    System.out.print("Probabilita' di terra? ");
    double probTerra = Double.parseDouble(br.readLine());
    Palude palude = new Palude(righe, colonne, probTerra);
    System.out.println(palude);

    int[] cammino = new int[colonne];

    boolean trovato = attraversaPalude(palude, cammino);
    if (trovato)
      System.out.println("Cammino che attraversa la palude:\n"
                         + stringaCammino(palude, cammino));
    else
      System.out.println("Non esiste un cammino che attraversa la palude.");

  }
}