一位朋友发给我的，不会做...

题目如下：

在中国象棋中，一旦你把对方绝杀了，你就赢了。绝杀的意思是在己方落子后对方无论怎么走，将/帅都会被吃掉。（象棋规则自己去查）
本题中仅展示5x9的半个棋盘，你是红棋先行，求最少的绝杀对手的步数（保证有解的测试点最多20步），若不能绝杀输出“Impossible”（没有引号）
本题棋子表现手法:

将-k 士-a 象-e 马-h 炮-c 兵-s 车-r 空位-*

大写字母表示红棋，小写字母表示黑棋（本题不考虑被绝杀或对面笑）

样例输入：
*********
*********
****H****
rr**a***R
***a*k***

样例输出：
3

级别：P7,C6 难度：困难
提示：残局如下：（此处红棋表示：“帅仕相马车兵炮”，黑方“将士象馬車卒砲”，“＊”是空位,"．＂是落子前棋子的位置）
＊＊＊＊＊＊＊＊＊1
＊＊＊＊＊＊＊＊＊2
＊＊＊＊马＊＊＊＊3
車車＊＊士＊＊＊车4
＊＊＊士＊将＊＊＊5
ＡＢＣＤＥＦＧＨＩ
第一步，红棋H4车走到H5，黑棋将走到E4
＊＊＊＊＊＊＊＊＊1
＊＊＊＊＊＊＊＊＊2
＊＊＊＊马＊＊＊＊3
車車＊＊士＊＊＊．4
＊＊＊士＊将＊＊车5
ＡＢＣＤＥＦＧＨＩ

＊＊＊＊＊＊＊＊＊1
＊＊＊＊＊＊＊＊＊2
＊＊＊＊马＊＊＊＊3
車車＊＊士将＊＊＊4
＊＊＊士＊．＊＊车5
ＡＢＣＤＥＦＧＨＩ
第二步，红棋E3马走到G2，黑棋将走到F3
＊＊＊＊＊＊＊＊＊1
＊＊＊＊＊＊马＊＊2
＊＊＊＊．＊＊＊＊3
車車＊＊士将＊＊＊4
＊＊＊士＊＊＊＊车5
ＡＢＣＤＥＦＧＨＩ

＊＊＊＊＊＊＊＊＊1
＊＊＊＊＊＊马＊＊2
＊＊＊＊＊将＊＊＊3
車車＊＊士．＊＊＊4
＊＊＊士＊＊＊＊车5
ＡＢＣＤＥＦＧＨＩ
第三步，红棋H5车走到H3，绝杀
＊＊＊＊＊＊＊＊＊1
＊＊＊＊＊＊马＊＊2
＊＊＊＊＊将＊＊车3
車車＊＊士＊＊＊＊4
＊＊＊士＊＊＊＊．5
ＡＢＣＤＥＦＧＨＩ