/* solver.c */
/* Last Change: 2019/05/21 (Tue) 18:09:17. */

#include<limits.h>
#include"solver.h"
#include"io.h"
#include<stdio.h>
#include <list>
#include <bits/stdc++.h>
/* #include<stdlib.h> */
/* #include<string.h> */
/* #include<math.h> */
/* #include<time.h> */

short int connected[MAXLINE]={0}; //if line connected:2, if one end:1, otherwize:0
short int board_beta[MAXSIZE][MAXSIZE]; //big board data
//edge:1~MAXLINE, line:-1~-MAXLINE, none:0, wall:SHRT_MIN
short int rank[MAXBLOCK+1];
short int done_block[MAXBLOCK+1];

void reset_board(void){
	int i,j;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			board_beta[i][j]=0;
	return;
}

void show_blocks(){
	int data[4][4];
	int i,j,k;
	for(i=1;i<blocks;i++){
		printf("block #%d\n",i);
		for(j=1;j<=4;j++){
			printf("x:%d y:%d edge:%d\n",block_data[i][j][0],block_data[i][j][1],block_data[i][j][2]);
		}
	}
	return;
}

void read_data(void){
	//show_blocks();
	return;
}


void translate(void){
	int i,j;
	int minw=MAXSIZE-1,maxw=0,minh=MAXSIZE-1,maxh=0;
	for(i=0;i<MAXSIZE;i++){
		for(j=0;j<MAXSIZE;j++){
			if(board_beta[i][j]){
				if(i>maxw)
					maxw=i;
				if(i<minw)
					minw=i;
				if(j>maxh)
					maxh=j;
				if(j<minh)
					minh=j;
				if(board_beta[i][j]==SHRT_MIN)
					board_beta[i][j]=0;
				else if(board_beta[i][j]<0)
					board_beta[i][j]=-board_beta[i][j];
			}
		}
	}
	for(i=1;i<=blocks;i++){
		/* block_data[i][0]-=minw; */
		/* block_data[i][1]-=minh; */
	}
	for(i=0;i<maxw-minw;i++){
		for(j=0;j<maxh-minh;j++){
			board_data[i][j]=board_beta[i+minw][j+minh];
		}
	}
	return;
}

void init_mino(void){
	int i;
	for(i=1;i<MAXBLOCK+2;i++){
		done_block[i]=0;
	}
}

int check_around(int x,int y){
	if(board_data[x+1][y] || board_data[x][y+1] || board_data[x-1][y] || board_data[x][y-1]||
	board_data[x+1][y+1]||board_data[x+1][y-1]||board_data[x-1][y-1]||board_data[x-1][y+1]) return 1;
	else{
		return 0;
	}
}

void data_mino(int i, int x,int y){
	std::cout << "put mino "<< i << std::endl;
	for(int j=0;j<100;j++){
		for(int k=1;k<5;k++){
			if(board_data[x+block_data[i][k][0]][y+block_data[i][k][1]]!=0){
				break;
			}
			if(check_around(x+block_data[i][k][0],y+block_data[i][k][1])) break;
			if(k==4){
				for(int l=1;l<5;l++){
					if(block_data[i][l][2]!=0){
						board_data[x+block_data[i][l][0]][y+block_data[i][l][1]]=block_data[i][l][2];
					}else{
						board_data[x+block_data[i][l][0]][y+block_data[i][l][1]]=-1;
					}
				}
				block_data[i][0][0]=x;
				block_data[i][0][1]=y;
				 return;
			}
		}

		x+=(j%2);
		y+=((j+1)%2);
		if(x>W || y>H) return;
	}
}

