Fox Ciel is playing a mobile puzzle game called "Two Dots". The basic levels are played…
- User
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:
Each cell contains a dot that has some color. We will use different uppercase Latin characters to express different colors.
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 d1, d2, ..., dk a cycle if and only if it meets the following condition:
- These k dots are different: if i ≠ j then di is different from dj.
- k is at least 4.
- All dots belong to the same color.
- For all 1 ≤ i ≤ k - 1: di and di + 1 are adjacent. Also, dk and d1 should also be adjacent. Cells x and y are called adjacent if they share an edge.
Determine if there exists a cycle on the field. Input
The first line contains two integers n and m (2 ≤ n, m ≤ 50): the number of rows and columns of the board.
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.
Output
Output "Yes" if there exists a cycle, and "No" otherwise.
Examples
Input
3 4 AAAA ABCA AAAA
Output
Yes
Input
3 4 AAAA ABCA AADA
Output
No
Input
4 4 YYYR BYBY BBBY BBBY
Output
Yes
Input
7 6 AAAAAB ABBBAB ABAAAB ABABBB ABAAAB ABBBAB AAAAAB
Output
Yes
Input
2 13 ABCDEFGHIJKLM NOPQRSTUVWXYZ
Output
No
Note
In first sample test all 'A' form a cycle.
In second sample there is no such cycle.
The third sample is displayed on the picture above ('Y' = Yellow, 'B' = Blue, 'R' = Red).
Assistant
We need to determine if there exists a cycle of at least 4 same-colored cells that are all distinct and form a cycle, with adjacency defined as 4-directional (up/down/left/right).
Constraints: n,m up to 50, so total cells 2500. We can do DFS/BFS for each cell to detect cycles.
Classic problem: find if there exists a cycle in a grid where nodes are colored, and cycle must be all same color, length >=4, and not necessarily simple? Condition says "These k dots are different", so it's a simple cycle (no repeated vertices). So we need to detect a simple cycle of length >=4 in a grid graph restricted to same color.
Approach: For each cell, we can perform DFS that keeps track of visited status and parent to detect back edges. But careful: the graph is undirected. In an undirected graph, a cycle exists if we encounter a visited node that is not the parent. However, we also need to ensure that the cycle length is at least 4. In a grid, the smallest possible cycle is of length 4 (a square). However, we need to be careful because there could be a cycle of length 4 or more. The typical DFS detection of cycles in undirected graph: For each vertex, if we see an adjacent vertex that is already visited and not the parent, then we have a cycle. The length of that cycle can be determined by the depth difference + 1. But we need to guarantee the cycle length >=4. However, note that in a grid with 4-direction adjacency, a back edge to a node that is not parent may result in a cycle of length 2? Actually, in an undirected graph, if there is an edge between two nodes, and we go from u to v and then immediately see v's neighbor u again, that would be the parent, so we ignore. If we see a visited neighbor that is not the parent, then the cycle includes the path from the neighbor to current plus the edge, and the length is (depth[current] - depth[neighbor] + 1). Since the graph is grid, could that be 2? That would imply depth[current] - depth[neighbor] = 1? But if neighbor is visited and not parent, then the difference must be at least 2? Actually, consider a triangle: three nodes each connected; undirected graph can have triangle. In grid, triangles are impossible because only orthogonal adjacency, no diagonal. So smallest cycle is a square, which has length 4. However, there could be a "cycle" that is actually two nodes connected by two different paths? That would be a cycle of length >2. But in grid, there can be cycles of length 4,6,8, etc. So if we detect a back edge that is not the parent, the cycle length will be at least 4 because grid is bipartite? Actually, grid is bipartite; cycles even length. So length will be even and at least 4. But is it guaranteed that any back edge will give a cycle length >=4? Consider a 2x2 square: nodes positions (0,0), (0,1), (1,0), (1,1). Graph edges: (0,0)-(0,1), (0,0)-(1,0), (0,1)-(1,1), (1,0)-(1,1). Suppose DFS start at (0,0), go to (0,1) (depth 1), then from (0,1) go to (1,1) (depth 2), then from (1,1) adjacent to (1,0) (depth 3) (if not visited), then from (1,0) adjacent to (0,0) which is visited and not parent (parent is (1,1)), depth[0,0]=0, current depth=3, cycle length = 3-0+1 =4. Good. Suppose we go from (0,0) to (0,1) to (1,1) then see (0,1) is visited but that's parent, ignore. So the only back edge yields length 4.
What about a "cycle" of length 4 that is not a simple square but maybe a shape like a "C" that closes? Actually, need simple cycle.
However, there is a catch: The cycle must consist of dots of the same color. So we need to consider only edges between cells of same color. So essentially we have separate graphs per color. For each color, we need to detect a cycle (i.e., find if the graph contains a cycle). But careful: The condition also requires that the cycle length is at least 4, and all nodes are distinct. In an undirected graph, any cycle will satisfy that. However, could there be a cycle of length 2? Not possible because no multi-edges. So any cycle in an undirected simple graph has length at least 3, but since grid is bipartite, length at least 4. So detecting any cycle in the color subgraph is sufficient? Actually, consider a subgraph that is a tree, no cycles. If there's a cycle, length will be at least 4 due to bipartite nature. So we just need to answer "Yes" if there exists any cycle in the same-color graph.
But wait: In the grid, consider a configuration where two cells of same color are adjacent and also connected via a path of length 2? That would be a triangle? Not possible because grid doesn't have triangles. So indeed any cycle must have at least 4 cells.
Thus problem reduces to: For each cell, do we have a cycle in the same-color subgraph? So we can run DFS for each connected component of a given color, and if we encounter a back edge, then cycle exists.
But there is nuance: The DFS might detect a back edge that yields a cycle of length exactly 4? That's fine. However, could there be a case where the DFS detects a cycle that is not of length >=4 due to some artifact? For example, consider a graph that is not bipartite? But grid subgraph is bipartite, but if we only include same-color cells, can the subgraph be non-bipartite? The underlying grid graph is bipartite, but the subgraph inherits the bipartite property (since it's an induced subgraph? Actually, edges are only between adjacent same-colored cells. The bipartite nature of the whole grid (coloring cells as black/white by (i+j) parity) is preserved: any edge connects a black to a white cell because adjacency changes parity. So any edge is between opposite parity. So any cycle must have even length. The smallest even length is 2? But there is no self-loop, and multiple edges not allowed. So smallest even cycle length is 4. Yes.
Thus detecting any cycle is sufficient.
But careful: The problem requires that the cycle has at least 4 distinct cells. In our subgraph, a cycle would have at least 4 distinct nodes.
Therefore, we can simply do DFS on each component and check for any back edge (i.e., visited node that is not parent). However, need to ensure we don't treat going to the parent as a cycle.
Implementation: visited array n x m. For each cell not visited, start DFS from it, with parent = -1 or previous cell's coordinates. In DFS, for each neighbor (up/down/left/right) that has the same color as the starting cell? Actually, the color is constant for component. We can pass the expected color. For each neighbor within bounds, if neighbor color equals current color, then:
- if not visited, DFS(neighbor, with parent = current cell).
- else if visited and neighbor != parent (the immediate previous), then cycle found.
But careful: In undirected graph DFS, we need to differentiate between visited nodes that are part of the current recursion stack? Not needed because cycles detection in undirected graphs is simple: if you encounter an already visited node that is not the parent, then there is a cycle. But note: In an undirected graph, if there is a cross edge to an already visited node that is not parent but is visited from earlier, it still indicates a cycle? Actually, in undirected DFS, any non-parent visited neighbor indicates a cycle. Consider a tree: there are no cycles, and the only visited neighbor you see (apart from parent) will be not visited because DFS goes depth-first, but once you backtrack, you might encounter a neighbor that was visited earlier in a different branch? For example, in a tree, there is no edge between two nodes not in ancestor relationship. So you won't encounter visited neighbor that is not parent because tree has no cycles. In a graph with cycles, you will encounter such a case. So it's valid.
But we must be careful to avoid false detection due to revisiting the parent from a different path? Actually, we ignore if neighbor == parent. So fine.
But what about a case where we have a square and we start DFS at top-left, go to top-right, then go to bottom-right, then bottom-left, then from bottom-left we see top-left visited and not parent (parent is bottom-right). That's a cycle.
Thus algorithm: For each cell, if not visited, run DFS; if any cycle found, output "Yes". If after all no cycle, output "No".
Complexity: O(n*m) = 2500, trivial.
But wait, sample 2: Input: 3 4 AAAA ABCA AADA Output: No. Let's analyze: We have many A's, but maybe not forming a cycle? Let's test.
But is it always sufficient to detect any cycle? Consider a case where the same color component has a cycle but all cycles have length 4? That's fine.
But could there be a "cycle" that is not simple because of revisiting? Condition says all dots are different, so it's a simple cycle. The cycle we detect using back edge will be a simple cycle (since DFS path is simple and the visited neighbor is part of the current path? Actually, if we encounter a visited neighbor that is not parent but is an ancestor, then the cycle formed is the part of the DFS path from that ancestor to current plus the edge. That's a simple cycle because DFS path is simple. If we encounter a visited neighbor that is not an ancestor but visited earlier in a separate component? That can't happen because if it's visited earlier but not connected? Actually, in an undirected graph, if you start DFS from a component, all nodes in that component will be visited eventually; but when you are exploring, a visited node that is not parent but not in the current recursion stack could be a node that was visited earlier via a different path. However, since the graph is undirected and we are in the same component, if you encounter a visited neighbor that is not parent and not ancestor, that means there is an edge connecting two nodes that are in different branches of the DFS tree, which creates a cycle. In undirected DFS, any non-parent visited neighbor indicates a cycle. The cycle might be not simple? But it will be simple: the edge plus the unique tree path between the two nodes (which exists because it's a tree) forms a cycle. That cycle is simple as long as the tree path does not contain the edge; but the tree path is simple. So it's a simple cycle. So fine.
Thus the simple DFS cycle detection should work.
However, there is a known twist: The cycle must have at least 4 dots, but if we detect a cycle with length 2 or 3? But as argued, not possible. But to be absolutely safe, we could compute the length by depth difference. But not needed.
Given constraints, we can also use BFS or union-find with cycle detection? Union-find can detect cycles in undirected graph by checking if adding an edge connects two already connected nodes; if so, then a cycle exists. That would also work. But we must ensure cycle length condition. But again, any cycle in grid subgraph is length >=4, so it's fine.
Thus solution: For each cell, if not visited, DFS and if cycle found, output Yes.
Implementation details:
We'll have global variables: n,m, grid (list of strings), visited = [[False]*m for _ in range(n)]. Possibly also a parent dictionary or store parent coordinates.
Define DFS(r, c, pr, pc) returning True if cycle found.
Inside DFS: visited[r][c] = True For each neighbor (nr,nc) within bounds: if grid[nr][nc] == grid[r][c]: if not visited[nr][nc]: if DFS(nr,nc, r,c): return True else: if (nr,nc) != (pr,pc): # visited and not parent return True return False
But careful: When we call DFS from start, parent could be (-1,-1). So we need to treat that specially: if (pr,pc) == (-1,-1) then any visited neighbor? Actually, at start, there are no visited neighbors because none visited yet. But after exploring, later we might see visited neighbor that is not parent, that's fine.
One potential issue: The DFS will mark visited as soon as it enters, and then explores neighbors. However, if we encounter a visited neighbor that is not parent, we return True. This detection is valid. However, there is a subtlety: In undirected graph, if we have a cycle, we might detect it multiple times, but fine.
Edge Cases: Suppose the component is a line of length 3; no cycle. DFS will not detect back edge.
Suppose component is a "U" shape that could form a cycle if the ends are adjacent? But that would be a cycle. If ends are not adjacent, no cycle.
So approach works.
Let's test on provided examples.
Example1: 3 4 AAAA ABCA AAAA
Visual: All A's. There is a cycle around the B and C? Actually, all A's form a cycle on border? Let's check. Grid: Row0: AAAA Row1: A B C A? Actually, row1: A B C A -> A at (1,0), B at (1,1), C at (1,2), A at (1,3) Row2: AAAA
All A cells: (0,0)-(0,1)-(0,2)-(0,3); (1,0); (1,3); (2,0)-(2,1)-(2,2)-(2,3). This shape includes a cycle: e.g., (0,0)-(0,1)-(0,2)-(0,3)-(1,3)-(2,3)-(2,2)-(2,1)-(2,0)-(1,0)-(0,0) that's a cycle of length 10, but there is also a smaller cycle? The inner area? The A's around the B and C? Actually, because (1,1) and (1,2) are not A, the A's form a ring around them. That ring is a cycle: (0,1)-(0,2)-(1,2?) no (1,2) not A. Actually need to check connectivity: (0,1) adjacent to (1,1) (B) not A, so (0,1) only connected to (0,0) and (0,2). So the A's form a shape like a donut? Let's see if there is a 4-cycle: (0,0)-(0,1)-(1,1?) no. So maybe the cycle is the border: (0,0)-(0,1)-(0,2)-(0,3)-(1,3)-(2,3)-(2,2)-(2,1)-(2,0)-(1,0)-(0,0). That's a cycle of length 10, all A. So DFS should detect cycle.
Example2: 3 4 AAAA ABCA AADA
Row0: AAAA Row1: A B C A Row2: A A D A? Actually, row2: A A D A? Wait "AADA": indices 0:A,1:A,2:D,3:A. So A cells: (0,0)-(0,1)-(0,2)-(0,3); (1,0); (1,3); (2,0); (2,1); (2,3). D at (2,2). Check connectivity: Are all A's connected? Probably yes, but does it contain a cycle? Possibly the shape is like a "C" missing a cell at (2,2) and (1,1),(1,2). The A's might not form a cycle because the interior is missing some cells that would close the loop. Let's see if we can find a cycle: Possibly (0,0)-(0,1)-(0,2)-(0,3)-(1,3)-(2,3)-(2,1?) not adjacent to (2,3) directly? (2,3) adjacent to (2,2) (D) and (1,3). To go back to start we need a path that doesn't repeat nodes. Might be no cycle. So answer No.
Example3: 4 4 YYYR BYBY BBBY BBBY
We need to see if any color has cycle. Probably Y's have a cycle? The picture described: Y=Yellow, B=Blue, R=Red. Output Yes.
Example4: big grid, Yes.
Example5: 2x13 alphabet, No.
Our algorithm should work.
But I recall known problem "Two Dots" from Codeforces (CF #510 A? Actually, it's a well-known problem). The typical solution is DFS with parent tracking and ensuring cycle length at least 4. Some solutions compute depth difference to verify length >= 4 because there might be a case where back edge is to immediate neighbor that is not parent but yields a cycle of length 2? No. However, there is a nuance: In grid, there could be a situation where the DFS sees a visited neighbor that is not the parent, but the cycle formed might be of length 2? Consider two nodes connected by two different edges? Not possible.
But some discussions mention that due to the grid's nature, a cycle might be detected but it's actually of length 2? Let's think: If the graph had multiple edges between same nodes, not possible. So fine.
Nevertheless, there is a known pitfall: In undirected graph DFS, if you start from a node and you go to neighbor, then from that neighbor you immediately see the original node as visited and not parent? Actually, it would be parent, so ignored. So no.
But what about if you have a configuration like: node A connected to B and C, and B and C are also connected. That's a triangle. In grid, triangle not possible because bipartite property forbids odd cycles. So no triangle.
Thus we are safe.
But wait: There is one more nuance: The cycle must consist of at least 4 dots, and they must be all distinct. However, what about a cycle that is formed by a shape that is not a simple cycle but uses the same color? Our detection detects simple cycles. Good.
Thus solution is straightforward.
But let's double-check sample 3 more thoroughly to ensure DFS detection works.
Given grid: Row0: Y Y Y R Row1: B Y B Y Row2: B B B Y Row3: B B B Y
Let's list Y positions: (0,0)Y, (0,1)Y, (0,2)Y, (1,1)Y, (1,3)Y, (2,3)Y, (3,3)Y. Also (1,1) Y? Row1: "BYBY" -> indices: 0:B,1:Y,2:B,3:Y => Y at (1,1) and (1,3). Row2: "BBBY" -> Y at (2,3). Row3: "BBBY" -> Y at (3,3). So Y connected? Check adjacency: (0,0) adjacent to (0,1) and (1,0) (B) so Y connects to (0,1). (0,1) adjacent to (0,0),(0,2),(1,1). All Y? (1,1) Y. (0,2) adjacent to (0,1),(0,3),(1,2) where (0,3) is R, (1,2) B. So (0,2) only connects to (0,1). (1,1) adjacent to (0,1),(1,0)B,(1,2)B,(2,1)B? (2,1) B, so only (0,1). (1,3) adjacent to (0,3)R, (1,2)B, (2,3)Y. So connects to (2,3). (2,3) adjacent to (1,3),(2,2)B,(3,3)Y. So connects to (1,3) and (3,3). (3,3) adjacent to (2,3),(3,2)B. So Y graph: nodes: (0,0)-(0,1)-(0,2) chain? Actually, (0,0)-(0,1) edge, (0,1)-(0,2) edge, (0,1)-(1,1) edge, (1,3)-(2,3) edge, (2,3)-(3,3) edge. And there is no connection between the two clusters? They are separate: one cluster containing (0,0),(0,1),(0,2),(1,1); another cluster containing (1,3),(2,3),(3,3). Neither seems to have a cycle because they are trees (actually the first cluster: (0,0)-(0,1)-(0,2) line, plus (1,1) attached to (0,1) -> a tree, no cycle; second cluster is a line of three). So no Y cycle. How about B? B positions: many. Possibly B forms a cycle. Let's check B: row1: B at (1,0), (1,2); row2: B at (2,0),(2,1),(2,2); row3: B at (3,0),(3,1),(3,2); also row0? row0 only Y and R, so no. So B cluster: (1,0) adjacent to (0,0) Y, (1,1) Y, (2,0) B => connects to (2,0). (1,2) adjacent to (0,2) Y, (1,1)Y, (1,3)Y, (2,2)B => connects to (2,2). (2,0) adjacent to (1,0)B, (2,1)B, (3,0)B. (2,1) adjacent to (2,0)B,(2,2)B,(1,1)Y,(3,1)B. (2,2) adjacent to (1,2)B,(2,1)B,(2,3)Y,(3,2)B. (3,0) adjacent to (2,0)B,(3,1)B. (3,1) adjacent to (3,0)B,(3,2)B,(2,1)B. (3,2) adjacent to (3,1)B,(2,2)B,(3,3)Y. So B graph is like a shape that may contain a cycle: e.g., (2,0)-(2,1)-(3,1)-(3,0)-(2,0) forms a 4-cycle? Check adjacency: (2,0)-(2,1) yes; (2,1)-(3,1) yes; (3,1)-(3,0) yes; (3,0)-(2,0) yes. All B. So that's a cycle of length 4. So detection will find.
Thus algorithm works.
But I've seen some solutions that keep a depth array and check that when they encounter a visited neighbor that is not the parent, if depth[current] - depth[neighbor] + 1 >= 4 then cycle. They do that to ensure length >=4. However, as we argued, it's unnecessary. But maybe there is a scenario where DFS could detect a "cycle" of length 2 due to something? Let's imagine if there was a self-loop? Not possible. Or maybe if the graph is not simple? All edges are unique.
Nevertheless, to be absolutely safe and align with many solutions, we can implement length check: When we find visited neighbor that is not parent, compute the cycle length as depth[current] - depth[neighbor] + 1. If >=4, then cycle found. But if we think about bipartite grid, the minimum is 4. So it's redundant but harmless.
But is there any case where the depth difference could be 1? That would be a back edge to immediate neighbor that is not parent. For that to happen, there would need to be an edge between two nodes of same depth difference 1 but not parent. That would imply that there are two distinct paths from current node to that neighbor of length 1 (edge) and also a tree path of length 1? Actually, if depth[current] - depth[neighbor] = 1, that means neighbor is the parent if the edge is the tree edge. But if the edge is not the tree edge (i.e., neighbor is visited but not parent), then depth[neighbor] must be less than depth[current] - 1, because if it's exactly depth[current]-1, that neighbor is at the same depth as parent? Let's analyze: In DFS tree, depth increases by 1 along tree edges. So for any node, its depth is defined as distance from root in tree. If we encounter an edge to a visited node v that is not the parent u, then v could be an ancestor (depth less than current depth) or could be a node that has been visited but not an ancestor? In undirected graph, if v is visited but not ancestor, it means that v is in a different branch, but because graph is undirected, there exists a path from root to v via tree edges. That path length is depth[v]. The tree path from root to current is depth[current]. Since v is not ancestor, the unique tree path from root to current and to v diverge at some LCA. So depth[v] could be less than, equal to, or greater than depth[current]? Actually, if v is visited but not ancestor, it's possible that depth[v] could be less than depth[current] (most common is ancestor), but if it's not ancestor, it's visited from another branch earlier. In an undirected DFS, if you encounter a visited node that is not parent, it could be an ancestor (back edge) or could be a node from a previously explored subtree? But since the graph is undirected, when we start DFS from a root, we mark visited as we go. If we see a visited node that is not parent, it means there is an edge connecting the current node to a node that has already been visited. But that node must be either an ancestor (because visited earlier in the recursion stack) or a node that was visited but is not an ancestor? In undirected DFS, typically we only consider visited nodes and ignore parent; any other visited node indicates a cycle. But could it be a node that was visited but is not ancestor? Example: Consider a graph that is a square: vertices A,B,C,D in order. DFS starting at A: go to B, then from B go to C (since adjacency: B connected to A and C, A visited parent, so go to C), then from C adjacency: B (visited parent), D (unvisited) go to D, then from D adjacency: C (parent) and A (visited, not parent). A is an ancestor? A is not direct parent; depth: A(0), B(1), C(2), D(3). A is ancestor (depth 0). So it's an ancestor.
Consider a more complex graph: A triangle? Not in grid. Could we have a graph where a visited node is not ancestor but still visited? For undirected DFS, if we start from root, we never revisit a node that is not ancestor because once we backtrack, that node is still visited, but it's not in the current recursion stack. But we could encounter an edge to such a node. Example: Consider a graph shaped like a "bowtie": two triangles sharing a vertex? Not in grid.
Consider a graph with a cycle and some chords. For undirected DFS, if we are exploring and we encounter a visited node that was visited earlier but is not an ancestor, it's still a cycle? Let's think: Suppose we have a graph: A-B, A-C, B-C, B-D, C-D. That's a K4 minus some? Actually, let's construct: vertices: A,B,C,D. Edges: A-B, A-C, B-C, B-D, C-D. This graph is not bipartite? Check parity? (A,B,C) forms triangle, so not possible in grid. So not relevant.
Given that grid subgraph is planar and bipartite, the only cycles are even cycles. In DFS of such a graph, any back edge will be to an ancestor, because cross edges are not typical in undirected DFS? Actually, in undirected DFS, all edges that are not tree edges are back edges to an ancestor. This is a property: In undirected graph, DFS classifies edges as tree edges or back edges; there are no forward or cross edges because if an edge connects two nodes where one is not ancestor of the other, then when the first node is visited, the other is unvisited (so it becomes tree edge), or if visited, then it must be ancestor because otherwise it would have been visited via a different path that is not ancestor? I recall that in undirected DFS, any edge that is not a tree edge goes to an ancestor in the DFS tree. This is because when we explore from a node, if we encounter a neighbor that has already been visited, then that neighbor must be an ancestor, because if it were not ancestor, then the edge would have been explored as a tree edge when the neighbor was visited (since graph is undirected, the edge would have been seen from the neighbor side earlier, and then when we later visit current, the neighbor would be visited, but it would be a descendant? Actually, let's be precise: In an undirected graph, DFS from a root produces a spanning tree. For any non-tree edge (u,v), one of u or v is an ancestor of the other in the DFS tree. This is a known property. Therefore, any visited neighbor not parent is an ancestor. Good.
Thus depth[current] - depth[neighbor] >= 1 (since not parent, so ancestor depth < current depth). Could it be exactly 1? That would mean neighbor is at depth current-1, which would be the parent if the edge were a tree edge. But if it's not the parent, then it's a different node at same depth as parent? But parent is at depth current-1 and is unique. Could there be another node at depth current-1 that is also an ancestor? Ancestors are nodes on the path from root to current, which includes only parent and higher ancestors. So the set of ancestors at depth current-1 is exactly the parent. So no other node at depth current-1 is an ancestor. Therefore, depth[neighbor] must be <= current-2. So depth difference at least 2. Then cycle length = depth[current] - depth[neighbor] + 1 >= 3. Since cycles are even, minimum even >=4? Actually, if depth difference = 2, then cycle length = 3? Wait: depth[current] - depth[neighbor] = 2 -> length = 3? Let's compute: The cycle consists of the edge (current, neighbor) plus the tree path from neighbor to current. The tree path from neighbor to current goes up from current to parent to grandparent? Actually, if neighbor is ancestor at depth d, current at depth d+2, then the tree path from neighbor to current is neighbor -> child -> ... -> current, which length = (depth[current] - depth[neighbor]) edges = 2. So total cycle edges = 2 + 1 = 3. That would be an odd cycle of length 3, which cannot exist in a bipartite graph. So in a bipartite graph, depth difference must be odd? Actually, since tree is bipartite, the tree path between any two nodes of same color? Let's think: In a bipartite graph, any cycle is even. For a back edge to close a cycle, the length of the tree path plus 1 must be even. The tree path length is depth[current] - depth[neighbor]. Since the edge connects two nodes of opposite parity (because grid bipartite), the depth difference parity? In DFS tree, depth corresponds to distance from root. However, the parity of depth might not align with bipartite color of the grid? But we can argue that in a bipartite graph, if two nodes are adjacent, they must have opposite parity in any bipartite coloring. In the DFS tree, the root's depth is 0. If we assign colors based on parity of depth, that's a valid bipartition? Not necessarily; the tree itself is bipartite, but the original graph's bipartition may not align with depth parity because the graph's bipartition is fixed (by (i+j) mod 2). However, the DFS tree is a subgraph, and its depth parity also gives a bipartition. But two different bipartitions? Actually, any tree is bipartite; one bipartition can be based on depth parity. In the original grid graph, the bipartition is also based on (i+j) mod 2, but depth parity may coincide or not depending on root selection? In a tree, there are two possible bipartitions; depth parity defines one of them. However, for the entire graph, if it's bipartite, there exists a bipartition that works. The DFS tree's depth parity is one such bipartition if we assign root to one side. Actually, for a bipartite graph, any spanning tree's bipartition based on depth (with root assigned a side) will be consistent with the graph's bipartition? Not necessarily: In a bipartite graph, you can assign colors to vertices such that adjacent vertices have different colors. If you root the tree and color by depth parity, that yields a valid 2-coloring of the tree (since tree edges connect nodes of opposite depth parity). But for non-tree edges, they may connect nodes of same depth parity, which would violate bipartiteness. However, the original graph is bipartite, so any non-tree edge must also connect nodes of opposite colors. So if we color by depth parity, non-tree edges should also connect opposite parity, meaning depth parity of the two endpoints must be opposite. So if we encounter a back edge from current to neighbor, then depth[current] and depth[neighbor] must have opposite parity. Since they are opposite parity, depth[current] - depth[neighbor] is odd. Because difference of opposite parity numbers is odd. So depth difference is odd, and at least 1. Since it's odd, the smallest odd number >=1 is 1. But if depth difference =1, neighbor would be parent (since parent has depth current-1, which is opposite parity). However, parent is already considered and we ignore. So the next possible odd depth difference is 3? Because if it's 3, then depth difference =3, cycle length = 4. Could depth difference be 1? That would be parent; ignore. Could depth difference be -1? Not possible because neighbor is ancestor, so depth[neighbor] < depth[current]. So the next is 3. So indeed cycle length >=4. So detection of any back edge that is not parent automatically ensures cycle length >=4 because depth difference must be odd and >1, so at least 3, making cycle length 4. Thus our earlier reasoning is consistent: any non-parent back edge yields cycle length at least 4.
Therefore, we can simply check for non-parent visited neighbor.
One more nuance: When we start DFS on a component, we need to ensure we don't accidentally treat a revisit from a different starting point? Actually, we only start DFS on unvisited cells, so each component is processed once.
Thus solution is simple.
Let's implement in Python.
Pseudo:
def has_cycle(): n, m = map(int, input().split()) grid = [input().strip() for _ in range(n)] visited = [[False]*m for _ in range(n)] directions = [(1,0), (-1,0), (0,1), (0,-1)]
def dfs(r, c, pr, pc): visited[r][c] = True for dr, dc in directions: nr, nc = r+dr, c+dc if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == grid[r][c]: if not visited[nr][nc]: if dfs(nr, nc, r, c): return True else: if not (nr == pr and nc == pc): # found cycle return True return False for i in range(n): for j in range(m): if not visited[i][j]: if dfs(i, j, -1, -1): print("Yes") return print("No")This should work.
But careful: In the else case, visited[nr][nc] is True. However, what if (nr,nc) is actually the parent? We check that it's not parent. But what if (nr,nc) is the parent but we are revisiting from another direction? Actually, we always ignore parent because we check explicitly. Good.
Potential bug: The recursion depth could be up to 2500, which is okay in Python (default recursion limit ~1000, but 2500 may exceed). So we need to increase recursion limit or use iterative DFS. We can set sys.setrecursionlimit(10000). Or we can use stack iterative approach to avoid recursion depth issues.
Given n,m <= 50, the maximum component size is 2500, and recursion depth could be up to 2500 in worst-case (e.g., a line). Python's default recursion limit is 1000, so that could cause RecursionError. So we should either increase recursion limit (setrecursionlimit(10000)) or implement iterative DFS. Both are fine. I'll set recursion limit.
Alternatively, use BFS and maintain parent with depth to detect cycles. But DFS is simpler.
But note: In DFS recursive, we also need to be careful about visited marking before recursion, which we do.
We'll add:
import sys sys.setrecursionlimit(10000)
Now test with examples.
Let's manually simulate first example.
But there is a subtlety: When we call dfs(i,j,-1,-1) and inside we check for visited neighbor that is not parent. At the start, visited[i][j] is set True. Then we explore neighbors. For first cell (0,0), neighbors (0,1) and (1,0) are both A and not visited, so we recurse.
The DFS will eventually find a back edge. Should work.
But I recall a known pitfall: In some solutions, they also keep a "in_stack" or visited array with two states to ensure they don't detect a cycle that is not of length >=4 due to backtracking? Let's examine a potential false positive.
Consider a component shaped like two cells adjacent only to each other (a single edge). DFS from first cell: mark visited. Go to second cell: mark visited. In second cell, neighbors: first cell visited and is parent; no other neighbors. So no cycle.
Consider a component shaped like a "V": three cells: A-B and A-C, where B and C are not adjacent. DFS: start at A, go to B, B returns false, back to A, then go to C. When at C, neighbors: A visited, parent? A is parent? Actually, from C, parent is A, so ignore. So no cycle.
Consider a component that is a square: A-B-C-D-A, but we might traverse in order that the back edge detection finds a cycle length 4 as we described.
What about a component that is a "bowtie" but grid can't.
Thus algorithm is correct.
But I recall reading some Codeforces solutions for "Two Dots" (problem 510B? Actually, it's 510B? No, it's problem 510B? I think it's CF round #274? Let's check: Two Dots is a problem from Codeforces Round #268? Not sure. But typical solution is DFS with parent and checking depth difference >=3? Actually many solutions check that the visited neighbor is already visited and the distance from that neighbor to current (in terms of steps) is at least 3. They compute depth and check depth difference >=3. This ensures cycle length >=4. So essentially same.
But we can simplify: just if visited neighbor and not parent, return True.
But is there any case where visited neighbor not parent but still the cycle length is exactly 2? Could it be that the visited neighbor is the start node and we are at depth 1? Example: Suppose we have component with two nodes connected by two distinct paths? But there is no multi-edge. Could there be a cycle of length 2 via two different edges? Not possible.
But there is another scenario: In undirected graph, if we use DFS and we encounter a visited neighbor that is the parent's parent? That would be depth difference 2. That would be a cycle of length 3, but as argued, impossible in bipartite grid. But we should verify: In a bipartite grid, can we have depth difference 2? That would imply that there is an edge between two nodes of same parity? Because depth parity: root depth 0, its children depth 1, grandchildren depth 2. Edge between current (depth 2) and an ancestor of depth 0 (grandparent) would connect nodes of same parity (both even) if root is even, depth 0 even, depth 2 even. That would be a connection between two cells of same (i+j) parity? In grid, adjacency always flips parity, so an edge between two even parity cells is impossible. Therefore, such a back edge cannot exist. So indeed any back edge must be between nodes of opposite parity, meaning depth difference is odd. So depth difference at least 1 (odd). If depth difference = 1, it's the parent. So next is 3. So safe.
Thus we can just detect any non-parent visited neighbor.
But what about a case where the visited neighbor is not parent but is a node that was visited earlier from a different starting point? That's impossible because we are within the same component and we haven't finished the DFS? Actually, if we start DFS on a component, all nodes in that component will be visited during that DFS. The DFS visits nodes recursively; if we encounter a neighbor that is visited but not parent, it must be an ancestor (as argued), because if it were visited from a different branch earlier but is not ancestor, that would imply that when we first visited that neighbor, we didn't explore the edge to current? But that edge exists, so when we were at that neighbor, we would have considered current as an unvisited neighbor (since current wasn't visited yet) and would have traversed the edge then, making current a child of that neighbor. So that can't happen. So indeed neighbor must be ancestor.
Thus good.
One more nuance: The DFS may detect a cycle early, but we might also need to ensure that the cycle is formed by at least 4 distinct dots. As we've argued, the cycle formed by back edge has length depth difference + 1. Since depth difference is at least 3, length >=4.
But to be absolutely safe, maybe there is a scenario where depth difference is 3 but the path between them includes the parent? Actually the path is along tree edges, which are all distinct. So length 4.
So answer.
Let's test on sample 2 to see if any false detection: Should not.
Thus final code.
But need to be careful about recursion depth: 2500 may exceed default 1000, so setrecursionlimit(10000).
Alternatively, could implement iterative DFS using stack. But recursion is fine.
Edge Cases:
-
n=2, m=2 all same color: grid: AA AA This is a 2x2 block. The graph: four nodes all connected? Actually edges: (0,0) adjacent to (0,1) and (1,0). (0,1) adjacent to (0,0) and (1,1). (1,0) adjacent to (0,0) and (1,1). (1,1) adjacent to (0,1) and (1,0). This graph contains cycles: (0,0)-(0,1)-(1,1)-(1,0)-(0,0) length 4. So output Yes.
-
n=2, m=3 all same color: AAA AAA This 2x3 grid: Let's see if there is a cycle? The graph is like a 2x3 grid. Does it contain a 4-cycle? Yes, any 2x2 subgrid forms a cycle. For example cells (0,0),(0,1),(1,0),(1,1) form a 4-cycle. So yes.
-
n=1, m>=2? But constraints say n,m >=2, so at least 2x2.
-
n=2, m=2 different colors: maybe no cycle.
Thus all good.
Potential pitfalls: The visited array should be marked before recursion to avoid infinite loops.
Now, let's also think about a case where the component is a tree but has a shape that might cause a back edge detection due to something like a node being visited from a different path before we go there? Not possible as argued.
Thus final answer.
I'll produce final solution.
But note: Some languages might require careful handling of parent parameter. In Python, we'll use integer coordinates and compare with (pr,pc). We'll pass (-1,-1) for root.
Implementation details:
-
Use sys.stdin.read or input() for speed; not needed.
-
We can also early exit when cycle found.
Now, double-check with sample 4 to be safe: A large grid. Should output Yes.
Now, potential bug: In the DFS, we might detect a back edge from a node to its parent's parent? That's not parent; but such an edge would be between nodes of same parity? In grid, such edge cannot exist because adjacency always flips parity. So it won't occur. But what if the root is at (0,0) (parity even) and we have an edge between (0,2) and (1,1)? Actually (0,2) parity: 0+2=2 even; (1,1) parity: 1+1=2 even; they are not adjacent because they are diagonal? Actually (0,2) and (1,1) are diagonal, not adjacent. So no.
Thus safe.
However, I've seen a Codeforces editorial that recommends using a visited array with two states: 0 = unvisited, 1 = visiting, 2 = visited. They do DFS and when they encounter a neighbor with state 1 (in current recursion stack) and depth difference >= 3, they output Yes. That's essentially the same.
Given all, we can implement.
Now, ensure to handle input with spaces? The input lines are strings without spaces.
Let's write final code.
But there is a possibility: The DFS might detect a cycle that is of length 4 but the path might not be a cycle in terms of the game? Actually, any simple cycle in the graph qualifies. So fine.
Thus final answer.
Now, produce solution in the required format.
But I recall that some solutions use BFS and check for cycles via union-find with detection of edges that connect already connected nodes. That would also work. But union-find would detect any cycle, regardless of length. However, union-find cannot guarantee that the cycle length is at least 4? Actually, union-find would detect a cycle when adding an edge that connects two nodes already in the same set. That indicates existence of some cycle, but it could be of length 2? Not possible. But could it be a cycle of length 2? Only if there were parallel edges, which don't exist. So union-find is safe. However, union-find might treat the cycle formed by three nodes? Not in grid. So it's safe. But union-find would not be able to differentiate between a cycle that uses only nodes of same color because we only add edges between same-colored cells. But careful: Union-find would consider the whole graph; if there is any cycle in the same-color graph, then when processing edges in some order, eventually we will try to add an edge whose endpoints are already connected. However, we must ensure we don't count trivial cycles that are not of length >=4? In a grid, the smallest cycle is 4, so safe. But one nuance: In a grid, there could be a "cycle" of length 4 formed by four nodes, but union-find might detect a cycle earlier when adding the fourth edge that completes the cycle. That's fine.
But we need to consider each color separately. Could do union-find per color. But simpler is DFS.
Thus final code using DFS.
Now, output "Yes" or "No" exactly as required (capital Y and N).
Let's write:
import sys sys.setrecursionlimit(10000)
def solve(): data = sys.stdin.read().split() if not data: return it = iter(data) n = int(next(it)) m = int(next(it)) grid = [list(next(it).strip()) for _ in range(n)] visited = [[False]*m for _ in range(n)] dirs = [(1,0), (-1,0), (0,1), (0,-1)]
def dfs(r, c, pr, pc): visited[r][c] = True for dr, dc in dirs: nr, nc = r+dr, c+dc if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == grid[r][c]: if not visited[nr][nc]: if dfs(nr, nc, r, c): return True else: if not (nr == pr and nc == pc): return True return False for i in range(n): for j in range(m): if not visited[i][j]: if dfs(i, j, -1, -1): print("Yes") return print("No")if name == "main": solve()
We used list of lists for grid to access faster.
Edge Cases: The parent coordinates (-1,-1) will never match any neighbor coordinate, so the check will treat any visited neighbor as cycle? At the start cell, visited is set True, but its neighbors are not visited yet, so no issue. But if there was a self-loop? Not possible.
Thus final.
Now, I will produce final answer. ```python
import sys
sys.setrecursionlimit(10000) # avoid recursion depth issues
def solve() -> None: data = sys.stdin.read().split() if not data: return it = iter(data) n = int(next(it)) m = int(next(it)) grid = [list(next(it).strip()) for _ in range(n)]
visited = [[False] * m for _ in range(n)] directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(r: int, c: int, pr: int, pc: int) -> bool: """Return True if a cycle is found in the current component.""" visited[r][c] = True for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == grid[r][c]: if not visited[nr][nc]: if dfs(nr, nc, r, c): return True else: # visited neighbour that is not the parent → cycle if not (nr == pr and nc == pc): return True return False for i in range(n): for j in range(m): if not visited[i][j]: if dfs(i, j, -1, -1): print("Yes") return print("No")if name == "main": solve()