Kevin Shepherd's solution:

#include <iostream>
#include <map>
#include <set>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <math.h>
#include <unistd.h>
#include <dirent.h>

#define MAX_CELL_DIM 0xFF
#define MAX_TARGET_COUNT 123
#define MAX_X_DIM	2048
#define MAX_Y_DIM	2048

#define POS_X_MASK	0x001FFFFF
#define POS_X_BITS	0x7FF
#define POS_X_ROLL	21

#define POS_Y_MASK	0xFFE003FF
#define POS_Y_BITS	0x7FF
#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

#define CELL_CLEAR	0
#define CELL_WALL	1
#define CELL_UNREACHABLE	2
#define CELL_START	3
#define CELL_TARGET	4

/*
random.txt
Cells: 100x75
Open Cell Count: 3418
Map size: 1000x750
Target count 1

big.txt
Cells: 173x173
Open Cell Count: 14854
Map size: 1730x1730
Target count 1

random2.txt
Cells: 100x75
Open Cell Count: 3418
Map size: 1000x750
Target count 25

big2.txt
Cells: 173x173
Open Cell Count: 14854
Map size: 1730x1730
Target count 38

*/

bool _opt_fuel = false;

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;
		}
	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;
	};

#define PATH_PREVIOUS_MASK 0xFFFFFF00
#define PATH_PREVIOUS_ROLL 8
#define PATH_COUNT_MASK 0xF
struct PathType
	{
	unsigned long	_M_previous_count;
	std::vector<unsigned long>	_M_arch;

	PathType()
	:_M_previous_count(0)
		{}
	PathType(const PathType & __other)
	:_M_previous_count(__other._M_previous_count), _M_arch(__other._M_arch)
		{}
	PathType & operator=(const PathType & __other)
		{
		_M_previous_count = __other._M_previous_count;
		_M_arch = __other._M_arch;
		}
	void	add_step(unsigned long __step)
		{
		int _count = count();
		if (_count == 0)
			{
			_M_arch.push_back(__step);
			}
		else
			{
			_M_arch.back() += __step * (unsigned long)pow( (int)6, _count );
			}
		++ _M_previous_count;
		if (count() == 12)
			_M_previous_count &= PATH_PREVIOUS_MASK;	
		}
	void set_previous(unsigned long __prev)
		{
		_M_previous_count = (__prev << PATH_PREVIOUS_ROLL) + count();
		}
	unsigned long count() const
		{
		return (_M_previous_count & PATH_COUNT_MASK);
		}
	unsigned long previous() const
		{
		return ((_M_previous_count & PATH_PREVIOUS_MASK) >> PATH_PREVIOUS_ROLL);
		}
	unsigned long step_count() const
		{
		return ((_M_arch.size() - (count()?1:0)) * 12) + count();
		}
	unsigned char get_step(unsigned long __idx) const
		{
		return ((_M_arch[__idx / 12] / (unsigned long)pow( (int)6, (int)(__idx % 12) )) % 6);
		}
	};

std::ostream & operator<< (std::ostream & __out, const PathType & __path)
	{
	for (unsigned long _idx = 0, _idy = __path.step_count(); _idx < _idy; ++ _idx)
		{
		unsigned short _step = __path.get_step(_idx);
		if (_step == 5)
			_step = 6;
		__out << _step;
		}
	return __out;
	}

struct Active
	{
	State	st;
	unsigned short primary, secondary;
	PathType	path;
	Active()
		{}
	Active(const Active & __other)
	:st(__other.st), primary(__other.primary), secondary(__other.secondary), path(__other.path)
		{}
	Active & operator=(const Active & __other)
		{
		st = __other.st;
		primary = __other.primary;
		secondary = __other.secondary;
		path = __other.path;
		}
	};

typedef std::list<Active>	ActiveList;
typedef std::map<unsigned long, ActiveList::iterator>	NewState;

