Naloga E: Poševni labirint

 

Program E.C, E.CPP, E.PAS

Ce z znakoma / in \ zapolnimo pravokotnik, dobimo preprost poševen labirint (na spodnji sliki je labirint višine 4 in širine 6).

Ni se težko prepricati, da so tako dobljeni labirinti sestavljeni le iz poti in ciklov, ne vsebujejo pa nobenih razvejišc. Vaša naloga je prešteti, koliko ciklov vsebuje tak labi­rint, in dolociti dolžino najdaljšega cikla. Labirint na sliki ima dva cikla: prvi je dolžine 16, drugi pa dolžine 4.

Vhod

Vhod je sestavljen iz zaporedja testnih primerov. Vsak testni primer se pricne s parom števil w (širina) in h (višina) v svoji vrstici. Pri tem je 1 £ h, w £ 75. Naslednjih h vrstic je opis labirinta. Vsaka od teh vrstic vsebuje natanko w znakov / oziroma \. Konec vhoda oznacuje testni primer z w = 0 in h = 0.

Izhod

Za vsak testni primer je treba v svoji vrstici izpisati besedilo "Maze #n:", kjer je n zaporedna številka testnega primera. V naslednji vrstici naj bo izpis "k Cycles; the longest has length l.", kjer je k število ciklov, ki jih vsebuje labirint, in l dolžina najdaljšega cikla v labirintu. Ce labirint ne vsebuje ciklov, izpišite besedilo "There are no cycles.". Vsakemu izpisu testnega primera naj sledi prazna vrstica.

Primer vhodnih podatkov

6 4

\//\\/

\///\/

//\\/\

\/\///

3 3

///

\//

\\\

0 0

in pripadajoci rezultat

Maze #1:

2 Cycles; the longest has length 16.

Maze #2:

There are no cycles.