Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Haunting of Herobrine

By hjr265 · Limits 1s, 512 MB

Herobrine’s horror stories are known by many, but only a few dares to speak that name out loud, for anyone who does suffer the same fate. Herobrine stays out of your sight and stares at you through the dense fog observing your every move. If you manage to catch a glimpse of Herobrine though, you see yourself standing in front of you - like looking at a mirror; only Herobrine’s eyes are empty.

In the world of Herobrine, redstone circuits are the only form of automation. Redstone components are made of redstone dust and other natural materials such as wood, stone, etc. These components and redstone signal works in a way similar to how electricity and electronics work in our world. The subject of redstone structures is huge and only Herobrine has mastered it all.

You don’t know how you came to Herobrine’s world, but you know that there is no way out! And to fight with Herobrine, redstone is your only option!

Redstone structures usually have a power source, a transmission component, and a mechanism component. A power source, such as the redstone torch (@), provides a redstone signal of a certain strength. This signal can travel through transmissions components, such as redstone dust (*), just like electric cables, for a certain distance. Redstone signals do not travel diagonally from cell to another. A redstone signal reaching a mechanism component, such as an alarm system (#), can power it.

........
...***#.
...*....
...*....
...*....
.@**....
........       

Redstone signals follow some simple rules. For each unit of redstone dust the signal travels through its strength falls by 1. Redstone torches provide a signal strength of 15. Blobs of redstone dust next to each other with no free space between them connects to each other and transfers the signal. A mechanism component at the end of the redstone dust can only be powered if the strength it receives is of no less than 1.

When the distance between the redstone torch and mechanism component is too large, redstone repeaters ($) can be used to boost the signal strength back to 15.

................
.............#..
.............*..
.............*..
.............*..
.....*********..
.....*..........
.....*..........
.....$..........
.....*..........
.....*..........
.....*..........
.....*..........
.....*..........
.@****..........
................

Without a repeater, redstone signal cannot travel through long paths of redstone dust. Here the signal strength falls to 1 just before reaching the alarm system (at the last blob of redstone dust, *):

@***************#

To keep Herobrine out of your house, you want to set up some redstone alarm systems. You found some redstone circuit diagrams in a treasure chest a few days ago, but you need to make sure they will actually work before following them.

The sun is about to set and you can still feel Herobrine looking at you through the dense fog. You know time is running out!

Input

The first line will contain an integer N (N ≤ 20).

The following N lines will represent the redstone circuit diagram. Each line will contain N characters:

  • . is a free space
  • * is a blob of redstone dust
  • @ is a redstone torch
  • # is an alarm system
  • $ is a redstone repeater

Each diagram will have at most one redstone torch and one alarm system. None of the diagrams have any redstone dust path overlapping with itself.

Output

Print “Yes” if the signal from the torch will reach the alarm system; otherwise, print “No”.

Samples

InputOutput
8
........
...***#.
...*....
...*....
...*....
.@**....
........
........
Yes
InputOutput
16
................
.............#..
.............*..
.............*..
.............*..
.....*********..
.....*..........
.....*..........
.....$..........
.....*..........
.....*..........
.....*..........
.....*..........
.....*..........
.@****..........
................
Yes


Discussion
Statistics

79% Solution Ratio

ssavi1994Earliest, Dec '16

ssavi1994Fastest, 117.2s

ssavi1994Lightest, 131 kB

zip_lightShortest, 1262B

Submit

Login to submit