codeforces-scrape

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

510B.md (2119B)


      1 Source: https://codeforces.com/problemset/problem/510/B
      2 
      3 B. Fox And Two Dots
      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 Fox Ciel is playing a mobile puzzle game called "Two Dots". The basic levels are played on a board of size *n* × *m* cells, like this:
     22 
     23 ![](https://espresso.codeforces.com/30ff39b4da1012c329ff4baf7733be9af8d54f55.png)
     24 
     25 Each cell contains a dot that has some color. We will use different uppercase Latin characters to express different colors.
     26 
     27 The key of this game is to find a cycle that contain dots of same color. Consider 4 blue dots on the picture forming a circle as an example. Formally, we call a sequence of dots *d*1, *d*2, ..., *d**k* a cycle if and only if it meets the following condition:
     28 
     29 1. These *k* dots are different: if *i* ≠ *j* then *d**i* is different from *d**j*.
     30 2. *k* is at least 4.
     31 3. All dots belong to the same color.
     32 4. For all 1 ≤ *i* ≤ *k* - 1: *d**i* and *d**i* + 1 are adjacent. Also, *d**k* and *d*1 should also be adjacent. Cells *x* and *y* are called adjacent if they share an edge.
     33 
     34 Determine if there exists a cycle on the field.
     35 
     36 Input
     37 
     38 The first line contains two integers *n* and *m* (2 ≤ *n*, *m* ≤ 50): the number of rows and columns of the board.
     39 
     40 Then *n* lines follow, each line contains a string consisting of *m* characters, expressing colors of dots in each line. Each character is an uppercase Latin letter.
     41 
     42 Output
     43 
     44 Output "Yes" if there exists a cycle, and "No" otherwise.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 3 4  
     52 AAAA  
     53 ABCA  
     54 AAAA
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 Yes
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 3 4  
     67 AAAA  
     68 ABCA  
     69 AADA
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 No
     76 ```
     77 
     78 Input
     79 
     80 ```
     81 4 4  
     82 YYYR  
     83 BYBY  
     84 BBBY  
     85 BBBY
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 Yes
     92 ```
     93 
     94 Input
     95 
     96 ```
     97 7 6  
     98 AAAAAB  
     99 ABBBAB  
    100 ABAAAB  
    101 ABABBB  
    102 ABAAAB  
    103 ABBBAB  
    104 AAAAAB
    105 ```
    106 
    107 Output
    108 
    109 ```
    110 Yes
    111 ```
    112 
    113 Input
    114 
    115 ```
    116 2 13  
    117 ABCDEFGHIJKLM  
    118 NOPQRSTUVWXYZ
    119 ```
    120 
    121 Output
    122 
    123 ```
    124 No
    125 ```
    126 
    127 Note
    128 
    129 In first sample test all 'A' form a cycle.
    130 
    131 In second sample there is no such cycle.
    132 
    133 The third sample is displayed on the picture above ('Y' = Yellow, 'B' = Blue, 'R' = Red).