Desants labirintā

ID: desants
Grūtība: 3/5
Laika limits: 1

Uzdevums

Ir dots labirints, kas izskatās kā taisnstūris ar izmēriem M*N rūtiņas. Katra labirinta rūtiņa var būt gan tāda, caur kuru ir iespējams pārvietoties, gan tāda, caur kuru nav.
Vienība izsēdina desantnieku labirinta rūtiņā (M1,N1)(Šeit un turpmāk pirmais skaitlis - rindas numurs, otrais - kolonnas numurs).
Desantniekam nepieciešams nokļūt rūtiņā (M2,N2) pa īsāko iespējamo ceļu. Pārvietoties katrā solī drīkst tikai uz tādu brīvo rūtiņu, kurai ar pašreizējo ir kopīga mala.

Uzrakstiet programmu, kas atrod un izvada visus īsākos iespējamos ceļus no sākotnējās līdz beigu rūtiņai.

 

Ievaddati

Teksta faila desants.in pirmajā rindā doti labirinta izmēri - naturāli skaitļi M(rindiņu skaits) un N(kolonnu skaits), kas atdalīti ar tukšumsimbolu. Zināms, ka 0 < M,N < 101.
Faila otrajā rindā dotas desantnieka sākotnējās rūtiņas koordinātas - M1 un N1 vērtības, kas atdalītas ar tukšumsimbolu.
Faila otrajā rindā dotas desantnieka beigu rūtiņas koordinātas - M2 un N2 vērtības, kas atdalītas ar tukšumsimbolu.
Faila nākošajās M rindās dots pa N simboliem - vienas labirinta rindas apraksts.
Ar simbolu # apzīmētās tās rūtiņas, caur kurām iziet nav iespējams, bet ar * tās, caur kurām pārvietošanās ir iespējama.

 

Izvaddati

Teksta faila desants.out katrā rindā jāizvada visu īsāko ceļu apraksts, izvadot pa viena ceļa aprakstam katrā rindā.
Katra ceļa apraksts ir ciparu virkne, kur cipars «0» nozīmē «soli pa kreisi», «1» - soli uz augšu, «2» - soli pa labi, «3» - soli uz leju. Ciparu skaits skaitlī ir ceļa garums.
Ceļu apraksti jāizvada augošā secībā. Izvad faila izmērs nepārsniedz 1 megabaitu, un noteikti eksistē vismaz viens ceļš no sākotnējās uz beigu rūtiņu.

 

Piemērs

desants.indesants.out
3 3
1 1
3 2
***
##*
#**
22330
  
desants.indesants.out
2 2
1 1
2 2
**
**
23
32

 

Atsauces

Uzdevums ņemts no Baltkrievijas 2001. gada sacensībām.
© 2001-2002 olimps! http://www.lio.lv/olimps/