board_game_solver.cc

#include <string>
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <algorithm>
#include <queue>
#include <list>

using namespace std;

class Solution {
public:
  vector<vector<int>> rotate90(vector<vector<int>> &matrix) {
    int n_row = matrix.size();
    int n_col = n_row == 0? 0 : matrix[0].size();
    
    vector<vector<int>> result(n_col, vector<int>(n_row));

    for (int row = 0; row < n_row; row++) {
      for (int col = 0; col < n_col; col++) {
        int dest_row = col;
        int dest_col = (n_row - 1) - row;
        result[dest_row][dest_col] = matrix[row][col];
      }
    }
    return result;
  }
  
  // start_row and start_col is positio in matrix
  bool is_placable(const vector<vector<int>> &matrix, const vector<vector<int>> &shape, const int start_row, const int start_col) {
    int n_row = matrix.size();
    int n_col = n_row == 0? 0 : matrix[0].size();
    int n_shape_row = shape.size();
    int n_shape_col = n_shape_row == 0? 0 : shape[0].size();

    for (int row = start_row; row < start_row + n_shape_row; row++) {
      for (int col = start_col; col < start_col + n_shape_col; col++) {
        // check if out of boundray
        if (row < 0 || row >= n_row || col < 0 || col >= n_col) return false;
        int shape_row = row - start_row;
        int shape_col = col - start_col;
        if (shape[shape_row][shape_col] == 1 && matrix[row][col] != 0) return false;
      }
    }
    return true;
  }

  void mark(vector<vector<int>> &matrix, const vector<vector<int>> &shape, int start_row, int start_col, int tag) {
    int n_row = matrix.size();
    int n_col = n_row == 0? 0 : matrix[0].size();
    int n_shape_row = shape.size();
    int n_shape_col = n_shape_row == 0? 0 : shape[0].size();

    for (int row = start_row; row < start_row + n_shape_row; row++) {
      for (int col = start_col; col < start_col + n_shape_col; col++) {
        // check if out of boundray
        assert(!(row < 0 || row >= n_row || col < 0 || col >= n_col));
        int shape_row = row - start_row;
        int shape_col = col - start_col;
        if (shape[shape_row][shape_col] == 1) matrix[row][col] = tag;
      }
    }
  }

  void bt(vector<vector<int>> &matrix, vector<vector<vector<int>>> &shapes, int index) {
    if (index == shapes.size()) {
      cout << "----Solution----" << endl;
      print(matrix);
      return;
    }

    int n_row = matrix.size();
    int n_col = n_row == 0? 0 : matrix[0].size();

    auto shape = shapes[index];
    for (int i = 0; i < 4; i++) {
      shape = rotate90(shape);
      for (int row = 0; row < n_row; row++) {
        for (int col = 0; col < n_col; col++) {
          if (is_placable(matrix, shape, row, col)) {
            mark(matrix, shape, row, col, index + 1);
            bt(matrix, shapes, index + 1);
            mark(matrix, shape, row, col, 0);
          }
        }
      }
    }
  }

  void print(vector<vector<int>> &matrix) {
    for (int row = 0; row < matrix.size(); row++) {
      for (int col = 0; col < matrix[0].size(); col++) {
        cout << matrix[row][col] << ", "; 
      }
      cout << endl;
    }
  }
};

int main(int argc, char **argv) {
  Solution sol;

  // vector<vector<int>> matrix(1, vector<int>(1));
  // vector<vector<vector<int>>> shapes;
  // shapes.push_back({{1}});

  // vector<vector<int>> matrix(1, vector<int>(2));
  // vector<vector<vector<int>>> shapes;
  // shapes.push_back({{1}});
  // shapes.push_back({{1}});

  // vector<vector<int>> matrix(2, vector<int>(2));
  // vector<vector<vector<int>>> shapes;
  // shapes.push_back({{1}});
  // shapes.push_back({
      // {1, 0},
      // {1, 1}
      // });
 
  vector<vector<int>> matrix(5, vector<int>(6));
  vector<vector<vector<int>>> shapes;
  shapes.push_back({
      {1, 1, 1, 1}
      });
  shapes.push_back({
      {1, 1},
      {0, 1},
      {0, 1}
      });
  shapes.push_back({
      {1},
      {1}
      });
  shapes.push_back({
      {0, 0, 1, 1},
      {0, 0, 1, 0},
      {1, 1, 1, 1}
      });
  shapes.push_back({
      {1},
      {1},
      {1}
      });
  shapes.push_back({
      {1, 1},
      {0, 1},
      {0, 1},
      {0, 1},
      {1, 1}
      });
  shapes.push_back({
      {1, 1}
      });
  shapes.push_back({
      {1}
      });

  sol.bt(matrix, shapes, 0);

  return 0;
}