unsigned long * state_array;
ActiveList	current_states;
NewState	new_states;
unsigned char cell_map[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
unsigned short cell_number[MAX_CELL_DIM+1][MAX_CELL_DIM+1];
unsigned long _cell_width = 0, _cell_height = 0;
unsigned long _pixel_width = 0, _pixel_height = 0;
unsigned long state_count = 0;
unsigned long _solution_count = 0;
unsigned short _min_primary = 0, _min_secondary = 0;

inline unsigned long compress(State _st)
	{
	unsigned long x = (unsigned long)_st.get_x();
	unsigned long y = (unsigned long)_st.get_y();

	return (cell_number[x/10][y/10] * 44100)+((x % 10) * 4410)+((y % 10) * 441)+((_st.get_vel_x() + 10) * 21)+(_st.get_vel_y() + 10);
	}

inline bool is_set_state(unsigned long _compressed)
	{
	return ( state_array[_compressed >> 5] & (1 << (_compressed & 0x1F) ) ) != 0;
	}

inline void set_state(unsigned long _compressed)
	{
	state_array[_compressed >> 5] |= (1 << (_compressed & 0x1F) );
	}

bool set_state_if(unsigned long _compressed)
	{
	bool _new_set = false;
	unsigned long _offset = _compressed >> 5;
	unsigned long _value = 1 << (_compressed & 0x1F);
	if ( ( state_array[_offset] & _value ) == 0)
		{
		state_array[_offset] |= _value;
		_new_set = true;
		}
	return _new_set;
	}

void transition (unsigned char __impulse, unsigned char __primary_delta, unsigned char __secondary_delta, const Active & __from);
void add_trans(const Active & _to);
unsigned long report(const ActiveList & current_states, ActiveList::const_iterator __start, unsigned long _iter);
void check_cells(unsigned char x, unsigned char y);

int main(int _argc, char * _argv[])
	{
	time_t _start_time = time(0);
	if (_argc < 2 )
		{
		std::cerr << "Usage: " << _argv[0] << " [--fuel] <map-name>" << std::endl;
		return 1;
		}
	std::string _map_name, _prefix_name;
	if (!strcmp(_argv[1], "--fuel"))
		{
		_opt_fuel = true;
		if (_argc < 3 )
			{
			std::cerr << "Usage: " << _argv[0] << " [--fuel] <map-name>" << std::endl;
			return 1;
			}
		_map_name.assign(_argv[2]);
		_prefix_name.assign(_map_name);
		_prefix_name.append("-fuel");
		}
	else
		{
		_map_name.assign(_argv[1]);
		_prefix_name.assign(_map_name);
		_prefix_name.append("-step");
		}
	_map_name.append(".txt");
	if (access(_map_name.c_str(), R_OK))
		{
		std::cerr << "Could not open file: " << _map_name << std::endl;
		std::cerr << "Usage: " << _argv[0] << " [--fuel] <map-name>" << std::endl;
		return 1;
		}
	std::ifstream _in(_map_name.c_str());
	_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;
		}
	bool _has_input = false;
	{
	DIR * _fdir = opendir(".");
	if (_fdir)
		{
		struct dirent _entry, * _result;
		while (!readdir_r(_fdir, & _entry, & _result))
			{
			int _len = strlen(_entry.d_name);
			if (_len > _prefix_name.size() && !strncmp( _entry.d_name, _prefix_name.c_str(), _prefix_name.size()))
				{
				_has_input = true;
				_prefix_name.assign(_entry.d_name);
				break;
				}
			}
		closedir(_fdir);
		}
	}

	unsigned long _target_count = 0, _active_targets = 0;
	Active _initial_state;
	_initial_state.primary = 0;
	_initial_state.secondary = 0;
	CellCoord	_cell_pos;
	_cell_pos.y = 0;
	memset(cell_map, CELL_CLEAR, sizeof(unsigned char [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
	memset(cell_number, 0, sizeof(unsigned short [MAX_CELL_DIM+1][MAX_CELL_DIM+1]));
	while (_in.good() && _cell_pos.y < _cell_height)
		{
		std::string _line;
		std::getline(_in, _line);
		if (_line.size() >= _cell_width)
			{
			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] = CELL_WALL;
					break;
				case 'O':
					cell_map[_cell_pos.x][_cell_pos.y] = CELL_START;
					_initial_state.st.set_x(_cell_pos.x * 10);
					_initial_state.st.set_y(_cell_pos.y * 10);
					break;
				case '+':
					{
					bool _is_active = true;
					if (_has_input)
						{
						char _buf[4];
						sprintf(_buf, "-%02d", _target_count);
						if (_prefix_name.find(_buf) != std::string::npos)
							_is_active = false;
						}
					if (_is_active)
						{
						cell_map[_cell_pos.x][_cell_pos.y] = (unsigned char)(_target_count + CELL_TARGET) | 0x80;
						++ _active_targets;
						}
					else
						{
						cell_map[_cell_pos.x][_cell_pos.y] = CELL_CLEAR | 0x80;
						}
					++ _target_count;
					}
					break;
				case ' ':
				default:
					cell_map[_cell_pos.x][_cell_pos.y] = CELL_CLEAR | 0x80;
					break;
					}
				}
			++ _cell_pos.y;
			}
		}
	bool _is_final = false;
	if (!_active_targets)
		{
		cell_map[_initial_state.st.get_x() / 10][_initial_state.st.get_y() / 10] = (unsigned char)(_target_count + CELL_TARGET) | 0x80;
		++ _active_targets;
		++ _target_count;
		_is_final = true;
		}
	_pixel_width = _cell_width * 10;
	_pixel_height = _cell_height * 10;
	std::cerr << "Map size: " << _pixel_width << "x" << _pixel_height << std::endl;
	std::cout << "Active Target count " << _active_targets << std::endl;

// Find unreachable cells
	_cell_pos.x = _initial_state.st.get_x() / 10;
	_cell_pos.y = _initial_state.st.get_y() / 10;
	check_cells(_cell_pos.x, _cell_pos.y);
	unsigned short _open_cell_count = 0;
	for (_cell_pos.y = 0; _cell_pos.y < _cell_height; ++ _cell_pos.y)
		{
		for (_cell_pos.x = 0; _cell_pos.x < _cell_width; ++ _cell_pos.x)
			{
			if ( (cell_map[_cell_pos.x][_cell_pos.y] & 0x80) != 0)
				{
				if (cell_map[_cell_pos.x][_cell_pos.y] == 0x80)
					{
					cell_map[_cell_pos.x][_cell_pos.y] = CELL_UNREACHABLE;
					}
				else
					{
					std::cerr << "Unreachable target(s)" << std::endl;
					return 1;
					}
				}
			if (cell_map[_cell_pos.x][_cell_pos.y] != CELL_WALL && cell_map[_cell_pos.x][_cell_pos.y] != CELL_UNREACHABLE)
				{
				cell_number[_cell_pos.x][_cell_pos.y] = _open_cell_count;
				++ _open_cell_count;
				}
			}
		}

	std::cout << "Open Cell Count: " << _open_cell_count << std::endl;
	if (_pixel_width > MAX_X_DIM || _pixel_height > MAX_Y_DIM)
		{
		std::cerr << "Map too large " << _pixel_width << "x" << _pixel_height << " > " << MAX_X_DIM << "x" << MAX_Y_DIM << std::endl;
		return 1;
		}
	_pixel_width -= 9;
	_pixel_height -= 9;
	if (_target_count > MAX_TARGET_COUNT)
		{
		std::cerr << "Too many targets " << _target_count << " > " << MAX_TARGET_COUNT << std::endl;
		return 1;
		}
	double _state_array_count = (1378.125 * _open_cell_count) + 1.0;
	unsigned long _state_array_size = (unsigned long)_state_array_count;
	std::cout << "Allocating state array unsigned long[" << _state_array_size << "]" << " Number of States: " << (44100 * _open_cell_count) << std::endl;
	state_array = new unsigned long[_state_array_size];
	if (! state_array)
		{
		std::cerr << "Insufficient memory for state array unsigned long[" << _state_array_size << "]" << std::endl;
		return 1;
		}
	memset(state_array, 0, sizeof(unsigned long) * _state_array_size);
/*
marsrescue big
Cells: 173x173
Map size: 1730x1730
Active Target count 1
Open Cell Count: 14854
Allocating state array unsigned long[20483666] Number of States: 655477312
Input 33496 Active states
Adding States ...
Added 2784 states
.
Cells: 173x173
Map size: 1730x1730
Active Target count 1
Open Cell Count: 14854
Allocating state array unsigned long[20470669] Number of States: 655061400
Input 33496 Active states
Adding States ...
Added 2784 states
.
*/
	ActiveList initial_states;
	if (_has_input)
		{
		std::ifstream _input(_prefix_name.c_str());
		unsigned long _in_count = 0;
		for (;;)
			{
			Active _from;
			short _value;
			std::string _prev_path;
			_input >> _from.primary;
			_input >> _from.secondary;
			_input >> _value;
			_from.st.set_x(_value);
			_input >> _value;
			_from.st.set_y(_value);
			_input >> _value;
			_from.st.set_vel_x(_value);
			_input >> _value;
			_from.st.set_vel_y(_value);
			_input >> _prev_path;
			_from.path.set_previous(_in_count + 1);
			if (!_input.good())
				break;
			initial_states.push_front(_from);
			++ _in_count;
			}
		std::cout << "Input " << _in_count << " Active states" << std::endl;
		}
	else
		{
		initial_states.push_back(_initial_state);
		}
	short _iter = initial_states.front().primary;
	-- _iter;

	current_states.push_back(Active());
	ActiveList::iterator _target_end = current_states.end();
	-- _target_end;
	
	if (_opt_fuel)
		{
		current_states.push_back(Active());
		ActiveList::iterator _end_2 = current_states.end();
		-- _end_2;

		current_states.push_back(Active());
		ActiveList::iterator _end_1 = current_states.end();
		-- _end_1;

		do
			{
			if (!initial_states.empty())
				{
				ActiveList::iterator _ix = initial_states.begin();
				for (ActiveList::iterator _iy = initial_states.end(); _ix != _iy; )
					{
					if ( (* _ix).primary > _iter + 1 )
						{
						break;
						}
					add_trans(* _ix);
					++ _ix;
					}
				initial_states.erase(initial_states.begin(), _ix);
				}
			ActiveList::iterator _start = _target_end;
			++ _start;
			ActiveList::iterator _ax = _start;
			for (; _ax != _end_2; )
				{
				transition(3, 2, 1, * _ax);
				transition(5, 2, 1, * _ax);
				ActiveList::iterator _nextx = _ax;
				++ _nextx;
				current_states.erase(_ax);
				_ax = _nextx;
				}
			current_states.erase(_end_2);
			// current_states.erase(_start, ++ _end_2);
			_ax = _target_end;
			for (++ _ax; _ax != _end_1; ++ _ax)
				{
				transition(1, 1, 1, * _ax);
				transition(2, 1, 1, * _ax);
				transition(4, 1, 1, * _ax);
				}
			_ax = _end_1;
			for (++ _ax; _ax != current_states.end(); ++ _ax)
				{
				transition(0, 0, 1, * _ax);
				}

			_end_2 = _end_1;
			current_states.push_back(Active());
			_end_1 = current_states.end();
			-- _end_1;

			std::cout << "Adding States ..." << std::endl;
			unsigned long _adding_count = 0;
			for (NewState::const_iterator _nx = new_states.begin(), _ny = new_states.end(); _nx != _ny; ++ _nx)
				{
				set_state( (* _nx).first );
				++ _adding_count;
				}
			std::cout << "Added " << _adding_count << " states" << std::endl;
			new_states.clear();
			++ _iter;
			std::cout << '.';
			}
		while ( (report(current_states, _target_end, _iter) > 2 || !initial_states.empty()) && (!_is_final || (current_states.begin() == _target_end)));
		}
	else
		{ // steps
		do
			{
			current_states.push_back(Active());
			ActiveList::iterator _partition = current_states.end();
			-- _partition;

			if (!initial_states.empty())
				{
				ActiveList::iterator _ix = initial_states.begin();
				for (ActiveList::iterator _iy = initial_states.end(); _ix != _iy; )
					{
					if ( (* _ix).primary > _iter + 1 )
						{
						break;
						}
					add_trans(* _ix);
					++ _ix;
					}
				initial_states.erase(initial_states.begin(), _ix);
				}

			ActiveList::iterator _start = _target_end;
			++ _start;
			for (ActiveList::iterator _ax = _start; _ax != _partition; )
				{
				transition(0, 1, 0, * _ax);
				transition(1, 1, 1, * _ax);
				transition(2, 1, 1, * _ax);
				transition(4, 1, 1, * _ax);
				transition(3, 1, 2, * _ax);
				transition(5, 1, 2, * _ax);
				ActiveList::iterator _nextx = _ax;
				++ _nextx;
				current_states.erase(_ax);
				_ax = _nextx;
				}
			current_states.erase(_partition);
			// current_states.erase(_start, ++ _partition);

			std::cout << "Adding States ..." << std::endl;
			unsigned long _adding_count = 0;
			for (NewState::const_iterator _nx = new_states.begin(), _ny = new_states.end(); _nx != _ny; ++ _nx)
				{
				set_state( (* _nx).first );
				++ _adding_count;
				}
			std::cout << "Added " << _adding_count << " states" << std::endl;
			new_states.clear();
			++ _iter;
			std::cout << '.';
			}
		while ((report(current_states, _target_end, _iter) || !initial_states.empty()) && (!_is_final || (current_states.begin() == _target_end)));
		}
	delete[] state_array;
	time_t _time_taken = time(0) - _start_time;
	std::ofstream _log("marsrescue.log", std::ios_base::out | std::ios_base::app | std::ios_base::ate);
	std::cout << _solution_count << " solutions in " << _time_taken << " seconds, minimum: " << (_opt_fuel?"fuel":"steps") << " = " << _min_primary << " " << (_opt_fuel?"steps":"fuel") << " = " << _min_secondary << std::endl;
	_log << _prefix_name << ": " << _solution_count << " solutions in " << _time_taken << " seconds, minimum: " << (_opt_fuel?"fuel":"steps") << " = " << _min_primary << " " << (_opt_fuel?"steps":"fuel") << " = " << _min_secondary << std::endl;

	std::vector<std::string>	_previous_path;
	if (_has_input)
		{
		std::ifstream _input(_prefix_name.c_str());
		for (;;)
			{
			short _value;
			unsigned short _value2;
			std::string _prev_path;
			_input >> _value2;
			_input >> _value2;
			_input >> _value;
			_input >> _value;
			_input >> _value;
			_input >> _value;
			_input >> _prev_path;
			_previous_path.push_back(_prev_path);
			if (!_input.good())
				break;
			}
		}
	int _optimal_solutions = 0;
	for (ActiveList::iterator _ax = current_states.begin(); _ax != _target_end; ++ _ax)
		{ // output targets
		if ( (* _ax).primary == _min_primary && (* _ax).secondary == _min_secondary)
			{
			++ _optimal_solutions;
			std::cout << (_has_input?_previous_path[(* _ax).path.previous()-1]:"") << (* _ax).path << std::endl;
			_log << (_has_input?_previous_path[(* _ax).path.previous()-1]:"") << (* _ax).path << std::endl;
			}
		std::string _output_file;
		if (_is_final)
			_output_file.assign("final-");	
		_output_file.append(_prefix_name);
		short _hit_target = -1;
		short _new_x = (* _ax).st.get_x();
		short _new_y = (* _ax).st.get_y();
		bool _x_two_col = ((_new_x % 10) != 0);
		bool _y_two_col = ((_new_y % 10) != 0);
		CellCoord	_cell_pos;
		_cell_pos.x = _new_x / 10;
		_cell_pos.y = _new_y / 10;
		unsigned char _cell_content = cell_map[_cell_pos.x][_cell_pos.y];
		if ( _cell_content >= CELL_TARGET)
			{
			_hit_target = _cell_content - CELL_TARGET;
			}
		if (_x_two_col)
			{
			++ _cell_pos.x;
			_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
			if ( _cell_content >= CELL_TARGET)
				{
				_hit_target = _cell_content - CELL_TARGET;
				}
			if (_y_two_col)
				{
				++ _cell_pos.y;
				_cell_content = cell_map[_cell_pos.x][_cell_pos.y];
				if ( _cell_content >= CELL_TARGET)
					{
					_hit_target = _cell_content - CELL_TARGET;
					}
				-- _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 >= CELL_TARGET)
				{
				_hit_target = _cell_content - CELL_TARGET;
				}
			-- _cell_pos.y;
			}

		char _buf[4];
		sprintf(_buf, "-%02d", _hit_target);
		_output_file.append(_buf);
		std::ofstream _out(_output_file.c_str(), std::ios_base::out | std::ios_base::app | std::ios_base::ate);
		_out << (* _ax).primary << " " << (* _ax).secondary << " " << (* _ax).st.get_x() << " " << (* _ax).st.get_y() << " " << (* _ax).st.get_vel_x() << " " << (* _ax).st.get_vel_y() << " " << (_has_input?_previous_path[(* _ax).path.previous()-1]:"") << (* _ax).path << std::endl;
		}
	_log << _optimal_solutions << " optimal of " << _solution_count << " solutions" << std::endl;
	std::cout << _optimal_solutions << " optimal of " << _solution_count << " solutions" << std::endl;

	if (_has_input)
		{
		std::string _new_name("done-");
		_new_name.append(_prefix_name);
		unlink(_new_name.c_str());
		rename(_prefix_name.c_str(), _new_name.c_str());
		}
	return 0;
	}

