Pipe Dream
As a kid, you might have played the game Pipe Dream.
Here's a picture (yes, from Windows 3.1!):
The goal is basically to get the fluid from one place to another.
In the original game, the pieces came to you randomly and you had to create the
longest path.
However, interesting games for humans tend to be hard for computers. Thus, your task is easier: use pipes to just guide the flow from one point to another. You will only have 4 types of pipes, and you can use as many of them wherever you wish.
You need to use the four "angle" pipes - use the characters
╔ ╗ ╚ ╝ to represent them. To output
these, use the following UTF-8 sequences:
| Character | UTF-8 sequence (hex) |
|---|---|
| ╔ | E2 95 94 |
| ╗ | E2 95 97 |
| ╚ | E2 95 9A |
| ╝ | E2 95 9D |
A grid with obstacles and the source/destination blocks will be given to you. Output any structure of pipes that gets the fluid to its destination.
Input
R (rows) ≤ 100, C (columns) ≤ 100, the size of the gridA grid of R lines with C characters each.
A '#' will represent a wall, ' ' an empty spot, 'S' the source, and 'D' the destination.
There will only be one source, and one destination.
Output
Arrange some pipes (if necessary) so that fluid can get from S to D.If it's impossible, just output IMPOSSIBLE.
Sample Input
9 12 ############ # # # S # # # # # # # # # # # ###D########
Sample Output
A similar setup to the picture (not quite as interesting, since you can't have straight pipes).
Your output need not be so complex, though.
Sample Input
5 10 ########## #S # ## # ###### ### # ####D#####
Sample Output
Of course, walls could be anywhere.
All Submissions
Best Solutions
Point Value: 15
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 02, 2008
Author: hansonw1
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Problems that use non-ASCII characters in the input and output are discouraged. This problem is retained for historical reasons. In Pascal, you can print out the UTF-8 sequences given like this (and so on): [code]write(#$E2#$95#$94);[/code] In C and C++, [code]printf("\xE2\x95\x94");[/code] Also for historical reasons, the judge for this problem will also accept the code page 437 encodings for the box drawing characters ╔ ╗ ╚ ╝. However, if you choose to use this encoding for your output, the "Your Output" display will be garbled since the web site uses exclusively UTF-8.In Pascal, you can print out the UTF-8 sequences given like this (and so on):
In C and C++,
Also for historical reasons, the judge for this problem will also accept the code page 437 encodings for the box drawing characters ╔ ╗ ╚ ╝. However, if you choose to use this encoding for your output, the "Your Output" display will be garbled since the web site uses exclusively UTF-8.