[wrsh07]

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.