// on Unix: compile with g++ -lz marsimg.cpp -o marsimg
// on Windows, for example Visual C++: create a new conole 
// application, download zlib and add all sources

#include <zlib.h>

#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

typedef unsigned char byte;
typedef vector<byte> byte_vector;

byte_vector pixels;
byte_vector result;
vector<int> crc_table;
int sx, sy;

void set_pixel(int r, int g, int b, int x, int y) {
	if (x < 0) x = 0;
	if (y < 0) y = 0;
	if (x >= sx) x = sx - 1;
	if (y >= sy) y = sy - 1;
	int ofs = 3 * (sx * y + x);
	pixels[ofs] = r;
	pixels[ofs + 1] = g;
	pixels[ofs + 2] = b;
}

void draw_cell(int r, int g, int b, int x, int y) {
	for (int cx = x; cx < x + 10; cx++) {
		for (int cy = y; cy < y + 10; cy++) {
			set_pixel(r, g, b, cx, cy);
		}
	}
}
        
// create a chunk with the bytes in data and the specified
// type and add it to result
void add_chunk(const char* type, byte_vector data) {
	// chunk layout:
	// length: 4 bytes: counting chunk data only
	// chunk type: 4 bytes
	// chunk data: length bytes
	// CRC: 4 bytes: CRC-32 checksum of the type and the data
	    
	// copy data and create CRC checksum
	size_t len = data.size();
	byte_vector chunk;
	chunk.push_back(byte((len >> 24) & 255));
	chunk.push_back(byte((len >> 16) & 255));
	chunk.push_back(byte((len >> 8) & 255));
	chunk.push_back(byte(len & 255));
	chunk.push_back(type[0]);
	chunk.push_back(type[1]);
	chunk.push_back(type[2]);
	chunk.push_back(type[3]);
	chunk.insert(chunk.end(), data.begin(), data.end());

	// calculate a CRC checksum with the bytes chunk[4..len-1]
	int z = 0xffffffff;
	int c = z;
	for (size_t n = 4; n < chunk.size(); n++) {
	    int c8 = (c >> 8) & 0xffffff;
	    c = crc_table[(c ^ chunk[n]) & 0xff] ^ c8;
	}
	int crc = c ^ z;

	chunk.push_back((crc >> 24) & 255);
	chunk.push_back((crc >> 16) & 255);
	chunk.push_back((crc >> 8) & 255);
	chunk.push_back(crc & 255);

	// add it to the result
	result.insert(result.end(), chunk.begin(), chunk.end());
}

void save_image(const char* filename) {
	// create crc-table
	int z = 0xedb88320;
	for (int n = 0; n < 256; n++) {
		int c = n;
		for (int k = 0; k < 8; k++) {
			int c2 = (c >> 1) & 0x7fffffff;
			if (c & 1) c = z ^ (c2); else c = c2;
		}
		crc_table.push_back(c);
	}

	// PNG file signature
	result.push_back(137);
	result.push_back(80);
	result.push_back(78);
	result.push_back(71);
	result.push_back(13);
	result.push_back(10);
	result.push_back(26);
	result.push_back(10);
	    
	// IHDR chunk data:
	//   width:              4 bytes
	//   height:             4 bytes
	//   bit depth:          1 byte (8 bits per RGB value)
	//   color type:         1 byte (2 = RGB)
	//   compression method: 1 byte (0 = deflate/inflate)
	//   filter method:      1 byte (0 = adaptive filtering)
	//   interlace method:   1 byte (0 = no interlace)
	byte_vector data;
	data.push_back((sx >> 24) & 255);
	data.push_back((sx >> 16) & 255);
	data.push_back((sx >> 8) & 255);
	data.push_back(sx & 255);
	data.push_back((sy >> 24) & 255);
	data.push_back((sy >> 16) & 255);
	data.push_back((sy >> 8) & 255);
	data.push_back(sy & 255);
	data.push_back(8);
	data.push_back(2);
	data.push_back(0);
	data.push_back(0);
	data.push_back(0);
	add_chunk("IHDR", data);

	// IDAT: image data:
	//    scanline:
	//        filter byte: 0 = none
	//        RGB bytes for the line
	unsigned long len = (sx * 3 + 1) * sy;
	unsigned long zlen = (unsigned long) len + len / 100 + 12;
	byte* uncompressed = new byte[len];
	int i_uncompressed = 0;
	int i_pixels = 0;
	for (int y = 0; y < sy; y++) {
		uncompressed[i_uncompressed++] = 0;
		for (int x = 0; x < sx; x++) {
			uncompressed[i_uncompressed++] = pixels[i_pixels++];
			uncompressed[i_uncompressed++] = pixels[i_pixels++];
			uncompressed[i_uncompressed++] = pixels[i_pixels++];
		}
	}
	byte* compressed = new byte[zlen];
	compress2(compressed, &zlen, uncompressed, len, 9);
	data.clear();
	for (size_t i = 0; i < zlen; i++) data.push_back(compressed[i]);
	delete [] compressed;
	delete [] uncompressed;
	add_chunk("IDAT", data);

	// IEND: marks the end of the PNG-file
	data.clear();
	add_chunk("IEND", data);

	// print the image
	ofstream out(filename, ios::out | ios::binary);
	copy(result.begin(), result.end(), ostream_iterator<byte>(out));
}


