oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

mining Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

mining v2.html

Steve is playing Minecraft! (and breaking the 4th wall) However, he finds himself suddenly sucked into a giant portal! Now Steve finds himself stuck in a mysterious world with r rows and c columns (1 <= r, c <= 300) full of stone blocks indicated by 'W' and bedrock indicated by 'B'. Steve has lost all his inventory except for a stone pickaxe with k (0 <= k <= 132) remaining uses (if you're wondering about the number that's the durability of a stone pickaxe). Furthermore, Steve finds that there is a low bedrock celing so he cannot jump over (and past) blocks. Note that the pickaxe is required to mine through stone blocks but it cannot destroy bedrock.

Steve is currently at position 'S'. He can only walk up, down, left or right and not diagonally. Steve needs to get to the exit portal located at position 'E'. Steve can mine blocks but each block mined will deplete his pickaxe by 1 use. Your task is to find the minimum number of steps Steve needs to take to reach the portal since his cuboid legs aren't exactly easy to walk on.

Input

The first line of input contains 3 integers r, c and k.

The next r lines describe the terrain on the corresponding rows. 'S' represents the start, 'E' represents the portal, 'W' represents a stone block, 'B' represents bedrock and '.' represents empty space.

Output

Print out the minimum number of steps required for Steve to escape. If he is unable to, print -1.

Limits

Subtask 1 (11%): 1 ≤ r, c ≤ 20, k = 0

Subtask 2 (38%): 1 ≤ r, c ≤ 100, k ≤ 40

Subtask 3 (51%): 1 ≤ r, c ≤ 300, k ≤ 132

Subtask 4 (0%): Sample Testcases

Sample Input 1

5 5 1
S.WWW
.B.WW
BW...
WWW.W
WE...

Sample Output 1

9

Sample Input 2

5 5 0
S.WWW
.B.WW
BW...
WWW.W
WE...

Sample Output 2

-1

Tags

Graph Theory, Breadth First Search

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
111201s64MBMinimum
238201s64MBMinimum
351201s64MBMinimum
4021s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o mining -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.