2469: 滑动游戏

Nemoarce这次在须弥参与解谜嬴原石的小游戏，这次他迎来的游戏是这样的。 游戏规定:Nemoarce需要进行多次滑动。每次滑动选择一个P作为自己的起点，从起点出发，并沿着一个方向(上下左右)前进，前进的同时需要保证
1.不能走到 N的格子上 2.不能走出mxn的地图 3.不能中途改变方向。
当一次滑动结束时，Nemoarce可以开始选择下一个P并开始下一次滑动直到地图中不存在P,游戏结束。为了增加游戏的趣味性，每经过一个格子，这个格子就会从P变成 N 。 米忽悠为了让游戏充满挑战性，进行的滑动的次数越少，得到的奖励越多，现在Nemoarce想要拿到最高等级的奖励，来抽取小吉祥草王，所以他把地图交给了你，请你好好研究下怎么解决这个问题。

第一行两个数字m，n表示正方形地图的边长接下来m行，每行1个长度为n的字符串，由P和 N 组成。

一行一个数字，表示最少需要的滑动次数。

6 6
PPPPPP
PPNNNN
PPPPPP
PPNNNP
PPNNNP
PPPPPP

6