void put_mino(){
	int i,j,k,now;
	std::vector<int> order_w;
	std::vector<int> order_h;
	int map_w[4]={0,0,0,0};
	int map_h[4]={0,0,0,0};
	int len[MAXBLOCK+1];
	int check_block[100];//block in the order_w
	int done_block[100];//fixed block in the order_w
	int end;
	int flag=0;
	order_w.push_back(1); // start from block#1
	int index=0;
	int next=0;
	int x=0;
	auto itr=order_w.begin();
	while(true){
		for(index=order_w.size()-1;index>=0;index--){ // find next block
			if(done_block[order_w[index]]==0){
				next=order_w[index];
				//done_block[next]=1;
				//check_block[next]=1;
				break;
			}
		}
		if(index==-1) break; // if all blocks are searched
		itr=order_w.begin();
		for(int i=0;i<index;i++){//remove index itretor
			itr++;
		}
		order_w.erase(itr);
		std::cout << "block#"<<next << std::endl;
		//make block order
		if(block_data[next][1][0]==block_data[next][2][0]){
			std::cout << "patern 1"<< std::endl;
			if(block_data[next][2][0]==block_data[next][3][0] || block_data[next][2][1]==block_data[next][4][1]){//for I-mino1,L-mino1,T-mino1,S-mino1,Lf-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][4][2];
			}else{
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][4][2];
				map_w[3]=block_data[next][3][2];
			}
		}else if(block_data[next][1][1]==block_data[next][4][1]){//I-mino2
			std::cout << "patern 2"<< std::endl;			
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][4][2];
		}else if(block_data[next][1][1]==block_data[next][2][1]){
			std::cout << "patern 3"<< std::endl;
			if(block_data[next][1][0]==block_data[next][4][0]){//L-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][4][2];
				map_w[2]=block_data[next][2][2];
				map_w[3]=block_data[next][3][2];
			}else{//S-mino2,Sf,mino2,O-mino,L-mino3,Lf-mino1,Lf-mino3,T-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][3][2];
				map_w[2]=block_data[next][4][2];
				map_w[3]=block_data[next][2][2];
			}
		}else if(block_data[next][2][1]==block_data[next][3][1]&&block_data[next][3][0]==block_data[next][4][0]){
			//std::cout << "patern 4"<< std::endl;
				map_w[0]=block_data[next][2][2];
				map_w[1]=block_data[next][4][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][1][2];
		}else{
			//std::cout << "patern 5"<< std::endl;
			map_w[0]=block_data[next][1][2];
			map_w[1]=block_data[next][2][2];
			map_w[2]=block_data[next][3][2];
			map_w[3]=block_data[next][4][2];
		}
		for(int k=0;k<4;k++){
			std::cout << map_w[k]<<" ";
		}
		std::cout << std::endl;
		for(int k=0;k<4;k++){
			if(map_w[k]==0) continue;
			flag=0;
			for(int i=1;i<=blocks;i++){
				if(i==next) continue;
				for(int j=1;j<=4;j++){// find pair block
					if(block_data[i][j][2]==map_w[k]){
						std::cout << k << " " << map_w[k]<< "found at " << i << std::endl;
						if(check_block[i]==1 || done_block[i]==1){
							map_w[k]=0;
						}else{
							check_block[i]=1;
							map_w[k]=i;
						}
						flag=1;
						break;
					}
					//if(j==4) std::cout << "not found " << map_w[k] <<std::endl;
				}
				if(flag==1) break;
			}
		}
		for(int i=0;i<4;i++){
			if(i==2){
				itr=order_w.insert(itr,next);
				itr++;
			}
			if(map_w[i]==0) continue;
			itr=order_w.insert(itr,map_w[i]);
			itr++;
		}
		done_block[next]=1;
		for(int i=0;i<order_w.size();i++){
			printf("%d ",order_w[i]);
		}
		printf("\n");
		x++;
		if(x==10)break;
	}//end of while ture for width
	printf("answer is \n");
	for(int i=0;i<order_w.size();i++){
		printf("%d ",order_w[i]);
	}
	printf("\n");




	printf("\n\nstart making order of height\n");
	for(int i=1;i<=blocks;i++){//init status
		check_block[i]=0;
		done_block[i]=0;
	}
	next=0;
	itr=order_h.begin();
	order_h.push_back(1);
	while(true){//start of while true for height
		for(index=order_h.size()-1;index>=0;index--){ // find next block
			if(done_block[order_h[index]]==0){
				next=order_h[index];
				break;
			}
		}
		//std::cout << "now" << std::endl;
		if(index==-1) break; // if all blocks are searched
		itr=order_h.begin();
		for(int i=0;i<index;i++){//remove index itretor
			itr++;
		}
		order_h.erase(itr);
		std::cout << "block#"<<next << std::endl;
		for(int k=1;k<=4;k++){
			std::cout << block_data[next][k][0];
		}
		std::cout << std::endl;
		//make block order
		if(block_data[next][1][1]==block_data[next][2][1]){
			std::cout << "patern 1"<< std::endl;
			if(block_data[next][3][1]==block_data[next][4][1]){//for I-mino2,S-mino2,Sf-mino2,O-mino
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][3][2];
			}else{//for L-mino3,L-mino4,Lf-mino2,Lf-mino3,T-mino4
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
			}
		}else if(block_data[next][1][0]==block_data[next][4][0]){//I-mino1
			std::cout << "patern 2"<< std::endl;			
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
		}else if(block_data[next][1][0]==block_data[next][2][0]){
			std::cout << "patern 3"<< std::endl;
			if(block_data[next][3][1]==block_data[next][4][1]){//L-mino1,Lf-mino1
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][3][2];
			}else{//T-mino1,Lf-mino4,S-mino1
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][3][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][2][2];
			}
		}else if(block_data[next][1][0]==block_data[next][3][0]&&block_data[next][4][1]!=1){//T-mino3,Sf-mino1
			std::cout << "patern 4"<< std::endl;
				map_h[0]=block_data[next][2][2];
				map_h[1]=block_data[next][1][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
		}else{//L-mino2,T-mino2
			std::cout << "patern 5"<< std::endl;
			map_h[0]=block_data[next][2][2];
			map_h[1]=block_data[next][1][2];
			map_h[2]=block_data[next][4][2];
			map_h[3]=block_data[next][3][2];
		}
		for(int k=0;k<4;k++){
			std::cout << map_h[k]<<" ";
		}
		std::cout << std::endl;
		for(int k=0;k<4;k++){
			if(map_h[k]==0) continue;
			flag=0;
			for(int i=1;i<=blocks;i++){
				if(i==next) continue;
				for(int j=1;j<=4;j++){// find pair block
					if(block_data[i][j][2]==map_h[k]){
						std::cout << k << " " << map_h[k]<< "found at " << i << std::endl;
						if(check_block[i]==1 || done_block[i]==1){
							map_h[k]=0;
						}else{
							check_block[i]=1;
							map_h[k]=i;
						}
						flag=1;
						break;
					}
					//if(j==4) std::cout << "not found " << map_w[k] <<std::endl;
				}
				if(flag==1) break;
			}
		}
		for(int i=0;i<4;i++){
			if(i==2){
				itr=order_h.insert(itr,next);
				itr++;
			}
			if(map_h[i]==0) continue;
			itr=order_h.insert(itr,map_h[i]);
			itr++;
		}
		for(int i=0;i<order_h.size();i++){
			printf("%d ",order_h[i]);
		}
		printf("\n");
		done_block[next]=1;
		x++;
		if(x==1)break;
	}//end of while ture for height

	printf("width is \n");
	for(int i=0;i<order_w.size();i++){
		printf("%d ",order_w[i]);
	}
	printf("\n");

	printf("height is \n");
	for(int i=0;i<order_h.size();i++){
		printf("%d ",order_h[i]);
	}
	printf("\n");

	int put_block[100];
	int hight_c=1,width_c=1;
	int next_put=1;
	for(int i=0;i<blocks;i++){
		hight_c=1;
		width_c=1;
		if(i%2){
			for(int j=0;j<blocks;j++){
				if(put_block[order_w[j]]==0){
					next_put=order_w[j];
					break;
				}
				width_c++;
			}
			for(int j=0;j<blocks;j++){
				if(order_h[j]==next_put){
					break;
				}
				hight_c++;
			}
			data_mino(next_put,width_c,hight_c);
		}else{
			for(int j=0;j<blocks;j++){
				if(put_block[order_h[j]]==0){
					next_put=order_h[j];
					break;
				}
				hight_c++;
			}
			for(int j=0;j<blocks;j++){
				if(order_w[j]==next_put){
					break;
				}
				width_c++;
			}
			data_mino(next_put,width_c,hight_c);
		}
		put_block[next_put]=1;
	}

}


void line(){

}

void solve(void){
	init_mino();
	put_mino();
	line();
	return;
}

void solver(void){
	read_data();
	solve();
	/* shape(); */
	translate();
	return;
}