fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <stdexcept>
  3. using namespace std;
  4.  
  5. class OrientedShape{
  6. public:
  7. 	// Oriented Shape represents a shape that has been transformed which may exist in 3-dimensions
  8. 	int rows, columns, height;
  9. 	vector<vector<vector<bool>>> a;
  10.  
  11. 	OrientedShape(int height, int rows, int columns)
  12.         : rows(rows), columns(columns), height(height) {
  13.         a.resize(height, vector<vector<bool>>(rows, vector<bool>(columns)));
  14.     }
  15.  
  16. 	void add(int h, int r, int c){
  17. 		a[h][r][c]=1;
  18. 	}
  19.  
  20. 	// Utility for printing the shape
  21.     void print(){
  22.     	for(int i=0;i<height;i++){
  23.     		cout<<"Plane "<<i<<":\n";
  24.     		for(int j=0;j<rows;j++){
  25.     			for(int k=0;k<columns;k++){
  26.     				cout<<a[i][j][k]<<" ";
  27.     			}
  28.     			cout<<"\n";
  29.     		}
  30.     		cout<<"\n\n";
  31.     	}
  32.     }
  33.  
  34. };
  35.  
  36.  
  37. class Shape{
  38. public:
  39.     int rows, columns, height=0;
  40.     string color;
  41.     int id;
  42.     vector<vector<bool>> block;
  43.  
  44.     // Construct a shape by specifying the rows, columns and adding the blocks incrementally
  45.     Shape(int id, int rows, int columns)
  46.         : id(id), rows(rows), columns(columns) {
  47.         block.resize(rows, vector<bool>(columns));
  48.     }
  49.  
  50.     bool operator==(const Shape& other) const {
  51.         return id == other.id;
  52.     }
  53.  
  54.     void add(int row, int col){
  55.         block[row][col]=1;
  56.     }
  57.  
  58.     vector<OrientedShape> getAllOrientations(){
  59.     	// TODO: to be implemented
  60.     	OrientedShape oshape(1, rows, columns);
  61.     	for(int i=0;i<rows;i++){
  62.     		for(int j=0;j<columns;j++){
  63.     			oshape.add(0, i, j);
  64.     		}
  65.     	}
  66.  
  67.     	return {oshape};
  68.     }
  69. };
  70.  
  71. struct ShapeHash {
  72.     size_t operator()(const Shape& shape) const {
  73.         return hash<int>()(shape.id);
  74.     }
  75. };
  76.  
  77.  
  78. class Board{
  79. public:
  80.     // Assuming the board is a square pyramid with a given height
  81.     int height;
  82.     vector<vector<vector<int>>> a;
  83.  
  84.     Board(){}
  85.  
  86.     Board(int height) : height(height) {
  87.         a.resize(height);
  88.         for (int i = 0; i < height; i++) {
  89.             a[i].resize(height - i, vector<int>(height - i, -1));
  90.         }
  91.     }
  92.  
  93.     // This checks if a given coordinates are valid on the board
  94.     bool exists(int h, int r, int c){
  95.     	return h<height and r < (height-h) and c < (height - h);
  96.     }
  97.  
  98.     // Add a given shape id to the given coordinates on the board
  99.     void add(int height, int row, int col, int id){
  100.  
  101.     	if(not exists(height, row, col)){
  102.     		cout << "Invalid Arguments: Failed to add Shape with "<<id<<" at ("<< height << ", "<< row <<", "<< col <<").\n";
  103.     		return;
  104.     	}
  105.  
  106.     	if(a[height][row][col]!=-1){
  107. 			cout<<"Alert: Overriding the location ("<< height << ", "<< row <<", " << col <<").\n";
  108. 		}
  109.  
  110. 		a[height][row][col] = id;
  111.     }
  112.  
  113.     // Checks if a given shape can be superimposed at the given coordinates on the board
  114.     bool canFit(int h, int r, int c, OrientedShape& oshape){
  115.  
  116.     	for(int ch=0;ch<oshape.height;ch++){
  117.     		for(int cr=0;cr<oshape.rows;cr++){
  118.     			for(int cc=0;cc<oshape.columns;cc++){
  119.     				// If there does not exist a ball at the current loc, continue
  120.     				if(not oshape.a[ch][cr][cc]) continue;
  121.  
  122.     				// Check if the coordinate exists and it is empty
  123.     				if(not exists(h+ch, r+cr, c+cc)) {
  124.     				    return false;
  125.     				}
  126.     				if(a[h+ch][r+cr][c+cc]!=-1) {
  127.     				    return false;
  128.     				}
  129.     			}
  130.     		}
  131.     	}
  132.  
  133.     	return true;
  134.     }
  135.  
  136.  
  137.     // Fits a given shape at a specified location on the board
  138.     void fit(int h, int r, int c, int shapeId, OrientedShape& oshape){
  139.     	for(int ch=0;ch<oshape.height;ch++){
  140.     		for(int cr=0;cr<oshape.rows;cr++){
  141.     			for(int cc=0;cc<oshape.columns;cc++){
  142.     				a[h+ch][r+cr][c+cc]=shapeId;
  143.     			}
  144.     		}
  145.     	}
  146.     }
  147.  
  148.     // Removes a given shape from the board
  149.     void remove(int h, int r, int c, OrientedShape& oshape){
  150.     	for(int ch=0;ch<oshape.height;ch++){
  151.     		for(int cr=0;cr<oshape.rows;cr++){
  152.     			for(int cc=0;cc<oshape.columns;cc++){
  153.     				a[h+ch][r+cr][c+cc]=-1;
  154.     			}
  155.     		}
  156.     	}
  157.     }
  158.  
  159.     // Utility for printing the board
  160.     void print(){
  161.     	for(int i=0;i<height;i++){
  162.     		cout<<"Plane "<<i+1<<":\n";
  163.     		for(int j=0;j<height-i;j++){
  164.     			for(int k=0;k<height-i;k++){
  165.     				cout<<a[i][j][k]<<" ";
  166.     			}
  167.     			cout<<"\n";
  168.     		}
  169.     		cout<<"\n\n";
  170.     	}
  171.     }
  172. };
  173.  
  174.  
  175. class Solver{
  176. public:
  177. 	Board board;
  178.  
  179. 	// List of shapes still pending to be inserted on the board
  180. 	unordered_set<Shape, ShapeHash> shapes;
  181. 	vector<Board> solutions;
  182.  
  183. 	Solver(Board board){
  184. 	    this->board = board;
  185. 	}
  186.  
  187. 	void addShape(Shape& shape){
  188. 		shapes.insert(shape);
  189. 	}
  190.  
  191. 	void backtrack(Board& board, unordered_set<Shape, ShapeHash>& shapesLeft){
  192. 		if(shapes.size()==0){
  193. 			solutions.push_back(board);
  194. 			return;
  195. 		}
  196.  
  197. 		Shape s = *shapesLeft.begin();
  198. 		shapesLeft.erase(s);
  199. 		vector<OrientedShape> oshapes = s.getAllOrientations();
  200.  
  201. 		for(int i=0;i<board.height;i++){
  202.     		for(int j=0;j<board.height-i;j++){
  203.     			for(int k=0;k<board.height-i;k++){
  204.  
  205.     				for(auto oshape: oshapes){
  206.     				    // cout<<i<<" "<<j<<" "<<k<<" "<<s.id<<" "<<shapesLeft.size()<<"\n";
  207.     					if(not board.canFit(i, j, k, oshape)) continue;
  208.     					board.fit(i, j, k, s.id, oshape);
  209.     					backtrack(board, shapesLeft);
  210.     					board.remove(i, j, k, oshape);
  211.     				}
  212.     			}
  213.     		}
  214.     	}
  215.  
  216.     	shapesLeft.insert(s);
  217. 	}
  218.  
  219.  
  220. 	void solve(){
  221. 		solutions.clear();
  222. 		backtrack(board, shapes);
  223.  
  224. 		if(solutions.size()==0){
  225. 			cout<<"No solution found for the given board and shapes configurations!\n";
  226. 			return;
  227. 		}
  228.  
  229. 		cout<<solutions.size()<<" solution(s) found! One of the solution is shown below: \n";
  230. 		solutions[0].print();
  231. 	}
  232.  
  233. 	void printAllSolutions(){
  234. 	    cout<<"There are a total of "<<solutions.size()<<" available solutions for the provided configuration.\n";
  235.  
  236. 	    for(int i=0;i<solutions.size();i++){
  237. 	        cout<<"Solution "<<i+1<<": \n";
  238. 	        solutions[i].print();
  239. 	    }
  240. 	}
  241. };
  242.  
  243. int main(){
  244. 	Board board(2);
  245. 	Shape s1(1, 1, 2), s2(2, 1, 1), s3(3, 1, 2);
  246. 	s1.add(0, 0);
  247. 	s1.add(0, 1);
  248. 	s3.add(0, 0);
  249. 	s3.add(0, 1);
  250. 	s2.add(0, 0);
  251.  
  252. 	Solver solver(board);
  253. 	solver.addShape(s1);
  254. 	solver.addShape(s2);
  255. 	solver.addShape(s3);
  256. 	solver.solve();
  257.  
  258. 	solver.printAllSolutions();
  259. }
  260.  
  261.  
  262.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 solution(s) found! One of the solution is shown below: 
Plane 1:
3 3 
1 1 


Plane 2:
2 


There are a total of 2 available solutions for the provided configuration.
Solution 1: 
Plane 1:
3 3 
1 1 


Plane 2:
2 


Solution 2: 
Plane 1:
1 1 
3 3 


Plane 2:
2
https://ideone.com/hGPqX4
language:
C++14 (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!