TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2097
  • 题目
  • P2097【搜索】推箱子
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    CodeWaySky的仓库是一块$n\times m$个格子的矩形,有的格子是空闲的——没有任何东西,有的格子上已经堆放了沉重的货物——太重了而不再可能被移动。

    现在,CodeWaySky有一项任务,要将一个小箱子推到指定的格子上去。CodeWaySky可以在仓库中移动,但不得跨过沉重的不可移动的货物和箱子。当CodeWaySky站在与箱子相邻的格子上时,他可以做一次推动,把箱子推到另一个相邻的格子。考虑到箱子很重,CodeWaySky为了节省体力,想尽量减少推箱子的次数。你能帮帮他么?

    输入格式

    第一行有两个数$n,m$,表示仓库是$n\times m$的矩形。以下有$n$行,每行有$m$个字符,表示一个格子的状态。

    • S 表示该格子上放了不可移动的沉重货物。
    • w 表示该格子上没有任何东西
    • M 表示CodeWaySky初始的位置
    • P 表示箱子的初始位置
    • K 表示箱子的目标位置
    输出格式

    只有一行,一个数,表示CodeWaySky最少要推多少次箱子。如果CodeWaySky不可能将箱子推到目标位置,那么请输出NIE,表示无解。

    样例输入 1

    10 12
    SSSSSSSSSSSS
    SwwwwwwwSSSS
    SwSSSSwwSSSS
    SwSSSSwwSKSS
    SwSSSSwwSwSS
    SwwwwwPwwwww
    SSSSSSSwSwSw
    SSSSSSMwSwww
    SSSSSSSSSSSS
    SSSSSSSSSSSS

    样例输出 1

    7

    样例输入 2

    4 3
    www
    wSw
    PMw
    KSS

    样例输出 2

    1

    样例输入 3

    12 12
    SMSwwSSSSSSS
    SPSwwwwwwwww
    SwSwSwSwSSww
    SwSwSwwwwwwS
    SwSwSwSSwSwS
    SwSwSwSwwSwS
    SwSwSKwSwSwS
    SwSwSSwSwSwS
    SwwwwwwwwSwS
    wwSSSSSSwSwS
    wwwwwwwwwwwS
    SSSSSSSSSwwS

    样例输出 3

    57

    样例输入 4

    1 5
    PMwwK

    样例输出 4

    NIE

    提示

    $1\leq n,m\leq 100$


    来源  感谢nodgd修改题目排版