Kevin Shepherd's solution:

#include <iostream>
#include <map>
#include <set>
#include <fstream>
#include <string>
#include <list>

#define MAX_CELL_DIM 0xFF
#define MAX_TARGET_COUNT 1
#define MAX_X_DIM	1024
#define MAX_Y_DIM	1024

#define STATE_ARRAY_SIZE	0x4000000

#define TARGET_MASK	0x3FFFFFFF
#define TARGET_BITS	0x40000000
#define TARGET_ROLL	30

#define POS_X_MASK	0xC00FFFFF
#define POS_X_BITS	0x3FF
#define POS_X_ROLL	20

#define POS_Y_MASK	0xFFF003FF
#define POS_Y_BITS	0x3FF
#define POS_Y_ROLL	10

#define VEL_X_MASK	0xFFFFFC1F
#define VEL_X_BITS	0xF
#define VEL_X_SIGN	0x200
#define VEL_X_ROLL	5

#define VEL_Y_MASK	0xFFFFFFE0
#define VEL_Y_BITS	0xF
#define VEL_Y_SIGN	0x10
#define VEL_Y_ROLL	0

#define VEL_MASK 0x000001EF

unsigned long target_mask = 0;

struct CellCoord
	{
	unsigned char	x, y;
	bool operator<(const CellCoord & __other)	const
		{
		return (x < __other.x?true:(x > __other.x?false:y < __other.y));
		}
	bool operator==(const CellCoord & __other)	const
		{
		return (x == __other.x && y == __other.y);
		}
	};

class State
	{
public:
	State()
	:packed(0)
		{}
	State(const State & __other)
	:packed(__other.packed)
		{}
	State & operator=(const State & __other)
		{
		packed = __other.packed;
		}


	bool operator<(const State & __other)	const
		{
		return packed<__other.packed;
 		}
	bool operator==(const State & __other)	const
		{
		return (packed == __other.packed);
		}
	void	set_packed(unsigned long __packed)
		{
		packed = __packed;
		}
	void	set_target(unsigned char )
		{
		packed |= TARGET_BITS;
		}
	unsigned long get_targets() const
		{
		return packed >> TARGET_ROLL;
		}
	void	set_targets(unsigned long __targets)
		{
		packed &= TARGET_MASK;
		packed |= (__targets << TARGET_ROLL);
		}
	bool	all_targets() const
		{
		return ((packed & TARGET_BITS) != 0);
		}
	short get_x() const
		{
		return (short)((packed >> POS_X_ROLL) & POS_X_BITS);
		}
	void set_x(short __x)
		{
		packed &= POS_X_MASK;
		packed |= ((unsigned long)__x << POS_X_ROLL);
		}
	short get_y() const
		{
		return (short)((packed >> POS_Y_ROLL) & POS_Y_BITS);
		}
	void set_y(short __y)
		{
		packed &= POS_Y_MASK;
		packed |= ((unsigned long)__y << POS_Y_ROLL);
		}
	short get_vel_x() const
		{
		return (packed & VEL_X_SIGN)?-(short)((packed >> VEL_X_ROLL) & VEL_X_BITS):+(short)((packed >> VEL_X_ROLL) & VEL_X_BITS);
		}
	void set_vel_x(short __vx)
		{
		packed &= VEL_X_MASK;
		if (__vx < 0)
			{
			packed |= VEL_X_SIGN;
			__vx = - __vx;
			}
		if (__vx > 10)
			__vx = 10;
		packed |= ((unsigned long)__vx << VEL_X_ROLL);
		}
	short get_vel_y() const
		{
		return (packed & VEL_Y_SIGN)?-(short)((packed >> VEL_Y_ROLL) & VEL_Y_BITS):+(short)((packed >> VEL_Y_ROLL) & VEL_Y_BITS);
		}
	void set_vel_y(short __vy)
		{
		packed &= VEL_Y_MASK;
		if (__vy < 0)
			{
			packed |= VEL_Y_SIGN;
			__vy = - __vy;
			}
		if (__vy > 10)
			__vy = 10;
		packed |= ((unsigned long)__vy << VEL_Y_ROLL);
		}
	bool has_vel() const
		{
		return ((packed & VEL_MASK) != 0);
		}

	unsigned long	packed;
	};

