matrix.rb

# 题目：
# 给出一个二维数组，从左到右递增，从上到下递增
# 要求给出一个 target，返回是否包含在数组里面？

# Example:
# target = 5, return true.
# target = 20, return false.

# [
#  [1,   4,  7, 11, 15],
#  [2,   5,  8, 12, 19],
#  [3,   6,  9, 16, 22],
#  [10, 13, 14, 17, 24],
#  [18, 21, 23, 26, 30]
#]

# 解答：

def include_target?(a, target)
  min = [0, 0]
  backs = []

  loop do
    if a[min[0]][min[1]] == target
      return true
    elsif a[min[0]][min[1]] > target
      return false
    else
      backs << [min[0], min[1] + 1] if min[1] + 1 < a[min[0]].length
      backs << [min[0] + 1, min[1]] if min[0] + 1 < a.length
      return false if backs.empty?
      min = backs.min_by { |i, j| a[i][j] }
      backs.delete(min)
      puts "index: #{min}, min: #{a[min[0]][min[1]]}, backs: #{backs}"
    end
  end
end

a = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
puts include_target?(a, 5)  # true
puts include_target?(a, 20)  # false
puts include_target?(a, 200)  # false