I'm not an AI as far as I know, but I would try a classic programming competition technique for this and observe that 6 isn't a very big number.<p>Step 0: Let's try to find a path without walking through fire. Run Dijkstra's or A* to find the shortest path with no fire, up to distance 6. If it succeeds, that's the answer.<p>Step 1: Okay, that didn't work. We need to go through at least 1 fire tile. Maybe we can do at most 1. Define distances to be a tuple (fire, cost) where fire is the number of fire tiles used and cost is the cost. Comparison works the obvious way, and Dijkstra's algorithm and A* work fine with distances like this. Look for a solution with cost at most (1, 6). Implemented straightforwardly will likely explore the whole grid (which may be fine), but I'm pretty sure that the search could be pruned when the distance hits values like (0, 7) since any path of cost (0, 7) cannot possibly be a prefix of a (1, c) path for any c<=6. If this succeeds, then return the path -- we already know there is no path of cost (0, c) for c <= 6, so a path of cost (1, c) for minimal c must be the right answer.<p>Step f: We know we need to go through at least f fire tiles. If f > 6, then just fail -- no path exists. Otherwise solve it like step 1 but for costs up to (f, 6). Prune paths with cost (f', c') with c' > 6.<p>This will have complexity 6<i>D where D is the cost of Dijkstra's or A</i> or whatever the underlying search is. Without pruning, D will be the cost of search with no length limit but, with pruning, D is nicely bounded (by the number of tiles with Manhattan distance 6 from the origin times a small constant).<p>For a large level and much larger values of 6, this could be nasty and might get as large as t^2 * polylog(t) where t is the number of tiles. Fortunately, is upper-bounded by 6 and doesn't actually get that large.