Pretty much this. Attempt to find a path to the target destination with a first A* run that disregards fire tiles, and if that fails due to limited movement, then do a second run with the fire tiles. I like that this mirrors the decision making a human would follow, too: I won't cross the fire tile unless I'm absolutely required to.