Блог пользователя Easy_

Задача на лабиринты (графы)
Автор Easy_, 12 лет назад, По-русски

Всем привет, вот дана такая задача: Lines

Я ее решил через обычный волновой алгоритм, представив лабиринт как матрицу NxN.

Но т.к. задача в разделе "Теория графов", значит ее нужно как-то через графы решить. Так вот, хотел бы спросить, а как?

Каким образом представить граф, и какая идея решения будет?

Спасибо.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

По факту, вы искали путь от одной вершины графа к другой. Вершины графа в данном случае -- проходимые клетки матрицы, а ребра существуют между вершинами, в которых соответствующие им клетки соседние. Отсюда и есть теория графов.

→ Ответить
  • »
    »
    12 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо, я думал еще можно считать лабиринт как матрицу смежности, и просто обычным bfs'ом пройтись.

    А какие идеи есть, что бы не матрицей смежности представлять данные, а списком?

    Я просто хочу реализовать это так:

    сразу при чтении входных данных формировать список смежных вершин.

    → Ответить
    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Ну можно сделать функцию, принимающую координаты клетки и возвращающую число, уникальное для каждой клетки. Например, f(i,j)=i*(n+1)+j; Ну а дальше просто пробрасываем ребра между соседними вершинами...

      → Ответить
    • »
      »
      »
      12 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      Так а зачем вам в явном виде хранить граф?. Вы же и так знаете, в какие вершины у вас есть ребра. Вы это и использовали, почти наверняка, в своем решении.. Вы знаете, что из вершины, соответствующей клетке (x,y), есть ребра в вершины, которые соответствуют клеткам (x+1,y),(x-1,y),(x,y+1),(x,y-1), если эти вершины существуют.

      → Ответить