[SGU536] Berland Chess

题目描述

有一个 $n\times m$ 的棋盘。棋盘上恰好有一个白王，以及若干个不会主动移动的黑色棋子。棋子种类如下：

• *：白王；
• K：黑马；
• B：黑象；
• R：黑车；
• .：空格。

白王每步可以向水平、竖直或对角方向移动一格，也可以走到一个黑棋所在的格子并将其吃掉。

黑棋虽然不会主动移动，但它们仍然控制按照普通国际象棋走法能够攻击到的格子：

• 马走“日”字，并且可以跳过其他棋子；
• 象沿四条对角线攻击；
• 车沿横向或纵向攻击；
• 除马以外，棋子不能越过其他棋子。

白王任何时候都不能走到一个会被仍然存在的黑棋攻击的格子。当白王吃掉一个黑棋后，该黑棋从棋盘上消失，白王占据它原来的格子。

求白王吃掉全部黑棋所需的最少步数。

输入格式

第一行两个整数 $n,m$，其中 $1\le n,m\le15$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述棋盘。

保证：

• 棋盘上恰好有一个 *；
• 白王初始位置不受黑棋攻击；
• 棋盘上的棋子总数（包括白王）不超过 $15$。

输出格式

若可以吃掉全部黑棋，输出最少步数。

若棋盘上没有黑棋，输出 0。

若不可能吃掉全部黑棋，输出 -1。

样例

样例输入

7 9
.........
.........
.........
..R.K.R..
.........
.........
*........

样例输出

9