struct Active
	{
	State	st;
	std::string	path;
	};

typedef std::list<Active>	ActiveList;

unsigned long state_array[STATE_ARRAY_SIZE];
ActiveList	current_states;
unsigned char cell_map[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
unsigned long target_baseline;
unsigned long _cell_width = 0, _cell_height = 0;
unsigned long state_count = 0;

bool is_set_state(State _st)
	{
	return ( state_array[_st.packed >> 5] & (1 << (_st.packed & 0x1F) ) ) != 0;
	}

void set_state(State _st)
	{
	state_array[_st.packed >> 5] |= (1 << (_st.packed & 0x1F) );
	}

bool transition (unsigned char __impulse, const Active & __from);

int main(int _argc, char * _argv[])
	{
	if (_argc < 2 )
		{
		std::cerr << "Usage: " << _argv[0] << " <map>" << std::endl;
		return 1;
		}
	std::ifstream _in(_argv[1]);
	_in >> _cell_width;
	_in >> _cell_height;
	std::cout << "Cells: " << _cell_width << "x" << _cell_height << std::endl;
	if (_cell_width == 0 || _cell_width > MAX_CELL_DIM ||
		_cell_height == 0 || _cell_height > MAX_CELL_DIM)
		{
		std::cerr << "Wrong cell dimensions 0 < cell < " << MAX_CELL_DIM << std::endl;
		return 1;
		}
	if (_cell_width * 10 > MAX_X_DIM || _cell_height * 10 > MAX_Y_DIM)
		{
		std::cerr << "Map too large " << _cell_width * 10 << "x" << _cell_height * 10 << " > " << MAX_X_DIM << "x" << MAX_Y_DIM << std::endl;
		return 1;
		}
	std::string _line;
	unsigned long _target_max = 0;
	Active _initial_state;
	CellCoord	_cell_pos;
	_cell_pos.y = 0;
	memset(cell_map, 1, sizeof(unsigned char [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
	memset(state_array, 0, sizeof(unsigned long [STATE_ARRAY_SIZE]));
	unsigned long _open_cell_count = 0;
	while (_in.good() && _cell_pos.y < _cell_height)
		{
		std::getline(_in, _line);
		if (_line.size() >= _cell_width)
			{
			std::cout << _line << std::endl;
			for (_cell_pos.x = 0; _cell_pos.x < _cell_width; ++ _cell_pos.x)
				{
				switch (_line[_cell_pos.x])
					{
				case '#':
					cell_map[_cell_pos.x][_cell_pos.y] = 1;
					break;
				case 'O':
					cell_map[_cell_pos.x][_cell_pos.y] = 2;
					_initial_state.st.set_x(_cell_pos.x * 10);
					_initial_state.st.set_y(_cell_pos.y * 10);
					++ _open_cell_count;
					break;
				case '+':
					++ _target_max;
					cell_map[_cell_pos.x][_cell_pos.y] = (unsigned char)(_target_max + 2);
					++ _open_cell_count;
					break;
				case ' ':
				default:
					cell_map[_cell_pos.x][_cell_pos.y] = 0;
					++ _open_cell_count;
					break;
					}
				}
			++ _cell_pos.y;
			}
		}
	if (_target_max > MAX_TARGET_COUNT)
		{
		std::cerr << "Too many targets " << _target_max << " > " << MAX_TARGET_COUNT << std::endl;
		return 1;
		}
	else
		{
		std::cout << "Target count " << _target_max << " Open Cell Count: " << _open_cell_count << std::endl;
		}
	target_mask = 0xFFFFFFFF >> (32 - _target_max);
	std::cout << "Target mask " << target_mask << std::endl;
	set_state(_initial_state.st);
	current_states.push_back(_initial_state);
	bool _found = false;
	unsigned long _iter = 0;
	unsigned long _prev_target_baseline = 0;
	while (!_found)
		{
		current_states.push_back(Active());
		ActiveList::iterator _partition = current_states.end();
		-- _partition;
		target_baseline = 0xFFFFFFFF;
		for (ActiveList::iterator _ax = current_states.begin(); _ax != _partition; ++ _ax)
			{
			if (transition(0, * _ax))
				{
				_found = true;
				break;
				}
			if (transition(1, * _ax))
				{
				_found = true;
				break;
				}
			if (transition(2, * _ax))
				{
				_found = true;
				break;
				}
			if (transition(4, * _ax))
				{
				_found = true;
				break;
				}
			if (transition(3, * _ax))
				{
				_found = true;
				break;
				}
			if (transition(6, * _ax))
				{
				_found = true;
				break;
				}
			}
		current_states.erase(current_states.begin(), ++ _partition);
		if (target_baseline != _prev_target_baseline)
			{
			State _t_from, _t_to;
			_t_from.set_targets(_prev_target_baseline);
			_t_to.set_packed(0xFFFFFFFF);
			_t_to.set_targets(_prev_target_baseline);
			std::cout << "Erasing Target base: " << _prev_target_baseline << std::endl;
			// states_reached.erase(states_reached.lower_bound(_t_from), states_reached.upper_bound(_t_to));
			_prev_target_baseline = target_baseline;
			}

		++ _iter;
		std::cout << '.';
			{ // report
			unsigned char report_map[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
			memcpy(report_map, cell_map, sizeof(unsigned char [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
			unsigned long _active_count = 0;
			for (ActiveList::iterator _ax = current_states.begin(), _ay = current_states.end(); _ax != _ay; ++ _ax)
				{
				unsigned char _content = report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ];
				if (_content != 0xFF)
					{
					if ((* _ax).st.all_targets())
						report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ] = 0xFF;
					else
						report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ] = 0xFE;
					}
				++ _active_count;
				}
			std::cout << std::endl;
			for (unsigned char y = 0; y < _cell_height; ++ y)
				{
				for (unsigned char x = 0; x < _cell_width; ++ x)
					{
					unsigned char _content = report_map[ x ][ y ];
					switch (_content)
						{
					case 0:
						std::cout << ' ';
						break;
					case 1:
						std::cout << '#';
						break;
					case 2:
						std::cout << 'O';
						break;
					case 0xFE:
						std::cout << '*';
						break;
					case 0xFF:
						std::cout << 'T';
						break;
					default:
						std::cout << '+';
						break;
						}
					}
				std::cout << std::endl;
				}
			std::cout << "Iteration: " << _iter << " Count: " << _active_count << " State Count: " << state_count << std::endl;
			}
		}
	if (_found)
		{
		std::cout << "Solution: " << current_states.back().path << std::endl;
		}
	return 0;
	}

bool transition (unsigned char __impulse, const Active & __from)
	{
	Active _to(__from);
	switch (__impulse)
		{
	case 0:
		_to.st.set_vel_y(_to.st.get_vel_y() + 1);
		break;
	case 1:
		_to.st.set_vel_x(_to.st.get_vel_x() - 2);
		_to.st.set_vel_y(_to.st.get_vel_y() + 1);
		break;
	case 2:
		_to.st.set_vel_y(_to.st.get_vel_y() - 1);
		break;
	case 3:
		_to.st.set_vel_x(_to.st.get_vel_x() - 2);
		_to.st.set_vel_y(_to.st.get_vel_y() - 1);
		break;
	case 4:
		_to.st.set_vel_x(_to.st.get_vel_x() + 2);
		_to.st.set_vel_y(_to.st.get_vel_y() + 1);
		break;
	case 6:
		_to.st.set_vel_x(_to.st.get_vel_x() + 2);
		_to.st.set_vel_y(_to.st.get_vel_y() - 1);
		break;
		}

	short _new_x, _new_y;
	bool _x_two_col, _y_two_col;
	do
		{
		_new_x = _to.st.get_x() + _to.st.get_vel_x();
		if (_new_x >= 0)
			{
			_new_y = _to.st.get_y() + _to.st.get_vel_y();
			if (_new_y >= 0)
				{
				CellCoord	_cell_pos;
				_cell_pos.x = _new_x / 10;
				if (_cell_pos.x < _cell_width)
					{
					_cell_pos.y = _new_y / 10;
					if (_cell_pos.y < _cell_height)
						{
						unsigned char _cell_content = cell_map[_cell_pos.x][_cell_pos.y];
						if (cell_map[_cell_pos.x][_cell_pos.y] != 1)
							{	
							_x_two_col = ((_new_x % 10) != 0);
							_y_two_col = ((_new_y % 10) != 0);
							bool _collision = false;
							if (_x_two_col)
								{
								++ _cell_pos.x;
								if (cell_map[_cell_pos.x][_cell_pos.y] == 1)
									_collision = true;	
								if (_y_two_col)
									{
									++ _cell_pos.y;
									if (cell_map[_cell_pos.x][_cell_pos.y] == 1)
										_collision = true;	
									-- _cell_pos.y;
									}
								-- _cell_pos.x;
								}
							if (_y_two_col)
								{
								++ _cell_pos.y;
								if (cell_map[_cell_pos.x][_cell_pos.y] == 1)
									_collision = true;	
								-- _cell_pos.y;
								}
							if (!_collision)
								break;
							}
						}
					}
				}
			}
		_to.st.set_vel_x(_to.st.get_vel_x() / 2);
		_to.st.set_vel_y(_to.st.get_vel_y() / 2);
		}
		while ( _to.st.has_vel() );

	_new_x = _to.st.get_x() + _to.st.get_vel_x();
	_new_y = _to.st.get_y() + _to.st.get_vel_y();
	_x_two_col = ((_new_x % 10) != 0);
	_y_two_col = ((_new_y % 10) != 0);
	CellCoord	_cell_pos;
	_cell_pos.x = _new_x / 10;
	_cell_pos.y = _new_y / 10;

	_to.st.set_x(_new_x);
	_to.st.set_y(_new_y);

	bool _home = false;
	unsigned char _cell_content = cell_map[_cell_pos.x][_cell_pos.y];
	if (_cell_content == 2)
		_home = true;	
	else if ( _cell_content > 2)
		{
		_to.st.set_target(_cell_content - 3);
		}
	if (_x_two_col)
		{
		++ _cell_pos.x;
		_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
		if (_cell_content == 2)
			_home = true;	
		else if ( _cell_content > 2)
			{
			_to.st.set_target(_cell_content - 3);
			}
		if (_y_two_col)
			{
			++ _cell_pos.y;
			_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
			if (_cell_content == 2)
				_home = true;	
			else if ( _cell_content > 2)
				{
				_to.st.set_target(_cell_content - 3);
				}
			-- _cell_pos.y;
			}
		-- _cell_pos.x;
		}
	if (_y_two_col)
		{
		++ _cell_pos.y;
		_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
		if (_cell_content == 2)
			_home = true;	
		else if ( _cell_content > 2)
			{
			_to.st.set_target(_cell_content - 3);
			}
		-- _cell_pos.y;
		}
	if (_home && !_to.st.all_targets())
		_home = false;
	if (!is_set_state(_to.st))
		{
		set_state(_to.st);
		++ state_count;
		target_baseline &= _to.st.get_targets();

		char _buf[2];
		sprintf(_buf, "%d", (int)__impulse);
		_to.path.append(_buf);

		current_states.push_back(_to);
		}
	return _home;
	}
/*
Iteration: 270 Count: 1087958 State Count: 60960443
.
      TTTTTTTTTTTTTTTTTTTTTT          TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
       TTTTTTTTTTTTTTTTTTTTT          TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
       TTTTTTTTTTTTTTTTTTTTT          TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
       TTTTTTTTTTTTTTTTTTTTT          TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT#TTTT
        TTTTTTTTTTTTTTTTTTTT          TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
         #TTTTTTTTTTTTTTTTTTO        ### #TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT     #
         #T ###TTTTTTTTTTT#####  # # ## #TTTTTTTTTTTTTTTTTTTTTTTTTT#TTTT#TTTTTTT
         #T####TTTTTTTTTTT### # ##  #  ###TTTTTTTTTTTTTTTTTTTTTTTT#TT###### TTTT            #
    ### #TTTTT#TTTTT#### ###### ####  ###TT#TT#TTTTTTTTTTTTTTTTTTTTTT#T #####TTT####  ##   # # ## #
  #   # # #TT#TTTTT############# ##  ##  # TT##T#TTTTTTTTTTTTTTTTT#TTTT  ##TTTTT# TT ##  ## # #   ##
      #    #TT ##T################ #    # #TTTTTTTTTT##TTTTTT#TTTTT####  #TTTTTTT#T#####  ## ##
 #       ## #T  TT ##################### ###TTTTTTTTTTT##TTTT##TT## ##  # #TTTTTTT##### # #    ##  #
  ##  # #   # #TTTT#############################T####T####TTT ###   ## ####  TTTTTTT### ###  # #   #
   #     #  TT TTTT# ########################  TT## #### ##TT###### #######  ##TTTTTT## ##    #### #
#  # # ##   TT#TT#T## ######################## #### # ####TTT# ### # # #######TTTTTTTT#T ##T# ######
#      #####TT##TTT## ######################## ###### # ##        # # #  # # ##TTTTTTT#T#TTT#######
     # #TT  #T TTT  #######################  ######## # # #  T T   #####  # # TTT# #TT#TT   ########
 #    #TT # TTTTT T########################### #######  ###  TT#   #######T####TT####TT ##  # #####
   # #  T##  TTTT#   #  ##############################   ###       ### #   TTTTTTTTTTTT###    ######
  ##   #TT###TT#T#T# #    ##########################  # #### ##    ##  ## T TTTTTTTTT## #   ######
  #  ###TTT#TTTTT   #   # ########################## #  # # #    #    #    ##TTTTT#TT### ##  # # ###
 #   ####TT  #TT#T    TT ##  ######### ############# #  #####        ##    # #TT#TTTT###  ##   #####
     #TTT###T#   T    TT#       ## #          ###### ##   # #   #   #    #  #TTT#TT#T#####    ######
#    ##TTTTTT# # #                   #    #  ########  #### #  ##       ### ####TTTTT ###   #  #####
## ###  ##TTT# ####                       ## ############## # ##   #       #  ######## #    ## #####
       ##TTT# ######        ########       #  ################ #   #T  ##  ### ### #  #    #    ####
   ### #TT #   ########     #######  ##    ##   ###########       #TT # # #  ###  ## #  ####   #####
    # ### #     ######      #########  #    #    #########        #TT # ### # ####     ##   #    ###
        ## #### ####### #   #  ###### #          ##########    #   #TTT#T#T###T###  # ##    ##  # ##
     #####  # ################  # ##  #####       #### ## #  # #  #TTTTTTTTTTTT########## #  #   ##
    # #   ##    ############################  #       #        # ###TTTTT#TTTTT############ ###   #
        # ###   ############### ############         #          ## #TT#TTTT#TTT###########
  ##  # ### #   # ##########################                       ##TTT TT#################      #
 ############## ##############   ###########   ####      #    # ####TTTT# #TT############# ###
# ## # #######     ##########    ####### #      ##    ## ### ##   ## TTT###TTTT##########    #   # #
   #  ######## #   ########## #   ####         ## #    ####    # ## #TTTT##TTTT###### #     ###  #
   ##  ######## ##  ## ######  ####       ##     ###  ## # ## ##### # TTT#TTTT######## #   ###     #
    #  ############## #########  #           #    # #  #  # ##  #######TTTTTT#T# ###### # ###  ## #
    #   ############### ######   #        # #    #### #  #### ########TTTTTTT#T# ## #   #    #  ##
    #  ################ ####### #       # # #    #####  #######   ###TTTTTTTTTTT### ## ##     #####
       ################ ######         ## #  #    ## ##########   ##   ####TTTTT##TT #  ##  #####
# #     #############  #######          ###     ## #  # ##### # ## ## ##  ##TTTTTTTT    # #   ### #
        ##  #####  #   ########      #  ####    #       ######## #######  TTT#TTTTT#     ###  ##
   #         #  #  #     ##### #     # # ##        #  # ###### #######  ## ## #TTTT#      #   #   #
                    #    ######     #### ###  #  ##   ########## # ### ####### ##T##### #  #  ####
#  ##    #          #     ###     ## ##  #    #  # ############   ####  ###   ######### #   #  #  ##
##       #   #           #        #### #### ##    # #############  ###  # #  #  ###   # ## #  ##
#        #              # ##  #    ## #   ## #   # ############# ## ##  # ####    #  ###  ###  # ###
 #   #        #   ##    ###   #      ## #######  #################### #### ##########   ######## # #
## #     ###  #   #            ## ######   ###    ###################     ####  ###   ### # #####  #
  ## #      # ##   #           #  #    ##   #    ### ################ #  ####### # #  ##### ######
#   # #            #     ###  #   # #  ######  #  #################### ############  ##  ## ##
  #  #      #    #      # #   #  ##   #########   # ################################ #  # ##########
#        #   #  #      ## # ## #####  ######  #     ################## ################ #### #######
##    # # #######      ##     ###### ########      ######## ######################## #### ### ## #
         # #######   ## #  #  ###############    ################################## ######  ## #   #
    #     #  #######  # ##   ####### #######    ### ######################## ##################
   #       #######       ##################    # ## ############################### ##### ####### ##
     #    # # ##  ##    ################## #   # ###  ###################################  ##  ###
 ### #    #  #    ###  ##################### ##  ######################################### # #  # #
#     #      #######  #################### ### ############## ## ######################## ## ##   ##
 #             ######################### #### ##### ###   ## ############### ############ #    ## ##
  ## #         ######################### #    ##### #     #    ## ## #  # #################### ### #
 ##  #         ###############  #  #   ##   # # #####   ####  # ## # ###  #########################
  #  # #       ############## #  ##     #     #  ### # ######### ###### # ### ###### ###  ## # # # #
 #    #        ##########    #    #            ############ ####### # ## ##   ############ ### # #
   ##  # ##   ####### ### # #     ###  #        #    ########       ###################  ##  #  # ##
# #   #######  ### #   #    # #    # #               #####   ### ## ###### ## ######## ### #   ##
# ######  ###  # # #            # #  # #    #        ## #      ### #####   ###  ##### ### # ## #
# #   # ###        #     # #     #  #### #    ##     #       ##  #### ##   ###  # ####### # #   ###
 ###   ####  #     #    ## #       #    ##  #### ## ##      # # ######## #  ###### ## #  #  ###### #
  ##   #    ##             #  #   #    ### #### # ###        ##  ## ## ###   ### ###  # ###  ######
 # # #  ##  # #      #  +   ## # # ##   ## #     ##     ###### #  #### # ###  ## #######      ######
      #   #     #    #  ##   #   ####  ##    #   # #     ###  # ## ##  # ### ##      ### #   ######
 ## ###       #  #     # ##   #     ## #   # #  ## #   ### #  ##       #   ## #        #   #  ######
Iteration: 271 Count: 1064267 State Count: 62024710
Solution: 311310000206444442411000026662662022222020000002000001113333321100000000000220222222266664
2211113022000444440000444044011130466626220033133130132222666662333332666640044444000220311110164666
222222202222222220000013333333110000000022000002222222266226662632662204440000000
Steps: 271, Fuel Usage: 253.
*/