def match(board, char, row, col)
  return false if row < 0 or row >= board.length
  return false if col < 0 or col >= board.first.length
  return board[row][col] == char
end

def _exist(board, word, row, col)
  return true if word.empty?
  [[row-1, col], [row+1, col], [row, col-1], [row, col+1]].each { |cur_row, cur_col|
    if (match(board, word[0], cur_row, cur_col))
      letter = board[cur_row][cur_col]
      board[cur_row][cur_col] = nil
      return true if (_exist(board, word[1..-1], cur_row, cur_col))
      board[cur_row][cur_col] = letter
    end
  }
  return false
end

def exist(board, word)
  return true if word.empty?

  board.each_index { |row|
    board[row].each_index { |col|
      if (board[row][col] == word[0])
        letter = board[row][col]
        board[row][col] = nil
        return true if _exist(board, word[1..-1], row, col)
        board[row][col] = letter
      end
    }
  }

  return false
end