Решите задачу на Python

Question

Решите задачу на Python

Саша Жарков Ученик (81), открыт 5 часов назад

На гранях кубика написаны цифры от 1 до 6. Муравей хочет обойти все грани куба, переползая с одной на другую, так, чтобы посетить грани с цифрами от 1 до 6 по порядку. То есть, начать с грани 1, переползти на грань 2, потом с нее на грань 3, и т. д.

Помогите ему понять, может ли он это сделать.

Входные данные:
Ввод содержит три строки по четыре символа в каждой — описание развертки кубика в следующем формате:

. X . .
X X X X
. X . .
Здесь каждый X заменяется цифрой от 1 до 6. Гарантируется что каждая цифра встречается ровно один раз.

Выходные данные
Если грани можно обойти по порядку до 1 до 6, выведите Yes, если нельзя, то выведите No.

Answer 1

 def can_traverse_cube(layout): 
    faces = {} 
    for i in range(3): 
        for j in range(4): 
            if layout[i][j] != '.': 
                faces[int(layout[i][j])] = (i, j) 
     
    neighbors = { 
        (0, 1): [(1, 0), (1, 1), (1, 2), (1, 3)], 
        (1, 0): [(0, 1), (1, 1), (2, 1)], 
        (1, 1): [(1, 0), (0, 1), (1, 2), (2, 1)], 
        (1, 2): [(1, 1), (1, 3), (2, 1), (0, 1)], 
        (1, 3): [(1, 2), (0, 1), (2, 1)], 
        (2, 1): [(1, 0), (1, 1), (1, 2), (1, 3)], 
    } 
     
    graph = {i: [] for i in range(1, 7)} 
    for num, coord in faces.items(): 
        for neighbor in neighbors[coord]: 
            if neighbor in faces.values(): 
                neighbor_num = next(k for k, v in faces.items() if v == neighbor) 
                graph[num].append(neighbor_num) 
     
    def dfs(current, target, visited): 
        if current == target: 
            return True 
        visited.add(current) 
        for neighbor in graph[current]: 
            if neighbor not in visited: 
                if dfs(neighbor, target, visited): 
                    return True 
        return False 
 
    for i in range(1, 6): 
        if not dfs(i, i + 1, set()): 
            return "No" 
    return "Yes" 
 
 
def print_layout(layout): 
    print("\nРазвертка куба:") 
    for row in layout: 
        print(" ".join(row)) 
    print() 
 
 
print("Введите развертку куба (3 строки по 4 символа, используйте '.' для пустых клеток):") 
layout = [input().strip().split() for _ in range(3)] 
 
print_layout(layout) 
 
result = can_traverse_cube(layout) 
if result == "Yes": 
    print("Yes\n ✅ Муравей может обойти грани куба в порядке от 1 до 6.") 
else: 
    print("No\n ❌ Муравей не может обойти грани куба в порядке от 1 до 6.")