As a human programmer I didn't quite understand the problem statement until I read the whole article and the tests. I believe the goal is to find a path with the fewest possible "fire" cells and the minimum cost as a tie breaker. The cost of a path is the sum of its cells' cost and it can't be greater than 5. If I understood the assignment correctly, I don't think the problem statement is equivalent to what's include…
The problem is, indeed, that Mr. Glaiel did not know the category of problem he was dealing with. A correct statement would be: "Given a solution set containing both the shortest path through fire and the shortest path avoiding fire, select the solution that fits within six tiles of movement, preferring the solution that avoids fire where possible." It's a constraint optimization problem in disguise: generate a solut…
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.