← 返回 bloomberg 的题目列表Grid Path Reachability with Refueling (Fuel-Constrained BFS)
类型：online_judge
Problem: Grid Reachability with Refueling
You are given an m x n grid grid with the following cell types:
S: start (exactly one)
T: target (exactly one)
.: open cell
#: blocked cell
F: fuel cell (refuels upon entry)
You have a fuel tank with initial fuel g (integer). Each move to a 4-neighbor cell costs 1 fuel.
Refueling rule:
When you enter an F cell, your fuel immediately increases by k (given positive integer).
The same F cell refuels every time you enter it (revisits are allowed).
Determine whether there exists a path from S to T such that fuel never becomes negative.
Input
Line 1: m n g k
Next m lines: strings of length n describing the grid
Output
Print true if reachable, otherwise false
Constraints
1 <= m, n <= 200
0 <= g <= 1e4
1 <= k <= 1e4
Sample Tests (5)
input:
3 3 2 2
S..
.#.
..T
output:
true
input:
3 3 3 2
S#T
...
...
output:
true
input:
3 3 1 2
S#T
###
..F
output:
false
input:
1 5 1 10
S..FT
output:
true
input:
2 4 2 1
S.F.
..#T
output:
false
Example
Input
3 3 2 2
S..
.#.
..T
Output
true