void transition (unsigned char __impulse, unsigned char __primary_delta, unsigned char __secondary_delta, const Active & __from)
	{
	Active _to(__from);
	_to.primary += __primary_delta;
	_to.secondary += __secondary_delta;
	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 5:
		_to.st.set_vel_x(_to.st.get_vel_x() + 2);
		_to.st.set_vel_y(_to.st.get_vel_y() - 1);
		break;
		}

	do
		{
		short _new_x = _to.st.get_x() + _to.st.get_vel_x();
		if (_new_x >= 0 && _new_x < _pixel_width)
			{
			short _new_y = _to.st.get_y() + _to.st.get_vel_y();
			if (_new_y >= 0 && _new_y < _pixel_height)
				{
				CellCoord	_cell_pos;
				_cell_pos.x = _new_x / 10;
				_cell_pos.y = _new_y / 10;
				if (cell_map[_cell_pos.x][_cell_pos.y] != CELL_WALL)
					{	
					bool _y_two_col = ((_new_y % 10) != 0);
					bool _collision = false;
					if ((_new_x % 10) != 0)
						{
						++ _cell_pos.x;
						if (cell_map[_cell_pos.x][_cell_pos.y] == CELL_WALL)
							_collision = true;
						else
							{	
							if (_y_two_col)
								{
								if (cell_map[_cell_pos.x][_cell_pos.y+1] == CELL_WALL)
									_collision = true;	
								}
							}
						-- _cell_pos.x;
						}
					if (_y_two_col)
						{
						++ _cell_pos.y;
						if (cell_map[_cell_pos.x][_cell_pos.y] == CELL_WALL)
							_collision = true;	
						}
					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() );

	short _new_x = _to.st.get_x() + _to.st.get_vel_x();
	short _new_y = _to.st.get_y() + _to.st.get_vel_y();
	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 _hit_target = false;
	if ( cell_map[_cell_pos.x][_cell_pos.y] >= CELL_TARGET)
		_hit_target = true;
	else
		{
		bool _y_two_col = ((_new_y % 10) != 0);
		if ((_new_x % 10) != 0)
			{
			++ _cell_pos.x;
			if ( cell_map[_cell_pos.x][_cell_pos.y] >= CELL_TARGET)
				_hit_target = true;
			else
				{
				if (_y_two_col)
					{
					if ( cell_map[_cell_pos.x][_cell_pos.y+1] >= CELL_TARGET)
						_hit_target = true;
					}
				}
			-- _cell_pos.x;
			}
		if (_y_two_col)
			{
			++ _cell_pos.y;
			if ( cell_map[_cell_pos.x][_cell_pos.y] >= CELL_TARGET)
				_hit_target = true;
			}
		}

	unsigned long _compressed = compress(_to.st);
	if (!is_set_state(_compressed))
		{
		bool _should_add = true;

		NewState::iterator _ns = new_states.find(_compressed);
		if (_ns != new_states.end())
			{
			if ( (* ((* _ns).second) ).secondary > _to.secondary)
				{
				current_states.erase( (* _ns).second );
				-- state_count;
				}
			else
				{
				_should_add = false;
				}
			}
		if (_should_add)
			{
/*			char _buf[2];
			sprintf(_buf, "%d", (int)__impulse);
			_to.path.append(_buf);
*/			_to.path.add_step(__impulse);

			++ state_count;
			ActiveList::iterator _inserted;
			if (_hit_target)
				{
				if (_to.primary < _min_primary || (_to.primary == _min_primary && _to.secondary < _min_secondary) || !_solution_count )
					{
					_min_primary = _to.primary;
					_min_secondary = _to.secondary;
					}
				++ _solution_count; 
				current_states.push_front(_to);
				_inserted = current_states.begin();
				}
			else
				{
				current_states.push_back(_to);
				_inserted = current_states.end();
				-- _inserted;
				}
			new_states[_compressed] = _inserted;
			}
		}
	}

void add_trans(const Active & _to)
	{
	unsigned long _compressed = compress(_to.st);
	if (!is_set_state(_compressed))
		{
		bool _should_add = true;

		NewState::iterator _ns = new_states.find(_compressed);
		if (_ns != new_states.end())
			{
			if ( (* ((* _ns).second) ).secondary > _to.secondary)
				{
				current_states.erase( (* _ns).second );
				-- state_count;
				}
			else
				{
				_should_add = false;
				}
			}
		if (_should_add)
			{
			++ state_count;
			ActiveList::iterator _inserted;
			current_states.push_back(_to);
			_inserted = current_states.end();
			-- _inserted;

			new_states[_compressed] = _inserted;
			}
		}
	}

unsigned long report(const ActiveList & current_states, ActiveList::const_iterator __start, unsigned long _iter)
	{ // 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::const_iterator _ax = ++ __start, _ay = current_states.end(); _ax != _ay; ++ _ax)
		{
		unsigned char _content = report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ];
		report_map[ (* _ax).st.get_x() / 10 ][ (* _ax).st.get_y() / 10 ] = 0xFF;
		++ _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 CELL_CLEAR:
				std::cout << ' ';
				break;
			case CELL_WALL:
				std::cout << '#';
				break;
			case CELL_UNREACHABLE:
				std::cout << 'X';
				break;
			case CELL_START:
				std::cout << 'O';
				break;
			case 0xFF:
				std::cout << '*';
				break;
			default:
				std::cout << '+';
				break;
				}
			}
		std::cout << std::endl;
		}
	std::cout << "Iteration: " << _iter << " Count: " << _active_count << " State Count: " << state_count << std::endl;
	return _active_count;
	}

