Huh that’s a neat problem. My instinct was to use a (fire, regular) tuple for cost, but then what A* heuristic can you use…
I guess run it once with no cost for regular tiles and remove fire from any tiles it used. Then run with normal tile costs, but block fire tiles. That doesn’t break ties nicely of course and I’m not convinced the first pass has a good A* heuristic either…