//C++
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <sstream>

//C
#include <stdio.h>
#include <stdlib.h>

using namespace std;

// ----------------------------------------------------------------------------
// Class/Struct Function Prototypes
// ----------------------------------------------------------------------------

/*
 * Class for ShapeShifter. Has a grid of the initial setup that you will try to
 * put pieces into. Also has a struct called "shape" that stores a shape's
 * grid, width, and height.
 */

typedef unsigned int uint;

class ShapeShifter {
	struct shape {
		//Constructors
		shape();
		shape(const string&);
		
		//Variables
		vector< vector<bool> > grid;
		uint width, height;
		string text;
	};
		
	public:
		//Constructors
		ShapeShifter();
		ShapeShifter(const vector<string>&);
		
		//Dealing with shapes
		void add_shape(const string&);
		bool apply_shape(uint, uint, uint);
		
		//Solving functions
		bool all_one();
		bool find_solution(uint);
		void print_solution();
		
	private:
		//All shapes to be inserted into the grid
		vector<shape> shapes;
		
		//Game Grid
		vector< vector<bool> > grid;
		
		//(x, y) points for each shape when the solution is found.
		list< pair<uint, uint> > solution;
		
		//Game grid size
		uint width, height;
};

// ----------------------------------------------------------------------------
// Class/Struct Function Declarations
// ----------------------------------------------------------------------------

/* Shape Struct */
ShapeShifter::shape::shape() {
	/* Leave Empty */
}

ShapeShifter::shape::shape(const string& line) {
	/*
	 * Takes "line" and makes a grid out of it.
	 *
	 * - Split the string by space (probably via istringstream).
	 *   Put each row into a temporary vector<string>.
	 *
	 * - Go through each char in each row and set "grid" up.
	 *
	 * - Set width and height
	 *
	 * - Store the original string ("line") in "text".
	 */
}

/* ShapeShifter Class */
ShapeShifter::ShapeShifter() {
	/* Leave Empty */
}

ShapeShifter::ShapeShifter(const vector<string>& rows) {
	/*
	 * Similar to the "shape" constructor. Except you're given a vector of
	 * rows already. So you can skip the splitting part.
	 */
}

void ShapeShifter::add_shape(const string& line) {
	/*
	 * Should just be one line. Push back a shape made with the string "line".
	 */
}

bool ShapeShifter::apply_shape(uint shape_id, uint x, uint y) {
	/*
	 * Insert the shape into the game grid.
	 *
	 * - Check if the shape can fit in the grid when shifted by "x" and "y".
	 * - Invert all parts of the grid where the shape would be red at.
	 */
}

bool ShapeShifter::all_one() {
	/*
	 * Check if all cells in the grid are "1". If so, return true. Otherwise,
	 * return false.
	 */
}

bool ShapeShifter::find_solution(uint shape_id) {
	/*
	 * The recursive function.
	 *
	 * - With "shape_id", go through every possible position and try to insert
	 *   shape[shape_id] in.
	 *
	 * - If inserted and it isn't the last shape, call:
	 *     find_solution(shape_id + 1)
	 *
	 * - If inserted and it is the last shape, call "all_one". If true then
	 *   return true. Have the other calls to the function also handle this
	 *   return.
	 *
	 * - If you looped through all possible positions and it didn't work, undo
	 *   all changes done to the class involving this shape and return false.
	 */
}

void ShapeShifter::print_solution() {
	/*
	 * Goes through "solution" list and prints out the coordinates of each
	 * shape, along with the original string used to make up the shape.
	 */
}

// ----------------------------------------------------------------------------
// Main Function
// ----------------------------------------------------------------------------

int main(int argc, char** argv) {
	/*
	 * - Create a vector of strings holding all argv after argv[0]
	 *
	 * - Create your ShapeShifter object.
	 *
	 * - Create all shapes.
	 *
	 * - Find a solution.
	 *
	 * - Print the result.
	 */
}