Can you not do A* where it normally costs one point per tile, 10 points for a fire tile but 1000000 points for > 6 tiles, so you never explore the > 6 options unless you have run out of shorter routes?
If the parent's description of the problem is correct, then imagine this:
You have a solution of length 6, no fire;
Solution of length 4, one fire;
Ok sure you prefer the no fire one.
the score for the paths is 6 and 13, respectively
Your algorithm works!
But as soon as you have a solution of length 10 (or some length bigger than the length you want), a* still prefers that to the solution without fire - but the answer must be less then or equal to six steps
You can modify to make fire cost 1.1. Now if you find a solution of length 6, you know it must be correct (it minimized the number of fire squares and ended up with a length six solve). But if it's not length 6, you need to increase the cost of fire and run again if there was any fire in your solution.
At a glance, it might be OK that way, and I would give it the gold star. It's just unintuitive to make the leap to "apply a cost to the total length of the path" as a way of expressing preferences among distinct categories of path.
Implementation of the categories as completely independent paths falls out of the clarified problem definition directly. It's really in nailing the specification that the problem is hard, i.e., even with GPT we're still programming.
