Нахождение минимального количества шагов, необходимых для перехода от источника к терминалу

Привет всем, это мой первый пост, так что, пожалуйста, критикуйте мой пост, если есть что-нибудь.

Я сделал программу, предназначенную для решения задачи программирования на open.kattis.com, Вот. Он должен действовать, как сказано в заголовке, но с условиями, что каждый обход следует правилам «коня» из шахмат, то есть плюс / минус два столбца / строки и плюс / минус один столбец / строка.

  1. Метод _read: я попытался решить эту проблему, создав класс Node и передав координаты и данные char в каждый экземпляр объекта Node для каждой координаты.

  2. _adjacencify метод: После этого я обнаружил смежности (соседей) всех объектов Node с вышеупомянутым условием шахматного коня.

  3. _jump: наконец, я использовал реализацию BFS, чтобы найти кратчайший путь от источника (корня) до терминала (здесь обозначен как «K»).

  4. find_path: завершает все.

Вот код, который у меня получился:

class Nite
  #attr_accessor :char, :col, :row
  class Node
    attr_accessor :char, :col, :row, :disc, :parent
    attr_reader :adjies
    def initialize(char, col, row)
      @char = char
      @col = col
      @row = row
      @adjies = [] # adjacencies
      @disc = false
      @parent = nil
    end
    def add(value)
      @adjies << value
    end
  end

  def _read
    # assign each coord. to a Node-object
    n = gets.to_i
    nodes = Array.new
    n.times do |x|
      temp = gets.strip.to_s
      temp.size.times do |y|
        node = Node.new(temp[y], x, y)
        nodes << node
      end
    end

    nodes
  end

  def _adjacencify(nodes)

    nodes.each do |x|
      nodes.each do |y|
        if y.col == x.col && y.row == x.row || y.char == "https://codereview.stackexchange.com/questions/255098/#"
          next
        end

        # logic

        if x.row == (y.row - 1) # y.row + 1

          if x.col == (y.col - 2) # y.col + 2
            x.add(y) # (col+2, row+1)
          elsif x.col == (y.col + 2) # y.col - 2
            x.add(y) # (col-2, row+1)
          end
    
        elsif x.row == (y.row + 1) # y.row - 1

          if x.col == (y.col - 2) # y.col + 2
            x.add(y) # (col+2, row-1)
          elsif x.col == (y.col + 2) # y.col - 2)
            x.add(y) # (col-2, row-1)
          end
    
        end

        if x.row == (y.row - 2) # y.row + 2

          if x.col == (y.col - 1) # y.col + 1
            x.add(y) # (col+1, row+2)
          elsif x.col == (y.col + 1) # y.col - 1
            x.add(y) # (col-1, row+2)
          end
    
        elsif x.row == (y.row + 2) # y.row - 2

          if x.col == (y.col - 1) # y.col + 1
            x.add(y) # (col+1, row-2)
          elsif x.col == (y.col + 1) # y.col - 1
            x.add(y) # (col-1, row-2)
          end

        end

      end
    end

    nodes
  end

  def _jump(nodes)

    nodes = _adjacencify(nodes)

    q = Queue.new
    root = nodes[0]
    root.disc = true
    q << root

    while !q.empty? do
      v = q.pop
      if v.char == 'K'
        steps = 0
        until v.parent == nil do
          if !v.nil?
          end
          steps += 1
          v.parent = v.parent.parent
        end
        return steps
      end
      v.adjies.each do |w|
        if w.disc == false
          w.parent = v
          w.disc = true
          q << w
        end
      end
    end
    return -1

  end

  def find_path
    _jump(_read)
  end

end

nite = Nite.new
puts nite.find_path

Я, конечно, подозреваю, что метод _adjacencify занимает очень много времени, а некоторые циклы – слишком много времени. Я не справился с требованием времени <1,00 с, чтобы пройти испытание.

я хочу все типы критики моего кода, и мне нужны советы, а также, если кто-то хочет, различные реализации, которые работают лучше. В частности, я хочу критиковать соглашение Ruby, учитывая, что я исхожу из опыта работы с Java и Python, и я достаточно новичок в Ruby.

Скажите, пожалуйста, нужно ли мне отредактировать что-нибудь в этом посте, чтобы было понятнее.

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *