小明在玩一款迷宮游戲，在游戲中他要控制自己的角色離開一間由NxN個格子組成的2D迷宮。  
小明的起始位置在左上角，他需要到達右下角的格子才能離開迷宮。
每一步，他可以移動到上下左右相鄰的格子中（前提是目標格子可以經(jīng)過）。
迷宮中有些格子小明可以經(jīng)過，我們用'.'表示；
有些格子是墻壁，小明不能經(jīng)過，我們用'#'表示。
此外，有些格子上有陷阱，我們用'X'表示。除非小明處于無敵狀態(tài)，否則不能經(jīng)過。

有些格子上有無敵道具，我們用'%'表示。
當小明第一次到達該格子時，自動獲得無敵狀態(tài)，無敵狀態(tài)會持續(xù)K步。
之后如果再次到達該格子不會獲得無敵狀態(tài)了。  

處于無敵狀態(tài)時，可以經(jīng)過有陷阱的格子，但是不會拆除/毀壞陷阱，即陷阱仍會阻止沒有無敵狀態(tài)的角色經(jīng)過。

給定迷宮，請你計算小明最少經(jīng)過幾步可以離開迷宮

第一行包含兩個整數(shù)N和K。 (1 <= N <= 1000 1 <= K <= 10)  
以下N行包含一個NxN的矩陣。
矩陣保證左上角和右下角是'.'。

一個整數(shù)表示答案。如果小明不能離開迷宮，輸出-1。

零基礎同學可以先學習視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結構等課程，提供視頻講解以及配套習題，還有老師答疑，點擊這里了解課程詳情

藍橋杯