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.
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.
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.
| desants.in | desants.out |
3 3 1 1 3 2 *** ##* #** |
22330 |
| desants.in | desants.out |
2 2 1 1 2 2 ** ** |
23 32 |