How do we detect cycles in an undirected graph?

The task involves determining if an undirected graph, where nodes represent cells and edges represent adjacent cells with the same color, contains any cycles.

Run dfs / bfs, if an edge leads you to a visited node, then there must be a cycle.

from collections import deque

def is_valid_cell(x, y, n, m):
    return 0 <= x < n and 0 <= y < m

def has_cycle(grid, n, m):
    # directions to move in the grid
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    # visited set to track visited cells
    visited = set()

    # perform bfs from each cell
    for i in range(n):
        for j in range(m):
            if (i, j) in visited:
                continue

            color = grid[i][j]
            q = deque([(i, j, None)])

            while q:
                x, y, prev = q.popleft()
                if (x, y) in visited:
                    # cycle found
                    return True

                visited.add((x, y))

                for k in range(4):
                    nx, ny = x + dx[k], y + dy[k]

                    if not is_valid_cell(nx, ny, n, m) or grid[nx][ny] != color:
                        continue

                    if (nx, ny) != prev:
                        q.append((nx, ny, (x, y)))

    # no cycle found
    return False

# read input
n, m = map(int, input().split())
grid = [input() for _ in range(n)]

# check if there is a cycle
if has_cycle(grid, n, m):
    print("Yes")
else:
    print("No")

def is_valid(x, y, n, m):
    return x >= 0 and x < n and y >= 0 and y < m

def has_cycle(grid):
    visited = set()

    # direction vectors for neighbors
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if (i, j) not in visited:
                stack = [(i, j, None)]

                while stack:
                    x, y, parent = stack.pop()

                    visited.add((x, y))

                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]

                        if is_valid(nx, ny, len(grid), len(grid[0])) and grid[nx][ny] == grid[x][y]:
                            if (nx, ny) not in visited:
                                stack.append((nx, ny, (x, y)))
                            elif (nx, ny) != parent:
                                return True

    return False

# read input
n, m = map(int, input().split())
grid = [input() for _ in range(n)]

# check if there is a cycle
if has_cycle(grid):
    print("Yes")
else:
    print("No")

From the input we are given that the total length of our path doesn’t exceed 10^5.

How can we find the shortest path in an undirected graph.

This problem involves finding the shortest path between two points on a chess field, given a set of allowed cells. We can model the chess field as an undirected graph and use breadth-first search (BFS) to find the shortest path between the two points. To ensure that the king only moves along the allowed cells, we can represent the allowed cells as a set and only consider a path if all of its cells are in the set of allowed cells. By using BFS, we guarantee that we find the shortest path between the two points, as BFS explores nodes in order of their distance from the starting node. If there is no path between the two points along the allowed cells, we can detect this by the fact that the BFS algorithm does not visit the ending node.

from collections import deque

def main():
    # Input
    x0, y0, x1, y1 = map(int, input().split())
    n = int(input())
    allowed = set()
    for i in range(n):
        r, a, b = map(int, input().split())
        for i in range(a, b + 1):
            allowed.add((r, i))

    # BFS
    queue = deque([(x0, y0)])
    visited = set([(x0, y0)])
    neighbors = [[-1, 0], [0, -1], [0, 1], [1, 0],
                 [-1, 1], [1, -1], [1, 1], [-1, -1]]
    level = 0
    while queue:
        level += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            if (x, y) == (x1, y1):
                return level - 1
            for dx, dy in neighbors:
                nx, ny = x + dx, y + dy
                if (nx, ny) in allowed and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))

    # No path found
    return -1

print(main())