Submission #791394

---

Source Code Expand

nm = gets.split.map {|i| i.to_i}
N = nm[0]
M = nm[1]

rules = {}
N.times do |i|
  rules[(i+1).to_s] = []
end

M.times do
  xy = gets.split.map {|i| i.to_i}
  rules[xy[0].to_s].push xy[1]
end

rules.each do |k,v|
  v.sort!
end

def search(current, arr, rules)
  current_rule = rules[current.to_s]
  if arr.length == 0 && current_rule.length == 0
    return 1
  end
  
  if !current.nil? && current_rule && current_rule.length > 0
    rule_index = 0
    arr_index = 0

    while(arr_index < arr.length && rule_index < current_rule.length)
      if current_rule[rule_index] > arr[arr_index]
        arr_index += 1
      elsif current_rule[rule_index] == arr[arr_index]
        rule_index += 1
      else
        break
      end
    end

    unless rule_index == current_rule.length
      return 0
    end
  end

  sum = 0
  arr.each.with_index do |i, index|
    if index == 0
      sum += search(i, arr[1..arr.length-1], rules)
    elsif index == arr.length - 1
      sum += search(i, arr[0..arr.length-2], rules)
    else
      sum += search(i, arr[0..index-1].concat(arr[(index+1)..arr.length-1]), rules)
    end
  end

  sum
end

numbers = (1..N).map {|i| i}
puts search(nil, numbers, rules)

Submission Info

Judge Result