Did you draw out a grid and start tracing routes? Well, you're on the right track, but as Shining Armor found, it's not possible to visit each room only once without missing one.
This catches some ponies out because it IS true that any contaminated room you visit must be destroyed before you leave. But that's just a case of not reading the question carefully. Isn't there one room that isn't contaminated, and thus fair game to visit more than once?
That's right: the entrance. It's the only uncorrupted room.
True, Shining WILL have to destroy the entrance after his second visit to keep the dark magic from spreading any further, but one more visit is all he needs.
Now that you know you need to double back to the entrance to solve the puzzle, you will find there are at least 8 different ways to solve this puzzle: 4 starting by destroying the room south of the entrance, and 4 involve destroying the room east of the entrance first.
Can you find them all?