Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <string>
- using namespace std;
- #define ROTATIONS 1
- // 1-40 max
- #define MAX_CNT 50
- // max count of houses
- //Comment:
- // FILL should be true for good effects
- // if your computer still calculates it in sensible time, increase
- // ROTATIONS. But it increases computational time by ROT^2
- struct pt{
- int x,y;
- };
- pt operator+(pt a,pt b){
- return {a.x+b.x,a.y+b.y};
- }
- vector<vector<pt>> all_sh;
- struct building{
- int ind;
- pt pos;
- };
- bool try_put(pt point, const vector<string>& mp){
- if(point.y<0 || point.y>=mp[0].length())return false;
- if(point.x<0 || point.x>=mp.size())return false;
- if(mp[point.x][point.y]=='#'){return false;}
- return true;
- }
- bool try_put(building bd, const vector<string>& mp,
- vector<string>& newmp, int& trees){
- int ind=bd.ind;
- pt pos=bd.pos;
- for(int i=0;i<6;i++){
- if(!try_put(all_sh[ind][i]+pos,mp))return false;
- }
- newmp=mp;
- trees=0;
- for(int i=0;i<6;i++){
- pt p=all_sh[ind][i]+pos;
- if(mp[p.x][p.y]=='X'){trees++;}
- newmp[p.x][p.y]='#';
- }
- return true;
- }
- int abs(int a){
- if(a<0){return -a;}
- return a;
- }
- int touch(pt a,pt b){
- if(a.x==b.x && a.y==b.y){return 1;}
- if(a.x==b.x){
- if(abs(a.y-b.y)==1){return 2;}
- }
- if(a.y==b.y){
- if(abs(a.x-b.x)==1){return 2;}
- }
- return 0;
- }
- int touch(building bd1,building bd2){
- //returns 0 if buildings cross
- //otherwise, # of common walls
- int ind1=bd1.ind;
- pt p1=bd1.pos;
- int ind2=bd2.ind;
- pt p2=bd2.pos;
- int cnt=0;
- for(int i=0;i<6;i++){
- for(int j=0;j<6;j++){
- int s=touch(p1+all_sh[ind1][i],p2+all_sh[ind2][j]);
- if(s==1){//cross
- return false;
- }
- if(s==2){//touch
- cnt++;
- }
- }
- }
- return cnt;
- }
- void solve(vector<string> mp){
- int n=mp.size();
- //printf("N= %d\n",n);
- int m=mp[0].length();
- //printf("M= %d\n",m);
- vector<building>gardens;
- vector<building>houses;
- bool anything;
- int total_score=0;
- do{
- anything=false;
- int g_best=-2000;
- building gbestg,gbesth;
- vector<string>gmp;
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++){
- for(int k=0;k<ROTATIONS;k++){
- vector<string>newmp;
- int trees;
- building garden={k,{i,j}};
- if(try_put(garden,mp,newmp,trees)){
- //printf("Can put garden at %d,%d with %d trees\n",i,j,trees);
- //for(int a=0;a<newmp.size();a++){
- // printf("%s\n",newmp[a].c_str());
- //}
- int score1=3+2*trees;
- int bestscore2=-20000;
- building besth;
- vector<string>bestmp;
- for(int i2=i-12;i2<i+12;i2++){
- for(int j2=j-12;j2<j+12;j2++){
- for(int k2=0;k2<ROTATIONS;k2++){
- building house={k2,{i2,j2}};
- vector<string>newmp2;
- if(try_put(house,newmp,newmp2,trees)){
- if(touch(garden,house)){
- int score2=-2*trees;
- if(score2>bestscore2){
- bestscore2=score2;
- besth=house;
- bestmp=newmp2;
- }
- }
- }
- }
- }
- }
- score1+=bestscore2;
- if(score1>g_best){
- g_best=score1;
- gbestg=garden;
- gbesth=besth;
- gmp=bestmp;
- }
- }
- }
- }
- }
- //printf("With one more builden: %d\n",g_best);
- //for(int a=0;a<gmp.size();a++){
- // printf("%s\n",gmp[a].c_str());
- //}
- if(g_best>1 || gardens.size()==0){//adding buildings!
- gardens.push_back(gbestg);
- houses.push_back(gbesth);
- mp=gmp;
- total_score+=g_best;
- anything=gardens.size()<MAX_CNT;
- }
- } while(anything);
- for(int i=0;i<houses.size();i++){
- for(int j=0;j<houses.size();j++){
- if(i==j){continue;}
- total_score-=touch(houses[i],houses[j]);
- }
- }
- printf("%d %d\n",houses.size(),total_score);
- for(int i=0;i<houses.size();i++){
- printf("%c %d %d %d ",'a'+houses[i].ind%10,houses[i].ind/10,houses[i].pos.y+1,
- houses[i].pos.x+1);
- printf("%c %d %d %d\n",'a'+gardens[i].ind%10,gardens[i].ind/10,
- gardens[i].pos.y+1,
- gardens[i].pos.x+1);
- }
- }
- vector<pt> basicshapes[10]={
- { {0,0}, {0,1}, {0,2}, {0,3}, {1,1}, {1,2} },
- { {0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {2,0} },
- { {0,0}, {0,1}, {0,2}, {1,3}, {-1,1},{-1,2}},
- { {0,0}, {0,1}, {0,2}, {0,3}, {-1,2},{-1,3}},
- { {0,0}, {0,1}, {0,2}, {0,3}, {1,3}, {2,3} },
- { {0,0}, {0,1}, {0,2}, {0,3}, {0,4}, {0,5} },
- { {0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1} },
- { {0,0}, {0,1}, {0,2}, {1,0}, {1,2}, {2,2} },
- { {0,0}, {1,0}, {1,1}, {1,2}, {1,3}, {2,3} },
- { {0,0}, {0,1}, {0,2}, {1,1}, {2,0}, {2,1} }
- };
- vector<pt> rotateshape(vector<pt>sh){
- vector<pt> ret;
- for(int i=0;i<sh.size();i++){
- ret.push_back({sh[i].y,-sh[i].x});
- }
- return ret;
- }
- void testshape(vector<pt>sh){
- const int MAX = 16;
- char buff[MAX][MAX];
- for(int x=0;x<MAX;x++){
- for(int y=0;y<MAX;y++){
- buff[x][y]='.';
- }
- }
- for(int j=0;j<6;j++){
- buff[sh[j].y+MAX/2][sh[j].x+MAX/2]='x';
- }
- for(int j=0;j<MAX;j++){
- buff[j][MAX-1]=0;
- printf("%s\n",buff[j]);
- }
- }
- int main(){
- for(int i=0;i<10;i++){
- all_sh.push_back(basicshapes[i]);
- }
- for(int i=0;i<30;i++){
- all_sh.push_back(rotateshape(all_sh[i]));
- }
- for(int i=0;i<40;i++){
- for(int j=0;j<6;j++){
- int tmp=all_sh[i][j].x;
- all_sh[i][j].x=all_sh[i][j].y;
- all_sh[i][j].y=tmp;
- }
- }
- int t;
- scanf("%d",&t);
- while(t--){
- int n,m;
- scanf("%d %d",&n,&m);
- vector<string>mp;
- char buff[209];
- for(int i=0;i<n;i++){
- scanf("%s",buff);
- string str(buff);
- mp.push_back(str);
- }
- solve(mp);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement