Problem 2608 --棋盘游戏 game

2608: 棋盘游戏 game

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 2  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][100kb]

Description

现有一新型的棋盘游戏。棋盘大小为N*N,棋盘中有M个棋子,棋子每步可以往上下左右移动一步,每个棋子必须按顺序移动到一个给定的出口点,且棋子之间永远不能相邻,求移动完所有棋子的最小步数。

注意:

C(C++)用户:请加全库,否则可能编译错误!

Input

输入数据的第一行是两个整数NM,表示棋盘大小为N*N,和棋子个数M

接下来有N行,每行N个数,x表示出口,o表示空地,1~M表示棋子,棋子1号棋子必须最先离开棋盘,2号其次,以此类推。

Output

输出一个数,即移动完所有棋子的最小步数,如果不能移动完则输出-1

Sample Input

3 2
x2o
ooo
oo1

Sample Output

7

HINT








所有数据,N<=4,M<=4

Source

[Submit][Status]