SPOJ in Armenian

Խողովակաշարը պետք է տրված n´m չափի ուղղանկյունաձև տարածքի (1, 1) կոորդինատներով ձախ վերևի վանդակը միացնի   (n, m) կոորդինատներով աջ ներքևի վանդակին։ Խողովակաշարը կառուցելու համար կարող են օգտագործվել հետևյալ չորս տիպի խողովակները, որոնցից յուրաքանչյուրը վանդակի որևէ երկու կողմ իրար է միացնում.

Նկ.1.  Խողովակների տիպերը

Խողովակները կարող են օգտագործվել միայն այնպես, ինչպես ցույց է տրված նկարում, այսինքն առանց պտտեցնելու։ Օրինակ, ոչ մի խողովակ չի կարող վանդակի ձախ կողմը միացնել վերևի կողմին։ Խողովակաշարի խողովակները պետք է կապակցված լինեն, այսինքն, եթե երկու հարևան վանդակներ պատկանում են խողովակաշարին, ապա այդ երկու վանդակների խողովակները պետք է իրար միանան այդ վանդակների ընդհանուր կողմով։ Ամբողջ խողովակաշարը պետք է դուրս չգա տրված ուղղանկյունաձև տիրույթից։

Ամենասկզբում վանդակներից յուրաքանչյուրը կարող է դատարկ լինել ( հետագայում այնտեղ կարող է խողովակ տեղադրվել), կամ պարունակել հետևյալ օբյեկտներից որևէ մեկը.

ա) նախապես կառուցված խողովակ, որը կարող է կապող օղակ հանդիսանալ խողովակաշարում, բայց չի կարող փոխարինվել այլ տիպի խողովակով

բ) խոչընդոտ, խողովակաշարը չպիտի օգտագործի այդ վանդակը։

Նկար 2-ում պատկերված է (n=4, m=5) չափերով նախապես կառուցված խողովակներ և խոչընդոտներ պարունակող տարածքի օրինակ։ (4;2) վանդակը պարունակում է խոչընդոտ։

Նկ.2.  Տարածքի օրինակ

Այս տարածքի համար երեք տարբեր եղանակով կարելի է խողովակաշար կառուցել, ինչպես ցույց է տրված նկար 3-ում։

Ձեր խնդիրն է գրել ծրագիր, որը հաշվի խողովակաշար կառուցելու տարբեր հնարավոր եղանակների քանակը։

Մուտքը

Մուտքային ֆայլի առաջին տողը պարունակում է տարածքի n (n£10) և m (m£10) չափերը։ Հաջորդ m տողերից յուրաքանչյուրը պարունակում է n թիվ։ i+1-րդ տողի j-րդ թիվը ներկայացնում է տարածքի i-րդ տողի j-րդ սյան վանդակը։ 0-ն նշանակում է, որ վանդակը դատարկ է, 1-ից 4 թվերը ցույց են տալիս խողովակի տիպը համաձայն նկար 1-ի, 5-ը նշանակում է, որ վանդակը խոչընդոտ է պարունակում։ Երկու հարևան թվեր իրարից անջատվում են մեկ բացակով։

Ելքը

Ելքային ֆայլում հարկավոր է արտածել մի թիվ՝ խողովակաշար կառուցելու տարբեր հնարավոր եղանակների քանակը։

Օրինակ

Մուտքը.
4 5
0 0 3 2
0 4 0 5
4 0 0 0
4 0 1 0
0 3 0 0

Ելքը.
3