codeforces-scrape

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

475B.md (2138B)


      1 Source: https://codeforces.com/problemset/problem/475/B
      2 
      3 B. Strongly Connected City
      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 Imagine a city with *n* horizontal streets crossing *m* vertical streets, forming an (*n* - 1) × (*m* - 1) grid. In order to increase the traffic flow, mayor of the city has decided to make each street one way. This means in each horizontal street, the traffic moves only from west to east or only from east to west. Also, traffic moves only from north to south or only from south to north in each vertical street. It is possible to enter a horizontal street from a vertical street, or vice versa, at their intersection.
     22 
     23  ![](https://espresso.codeforces.com/84cbe4fd6c95553e49925d85ae321a4b8c12f327.png) 
     24 
     25 The mayor has received some street direction patterns. Your task is to check whether it is possible to reach any junction from any other junction in the proposed street direction pattern.
     26 
     27 Input
     28 
     29 The first line of input contains two integers *n* and *m*, (2 ≤ *n*, *m* ≤ 20), denoting the number of horizontal streets and the number of vertical streets.
     30 
     31 The second line contains a string of length *n*, made of characters '<' and '>', denoting direction of each horizontal street. If the *i*-th character is equal to '<', the street is directed from east to west otherwise, the street is directed from west to east. Streets are listed in order from north to south.
     32 
     33 The third line contains a string of length *m*, made of characters '^' and 'v', denoting direction of each vertical street. If the *i*-th character is equal to '^', the street is directed from south to north, otherwise the street is directed from north to south. Streets are listed in order from west to east.
     34 
     35 Output
     36 
     37 If the given pattern meets the mayor's criteria, print a single line containing "YES", otherwise print a single line containing "NO".
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 3  
     45 ><>  
     46 v^v
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 NO
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 4 6  
     59 <><>  
     60 v^v^v^
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 YES
     67 ```
     68 
     69 Note
     70 
     71 The figure above shows street directions in the second sample test case.