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  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).