As part of a project for another class, I was building a small fusion reactor in my dormroom. Everything was fine until I turned the machine on, then I realized that I had built a hot fusion reactor with a cold fusion cooling system. Apparently I was working off the wrong page.
In any case, all the pipes I had connected up came unconnected and the reactor is going to overheat unless I can get some coolant flowing again. If don't need a complete system - I just a single flow from the in pipe to the out pipe. With that I'm sure things can be controlled.
I need you to write a program that tells me whether the pipes can be repaired (So I can quickly decide whether to fix them or escape on the B-line).
The pipe segments are attached to my wall. Each segment can be rotated but not moved to a different position. Segments can be attached to their neighbours where the end of one segment touches the end of another. There are four types of pipe:
- l : standard straight segments
- v : right angle pipes
- x : 4-way pipes (coolant can flow any direction through a 4-way pipe)
- o : straight heated segments
In order to get coolant flowing, there needs to be some way I can twist and connect the segments that makes a continuous path between the start and the end. Not only that, but there must be such a path goes through less than three heated segments or the pipes will burst.
Starting and ending segments can be any type of pipe. If they are heated segments, this must be taken into account.
The first line of the input contains a number n 0 < n < 100 that contains the number of test cases. The test cases follow.
Each test case starts with a line containing six integers. In order, they are:
Following this is the grid of pipes. There will be as many lines as there are rows, and each line contains as many characters as there are columns. There are four kinds of pipe, as described above. Other characters signify that there is no pipe at a location, and coolant cannot flow through it.
- The number of rows of pipes (< 30)
- The number of columns of pipes (< 30)
- Starting row ( between 0 and rows-1 )
- Starting column ( between 0 and cols-1 )
- Ending row ( between 0 and rows-1 )
- Ending column ( between 0 and cols-1 )
Output either "YES" or "NO" on a line, based on whether it is possible to construct a path from the start location to the end location that does not pass through three or more heated pipe segments.
3 5 0 0 2 4
5 5 0 0 2 4