codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

106D.md (2981B)


      1 Source: https://codeforces.com/problemset/problem/106/D
      2 
      3 D. Treasure Island
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Our brave travelers reached an island where pirates had buried treasure. However as the ship was about to moor, the captain found out that some rat ate a piece of the treasure map.
     22 
     23 The treasure map can be represented as a rectangle *n* × *m* in size. Each cell stands for an islands' square (the square's side length equals to a mile). Some cells stand for the sea and they are impenetrable. All other cells are penetrable (i.e. available) and some of them contain local sights. For example, the large tree on the hills or the cave in the rocks.
     24 
     25 Besides, the map also has a set of *k* instructions. Each instruction is in the following form:
     26 
     27 "Walk *n* miles in the *y* direction"
     28 
     29 The possible directions are: north, south, east, and west. If you follow these instructions carefully (you should fulfill all of them, one by one) then you should reach exactly the place where treasures are buried.
     30 
     31 Unfortunately the captain doesn't know the place where to start fulfilling the instructions — as that very piece of the map was lost. But the captain very well remembers that the place contained some local sight. Besides, the captain knows that the whole way goes through the island's penetrable squares.
     32 
     33 The captain wants to know which sights are worth checking. He asks you to help him with that.
     34 
     35 Input
     36 
     37 The first line contains two integers *n* and *m* (3 ≤ *n*, *m* ≤ 1000).
     38 
     39 Then follow *n* lines containing *m* integers each — the island map's description. "#" stands for the sea. It is guaranteed that all cells along the rectangle's perimeter are the sea. "." stands for a penetrable square without any sights and the sights are marked with uppercase Latin letters from "A" to "Z". Not all alphabet letters can be used. However, it is guaranteed that at least one of them is present on the map. All local sights are marked by different letters.
     40 
     41 The next line contains number *k* (1 ≤ *k* ≤ 105), after which *k* lines follow. Each line describes an instruction. Each instruction possesses the form "*dir* *len*", where *dir* stands for the direction and *len* stands for the length of the way to walk. *dir* can take values "N", "S", "W" and "E" for North, South, West and East correspondingly. At that, north is to the top, South is to the bottom, west is to the left and east is to the right. *len* is an integer from 1 to 1000.
     42 
     43 Output
     44 
     45 Print all local sights that satisfy to the instructions as a string without any separators in the alphabetical order. If no sight fits, print "no solution" without the quotes.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 6 10  
     53 ##########  
     54 #K#..#####  
     55 #.#..##.##  
     56 #..L.#...#  
     57 ###D###A.#  
     58 ##########  
     59 4  
     60 N 2  
     61 S 1  
     62 E 1  
     63 W 2
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 AD
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 3 4  
     76 ####  
     77 #.A#  
     78 ####  
     79 2  
     80 W 1  
     81 N 2
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 no solution
     88 ```