TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2097
  • 問題
  • P2097【搜索】推箱子
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    CodeWaySky的仓库是一块n*m个格子的矩形,有的格子是空闲的——没有任何东西,有的格子上已经堆放了沉重的货物——太重了而不再可能被移动。
    现在,CodeWaySky有一项任务,要将一个小箱子推到指定的格子上去。CodeWaySky可以在仓库中移动,但不得跨过沉重的不可移动的货物和箱子。当CodeWaySky站在与箱子相邻的格子上时,他可以做一次推动,把箱子推到另一个相邻的格子。考虑到箱子很重,CodeWaySky为了节省体力,想尽量减少推箱子的次数。你能帮帮他么?

    入力形式

    第一行有两个数n,m,表示仓库是n*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≤n,m≤100


    ソース  感谢nodgd修改题目排版