#define EMPTY 0
#define START 1
#define TARGET 2
#define STONE 3

int width, height, startX, startY, robotX, robotY;
int speedX = 0;
int speedY = 0;
bool targetReached = false;
bool won = false;
int** map;

bool inMap(int x, int y) {
	return x >= 0 && x < 10 * width && y >= 0 && y < 10 * height;
}

bool hitTestImpl(int x, int y, int cellType) {
	if (inMap(x, y)) {
		return (map[y/10][x/10]) == cellType;
	} else {
		return cellType == STONE;
	}
}

bool hitTest(int x, int y, int cellType) {
	return hitTestImpl(x, y, cellType) ||
		hitTestImpl(x + 9, y, cellType) ||
		hitTestImpl(x, y + 9, cellType) ||
		hitTestImpl(x + 9, y + 9, cellType);
}

void updateRobot(bool left, bool bottom, bool right) {
	if (left) speedX -= 2;
	if (bottom) speedY -= 2;
	if (right) speedX += 2;
	speedY++;
	if (speedX < -10) speedX = -10;
	if (speedY < -10) speedY = -10;
	if (speedX > 10) speedX = 10;
	if (speedY > 10) speedY = 10;
	while (true) {
		int newX = robotX + speedX;
		int newY = robotY + speedY;
		if (hitTest(newX, newY, STONE)) {
			speedX /= 2;
			speedY /= 2;
		} else {
			robotX = newX;
			robotY = newY;
			break;
		}
		if (speedX == 0 && speedY == 0) break;
	}
}

void update(bool left, bool bottom, bool right) {
	updateRobot(left, bottom, right);
	if (hitTest(robotX, robotY, TARGET)) {
		targetReached = true;
	}
	if (targetReached) {
		if (hitTest(robotX, robotY, START)) {
			won = true;
		}
	}
}

int main(int argc, char* argv[]) {
	if (argc != 4) {
		cerr << "usage: marsimg map.txt output.png [small|large]\nsolution string by stdin" << endl;
		return 1;
	}

	// load map
	ifstream map_file(argv[1]);
	string widthString, heightString;
	int startX, startY;
	getline(map_file, widthString);
	getline(map_file, heightString);
	width = atoi(widthString.c_str());
	height = atoi(heightString.c_str());
	map = new int*[height];
	for (int y = 0; y < height; y++) {
		map[y] = new int[width];
		string line;
		getline(map_file, line);
		for (int x = 0; x < width; x++) {
			char c = line[x];
			switch (c) {
				case ' ' :
					map[y][x] = EMPTY;
					break;
				case 'O' :
					map[y][x] = START;
					startX = 10 * x;
					startY = 10 * y;
					break;
				case '+' :
					map[y][x] = TARGET;
					break;
				default :
					map[y][x] = STONE;
					break;
			}
		}
	}

	// fill image background
	bool small = string("small") == argv[3];
	sx = width;
	sy = height;
	if (!small) {
		sx *= 10;
		sy *= 10;
	}
	for (int h = 0; h < sy; h++) {
		for (int w = 0; w < sx; w++) {
			int r = 255;
			int g = 255;
			int b = 255;
			pixels.push_back(r);
			pixels.push_back(g);
			pixels.push_back(b);
		}
	}

	// draw map
	for (int y = 0; y < height; y++) {
		for (int x = 0; x < width; x++) {
			switch (map[y][x]) {
				case EMPTY:
					if (small) {
						set_pixel(255, 255, 255, x, y);
					} else {
						draw_cell(255, 255, 255, 10*x, 10*y);
					}
					break;
				case START:
					if (small) {
						set_pixel(0, 0, 0, x, y);
					} else {
						draw_cell(0, 0, 0, 10*x, 10*y);
					}
					break;
				case TARGET:
					if (small) {
						set_pixel(255, 0, 0, x, y);
					} else {
						draw_cell(255, 0, 0, 10*x, 10*y);
					}
					break;
				case STONE:
					if (small) {
						set_pixel(255, 165, 0, x, y);
					} else {
						draw_cell(255, 165, 0, 10*x, 10*y);
					}
					break;
			}
		}
	}

	// draw solution
	robotX = startX;
	robotY = startY;
	int step = 0;
	while (!cin.eof()) {
		char c = cin.get();
		if (c >= '0' && c <= '7') {
			int jets = c - '0';
			bool left = (jets & 1) > 0;
			bool bottom = (jets & 2) > 0;
			bool right = (jets & 4) > 0;
			update(left, bottom, right);
			if (targetReached) {
				if (small) {
					set_pixel(255, 0, 0, robotX/10, robotY/10);
				} else {
					draw_cell(255, 0, 0, robotX, robotY);
				}
			} else {
				if (small) {
					set_pixel(0, 0, 0, robotX/10, robotY/10);
				} else {
					draw_cell(0, 0, 0, robotX, robotY);
				}
			}
			if (won) break;
		}
	}
	save_image(argv[2]);
}