Lessie, inizialmente situato nella cella in alto a sinistra di una griglia rettangolare di m x n celle quadrate, vuole raggiungere la sua casa, stabilmente situata nella cella in basso a destra ( cella (m,n) ). Alcune celle, incluse tutte le celle esterne alla griglia m x n, sono inagibili; le altre (e tra esse la posizione iniziale di Lessie e la posizione della casa, sono agibili. Ad ogni passo, Lessie segue la seguente strategia: 1. se la cella alla sua destra e la cella sotto di lui sono entrambe agibili, allora sceglie su quale di queste 2 celle portarsi gettando una moneta perfettamente bilanciata; 2. se la cella alla sua destra e' agibile ma quella sotto di lui non lo e', allora si porta sulla cella alla sua destra; 3. se la cella sotto di lui e' agibile ma quella alla sua destra non lo e', allora si porta sulla cella sotto; 4. se la cella alla sua destra e la cella sotto di lui sono entrambe inagibili, allora si arrende ed entra in stallo. Ci interessa stabilire la probabilita' che Lessie ha di giungere a casa. Nella prima riga del file input.txt trovate 4 interi positivi m, n, qL, qH; seguono poi m righe che specificano, riga per riga, la griglia rettangolare m x n (0 = agibile, 1 = inagibile), seguono quindi qL righe che specificano qL posizioni di partenza per Lessie entro posizioni agibili della griglia (con la casa assunta sempre nella cella in basso a destra), seguono infine qH righe che specificano qH posizioni diverse per la casa (Home) sempre entro posizioni agibili della griglia (si assume qui' che la posizione di partenza di Lessie sia nella cella in alto a sinistra). Ciascuna di queste qH+qL posizioni viene specificata tramite una coppia (i, j) di numeri e varra' sempre che nella riga i e colonna j della griglia vi e' uno 0 ( = posizione agibile). Esempio: input.txt 3 4 2 2 0 0 0 0 0 0 0 0 0 0 1 0 1 3 3 1 3 1 2 2 Nella prima delle sue qL + qH +1 righe il file output.txt contiene la probabilita' che Lessie, partendo dalla cella (1,1) in alto a sinistra, giunga alla cella (m,n) in basso a destra. Nelle successive qL + qH righe risponde alle qL + qH queries aggiuntive, come nell'ordine in cui sono state poste. output.txt 0.5 1 0 0.25 0.5 In tutte le 20 istanze m, n <= 250, in almeno 13 istanze qH = 0, in almeno 11 istanze qL = 0 (e quindi in almeno 2 istanze qH = qL = 0), ed ovviamente qH, qL <= m*n poiche' nessuna query e' mai ripetuta. Danno punto solo le istanze risolte in un massimo di 1 decimo di secondo. IMPORTANTE: Per memorizzare le probabilita' utilizzate dei e, al momento di darli in output, passateli prima per la funzione: double round(long double p) { return int(p*10000 +0.0001)/10000.0; } in modo che gli outputs di due algoritmi diversi ma entrambi sostanzialmente corretti non differiscano per questioni di arrotondamento.