Ալգորիթմներ և Տվյալների Կառուցվածքներ

Փոխել ռոբոտները տեղերով

Դուք աշխատում եք մի ստարտափում, որը փորձում է մրցակցել Boston Dynamics ընկերության հետ։ Ի շարքին հանդիպող փորձություններից մեկը երկու ռոբոտներին ցանցի (grid) վրա տեղերով փոխելն է այնպես, որ դրանք երբեք չհայտնվեն միմյանց վրա։
Ցանցը ունի բարձրություն h և լայնություն w, որտեղ հատակը նշված է կետերով (.), իսկ պատերը նշված են հեշ նշաններով (#)։
Ռոբոտներին թույլատրվում է շարժվել հորիզոնական, ուղղահայաց և թեք ուղղություններով դեպի հարևան բջիջներ։ Այնուամենայնիվ, նրանք չեն կարող կանգնել կամ անցնել միմյանց վրա, կամ մտնել պատերի վրա։ Յուրաքանչյուր քայլին երկու ռոբոտները կարող են կատարировать մեկ տեղաշարժ կամ մնալ իրենց ընթացիկ դիրքերում։ Նրանք չեն կարող «ցատկել» միմյանց վրայով մեկ քայլի ընթացքում։
Ձեզ խնդրում են գտնել նվազագույն քայլերի քանակը, որը նախապատրաստում է առաջին ռոբոտին հասնել երկրորդ ռոբոտի նախնական տեղին, իսկ երկրորդ ռոբոտին՝ առաջինի տեղին։

Մուտք

Մուտքի առաջին տողում տրված են 2 ամբողջ թվերը h և w (1 ≤ h, w ≤ 50)։
Հաջորդ h տողերում յուրաքանչյուրում ներառված են w նշաններ, որոնք ներկայացնում են ցանցը։
Առաջին ռոբոտը նշված է A տառով, իսկ երկրորդ ռոբոտը՝ B տառով։

Ելք

Ծրագիրը պետք է տպի ռոբոտները տեղերով փոխելու համար պահանջվող նվազագույն քայլերի քանակը։ Եթե դա հնարավոր չէ, պետք է տպել Impossible:

Օրինակներ

Input

4 4
AB.#
###.
...#
.###
Output

11
Input

2 2
AB
..
Output

2
Input

1 3
A.B
Output

Impossible
 

Constraints

Time limit: 15 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue