himilk chocolate puzzle solver

choco.cpp

/*! if g++ -g choco.cpp -o choco.out; then ./choco.out piece.txt 9 5; fi
 */




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




using namespace std;




typedef pair<int, int> pos;
typedef vector<pos> piece;
typedef vector<piece> piece_pool;




vector<piece_pool> pools;
const size_t pools_size = 4;
size_t piece_num;
size_t width, height;
vector<vector<int> > box;
const size_t BUFFER = 5;
vector<vector<bool> > rotate_flag;
vector<vector<int> > area_check_box;
size_t min_piece;




piece build_piece(const vector<string>& v){
  size_t x = v[0].find_first_of("*");
  size_t y = 0;
  piece ret;
  for(size_t i = 0; i < v.size(); i++){
    for(size_t j = 0; j < v[i].size(); j++){
      if(v[i][j] == '*'){
        ret.push_back(pos(j-x, i-y));
      }
    }
  }
  sort(ret.begin(), ret.end());
  return ret;
}




piece_pool read_piece(const char* fname){
  ifstream ifs(fname);
  string buf;
  vector<string> temp;
  piece_pool ret;
  while(getline(ifs, buf)){
    size_t pos = buf.find_first_of("*");
    if(pos == string::npos){
      if(temp.size()){
        ret.push_back(build_piece(temp));
        temp.clear();
      }
      continue;
    }
    temp.push_back(buf);
  }
  if(temp.size()){
    ret.push_back(build_piece(temp));
  }
  return ret;
}




void slide(piece& p){
  int min_y = INT_MAX;
  for(size_t i = 0; i < p.size(); i++){
    min_y = min(min_y, p[i].second);
  }
  for(size_t i = 0; i < p.size(); i++){
    p[i].second -= min_y;
  }
  int min_x = INT_MAX;
  for(size_t i = 0; i < p.size(); i++){
    if(p[i].second == 0) min_x = min(min_x, p[i].first);
  }
  for(size_t i = 0; i < p.size(); i++){
    p[i].first -= min_x;
  }
  sort(p.begin(), p.end());
}




piece_pool reflect(const piece_pool& p, int r){
  piece_pool ret = p;
  for(size_t i = 0; i < ret.size(); i++){
    for(size_t j = 0; j < ret[i].size(); j++){
      if(r & 1){
        ret[i][j].first *= -1;
      }
      if(r & 2){
        ret[i][j].second *= -1;
      }
    }
    slide(ret[i]);
  }
  return ret;
}




bool same_piece(const piece& a, const piece& b){
  for(size_t i = 0; i < a.size(); i++){
    if(a[i] != b[i]) return false;
  }
  return true;
}




void init(char** argv){
  char* piece_file = argv[1];
  width = atoi(argv[2]);
  height = atoi(argv[3]);




  pools.clear();
  pools.push_back(read_piece(piece_file));
  for(int i = 1; i <= 3; i++){
    pools.push_back(reflect(pools[0], i));
  }




  piece_num = pools[0].size();
  box = vector<vector<int> >(height + BUFFER * 2, vector<int>(width + BUFFER * 2, 0));
  for(size_t i = BUFFER; i < BUFFER + width; i++){
    for(size_t j = BUFFER; j < BUFFER + height; j++){
      box[j][i] = -1;
    }
  }




  min_piece = SIZE_MAX;
  for(size_t i = 0; i < piece_num; i++){
    min_piece = min(pools[0][i].size(), min_piece);
  }




  area_check_box = box;




  rotate_flag = vector<vector<bool> >(pools_size, vector<bool>(piece_num, true));
  for(size_t j = 0; j < piece_num; j++){
    for(size_t i = 0; i < pools_size; i++){
      rotate_flag[i][j] = true;
      for(size_t k = 0; k < i; k++){
        if(same_piece(pools[i][j], pools[k][j])){
          rotate_flag[i][j] = false;
        }
      }
    }
  }
}




bool check(size_t x, size_t y, size_t rotate_idx, size_t piece_idx){
  piece& p = pools[rotate_idx][piece_idx];
  for(size_t i = 0; i < p.size(); i++){
    if(box[y + p[i].second][x + p[i].first] >= 0) return false;
  }
  return true;
}




void put(size_t x, size_t y, size_t rotate_idx, size_t piece_idx){
  piece& p = pools[rotate_idx][piece_idx];
  for(size_t i = 0; i < p.size(); i++){
    box[y + p[i].second][x + p[i].first] = piece_idx;
  }
}




void remove(size_t x, size_t y, size_t rotate_idx, size_t piece_idx){
  piece& p = pools[rotate_idx][piece_idx];
  for(size_t i = 0; i < p.size(); i++){
    box[y + p[i].second][x + p[i].first] = -1;
  }
}




void print_answer(){
  cout << "answer:" << endl;
  for(size_t y = BUFFER; y < BUFFER + height; y++){
    for(size_t x = BUFFER; x < BUFFER + width; x++){
      printf("%02d ", box[y][x]);
    }
    cout << endl;
  }
}




size_t area_dfs(size_t x, size_t y){
  int dx[] = {1, 0, -1, 0};
  int dy[] = {0, -1, 0, 1};
  if(area_check_box[y][x] >= 0) return 0;    
  area_check_box[y][x] = 0;
  size_t ret = 1;
  for(size_t i = 0; i < 4; i++){
    ret += area_dfs(x + dx[i], y + dy[i]);
  }
  return ret;
}




bool check_area(){
  size_t min_area = SIZE_MAX;
  for(size_t y = BUFFER; y < BUFFER + height; y++){
    for(size_t x = BUFFER; x < BUFFER + width; x++){
      area_check_box[y][x] = box[y][x];
    }
  }
  for(size_t y = BUFFER; y < BUFFER + height; y++){
    for(size_t x = BUFFER; x < BUFFER + width; x++){
      size_t temp = area_dfs(x, y);
      if(temp > 0) min_area = min(min_area, temp);
    }
  }
  return min_area >= min_piece;
}




void dfs(size_t piece_idx){
  if(piece_idx == piece_num){
    print_answer();
    return;
  }
  if(!check_area()){
    return;
  }
  for(size_t x = BUFFER; x < BUFFER + width; x++){
    for(size_t y = BUFFER; y < BUFFER + height; y++){
      for(size_t rotate_idx = 0; rotate_idx < pools_size; rotate_idx++){
        if(!rotate_flag[rotate_idx][piece_idx]) continue;
        if(check(x, y, rotate_idx, piece_idx)){
          put(x, y, rotate_idx, piece_idx);
          dfs(piece_idx + 1);
          remove(x, y, rotate_idx, piece_idx);
        }
      }
    }
  }
}




void print_pool(){
  for(size_t j = 0; j < piece_num; j++){
    printf("piece %zd\n", j);
    for(size_t i = 0; i < pools_size; i++){
      for(size_t k = 0; k < pools[i][j].size(); k++){
        printf("(%d, %d)", pools[i][j][k].first, pools[i][j][k].second);
      }
      cout << endl;
    }
  }
}




void print_flag(){
  for(size_t i = 0; i < pools_size; i++){
    for(size_t j = 0; j < piece_num; j++){
      cout << rotate_flag[i][j];
    }
    cout << endl;
  }
}




int main(int argc, char *argv[]){
  init(argv);
  dfs(0);
  return 0;
}

piece.txt

****




***




 *
***




*
**
*




*
*
*




*
*
*
*




**
**




 *
**
*




 **
**




*
**




*
*
**




***
  *