TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2097
  • Problem
  • P2097【搜索】推箱子
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

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

    Input Format

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

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

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

    Sample Input 1

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

    Sample Output 1

    7

    Sample Input 2

    4 3
    www
    wSw
    PMw
    KSS

    Sample Output 2

    1

    Sample Input 3

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

    Sample Output 3

    57

    Sample Input 4

    1 5
    PMwwK

    Sample Output 4

    NIE

    Hint

    $1\leq n,m\leq 100$


    Source  感谢nodgd修改题目排版