void check_cell(unsigned char x, unsigned char y)
	{
	if ((cell_map[x][y] & 0x80) != 0)
		{
		cell_map[x][y] &= 0x7F;
		check_cells(x, y);
		}
	}

void check_cells(unsigned char x, unsigned char y)
	{
	if (y > 0)
		{
		if (x > 0)
			check_cell(x - 1, y - 1);
		check_cell(x, y - 1);
		if (x < (_cell_width - 1))
			check_cell(x + 1, y - 1);
		}
	if (x > 0)
		check_cell(x - 1, y);
	if (x < (_cell_width - 1))
		check_cell(x + 1, y);
	if (y < (_cell_height - 1))
		{
		if (x > 0)
			check_cell(x - 1, y + 1);
		check_cell(x, y + 1);
		if (x < (_cell_width - 1))
			check_cell(x + 1, y + 1);
		}
	}
/*
map-step: 18890 solutions in 1112 seconds, minimum: steps = 139 fuel = 85
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222242013100
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222242013010
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222206003110
6444422202022220200000222000222222000000222022222000000000000000000001111101133322222022222222020000000000002222202022222222220222206003101
map-step-00: 3534 solutions in 1015 seconds, minimum: steps = 282 fuel = 169
644442220202222020000022200022222200000022202222200000000000000000000111110113332222202222222202000000000000222220202222222222022220226100044446604010000046222222222222000222222020000000000022220222222222233131313130202000000000000002222222200000020002222222222202000000000000000000
644442220202222020000022200022222200000022202222200000000000000000000111110113332222202222222202000000000000222220202222222222022220226100044446604010000046222222222222000222222020000000000022220222222222233131313130202000000000000002222222200000020002222222222022000000000000000000
random-step: 10567 solutions in 1242 seconds, minimum: steps = 135 fuel = 103
313310000004444440411000026662662022222020000002000001113333321100000000000220222222266664221111302200044444040440000000110446662222000
313310000004444440411000026662662022222020000002000001113333321100000000000220222222266664221111302200044444040440000000110446626222000
313310000004444440411000026662662022222020000002000001113333321100000000000220222222266664221111302200044444004440000000011046666222000
random-step-00: 24 solutions in 3692 seconds, minimum: steps = 271 fuel = 237
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662244400000000
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662244040000000
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662240440000000
3133100000044444404110000266626620222220200000020000011133333211000000000002202222222666642211113022000444440044400000000130466626220033133131022222626663323222266262244644000022000000146666222222220202022220000013333333110000000022000002222222266226662632662204440000000
random-fuel: 9862 solutions in 3920 seconds, minimum: fuel = 57 steps = 156
313110000000000000040040000000000000006644422220200000202000000000000011111002000000000000000333332000000000202022000400001000440000040000000000066640020000
313110000000000000040040000000000000006644422220200000202000000000000011111002000000000000000333332000000000202022000400001000440000040000000000066604020000
random-fuel-00: 35 solutions in 957 seconds, minimum: fuel = 157 steps = 329
31311000000000000004004000000000000000664442222020000020200000000000001111100200000000000000033333200000000020202200040000100044000004000000000004662000202000000032201201002222222222620000022222000626020200006004400000000000004000006222666422220202020202000000000222233333200000000020000222222220000022222222202422624400000000000
map-fuel: 16153 solutions in 1226 seconds, minimum: fuel = 69 steps = 155
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222202420000000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222202060000000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222242004000000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222242000400000000
66666220020000000220022002200220022002200220022002200000000000000000000000001110000000100000000000033333002002000222000202220020202022222222242000040000000
map-fuel-00: 108 solutions in 2067 seconds, minimum: fuel = 146 steps = 318
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222222212020202031302020200000000200002200220022002200220022002200220022000000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222223202020202021312020200000000200002200220022002200220022002200220022000000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222223202020202021303020200000000200002200220022002200220022002200220022000000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000040000200666662200200220020000000020002222222200020000000000322222222212020202031302020200000000200020022002200220022002200220022002200200000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222222212020202031302020200000000200002200220022002200220022002200220020200000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000040000200666662200200220020000000020002222222200020000000000322222222212020202031302020200000000200020022002200220022002200220022002200020000000000
666662200200000002200220022002200220022002200220022000000000000000000000000011100000001000000000000333330020020002220002022200202020222222222024200000000000066400000040000000000662222262220022020020000000002002222222200200000000000322222222212020202031302020200000000200002200220022002200220022002200220020020000000000
big-step-00: 2219 solutions in 4726 seconds, minimum: steps = 660 fuel = 345
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222020000000000000000000000000000000000333202222222222220202020202020200000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222020000000000000000000000000000000000333022222222222220202020202020200000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222002000000000000000000000000000000002333222222222220202020202020220000000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000022000000000000000000000000000000000002333222222202222202020202020200000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202200000000000000000000000000000000000033322222222222202020202020200000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202200000000000000000000000000000000000033322222222222022020202020200000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222222020202020202020000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222220220202020202020000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222202220202020202020000000000000000000000000
664440000000000000000000002222222222220222222222020202020202020202020202000000000000000000000000000000000111111111100000000000000000000000004440444444400000000000000000000111111112332220000000000000000222222222222022202222222020202020202000000000002222022000000000000000000000000000000000000444000000000000000000000000000000000006222222222020202020222222222266622222222222622222222222222200000000000000222222202222000000000000000000000000000222222222222222220222202020202020000202222131313131302020202022222222222226666626666622222222222222222222222233333333332222222000000202000000000000000000000000000000233322222222022220202020202020000000000000000000000000
10 optimal of 2219 solutions
*/