アルゴリズム
１、IDA*過去のステップ数と残りの距離見積りの和で与えた閾値を上げながら反復深化
２、双方向探索
ゴールから幅優先探索、前方からIDA*を実行しマッチング
実装中に他の方法で万点取れる目途が付いたので中途半端（というかまだ動いていなかった。。）になっています。
３、端優先
人がパズルを組み立てる時のように端から順に揃えていくアルゴリズム。
４、ステップ実行
指定された回数探索を行い、それまでにゴールに達しなかった場合、過去に見つかった残りの距離見積りが最小のものをスタートに再度探索を繰り返す。（それ以外のノードを捨てる）
５、半自動シミュレーション
上記で解けない問題が7問残った。この残った問題を半自動で解くためのヒントを元に解いていくシュミレーター。
*距離関数としてはブロックを考慮したマンハッタンディスタンスを使用。
*２だけはゴールを広げる程度に幅優先でメモリー使ってますが、基本的にはメモリーを消費しない深さ優先をベースに作っています。辿ったノードを記憶しておく幅優先系ではメモリーが厳しいかなと予想してたんですが、A*で大半の問題を解いた人もいるようですね。
excuse
高得点を取る事だけを目的に書いていたプログラムなので、書きかけのコードが入っていたりグローバル変数使いまくりのコードになってます。きちんと書いて今後公開しますが(気が向いたときw）、一旦提出したそのままのコードをUPします。
150点取れたときの画像(@o@)
実際のソース
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <unistd.h>
#define YOKO_YUSEN
//#define INVD
#define MAXIDTBL 600
#define MAX_STACK_LEVEL 5000
#define MAX_HANPUKU 2000
#define MIN(a,b) ( ((a)<(b) ) ? (a) : (b) )
#define MAX(a,b) ( ((a)>(b) ) ? (a) : (b) )
int matrix_size;
int matrix_size_x;
int matrix_size_y;
int hanpuku_done;
int step_done;
int shurink;
int shurink_mask;
unsigned long long max_count;
unsigned long long count_hanpuku;
int step_dist;
unsigned long long level_counter[MAX_STACK_LEVEL+1];
int level_max_md_counter[MAX_STACK_LEVEL+1];
int level_min_md_counter[MAX_STACK_LEVEL+1];
int moving_history[MAX_STACK_LEVEL+1];
int mh_cnt;
int simflg;
int pre_result_threshold;
char *pre_result_string;
char *mondai;
char *kaitou;
enum STACK {UP, DOWN};
enum MODE2 {MOVE, HANPUKU, STEP, STEP_TARGET, FIX,UNFIX};
struct MATRIX{
char mval[40];
int sp_pos;
};
struct HASH_LIST {
struct MATRIX *matrix;
struct HASH_LIST *next;
};
struct HABA_STACK{
char mval[36];
};
struct Stock_Arr{
char r;
char sp_pos;
char new_pos[4];
int md;
int wd;
int sd;
int id;
int id1;
int id2;
int inv1;
int inv2;
};
struct Stock_Arr stock_arr[MAX_STACK_LEVEL+4];
char New_Pos[36][4];
struct HARR{
int arr[36][36];
int arr_len[36];;
int arr_num;
};
struct MATRIX Matrix;
struct MATRIX Matrix_Min;
struct MATRIX Matrix_Parity;
struct MATRIX Matrix_backup;
struct HARR HArr;
int CrrHarrIdx;
int Threshold;
int Pair_Threshold;
int StackPath[MAX_STACK_LEVEL+1];
int StackPath_Min[MAX_STACK_LEVEL+1];
int *IDTBL1;
int *IDTBL2;
int IDTBL3[MAXIDTBL];
int IDTBL4[MAXIDTBL];
int IDTBL5[MAXIDTBL];
int IDTBL6[MAXIDTBL];
int M_Distance[36][36];
int R_Distance[36][36];
int Parity_omote2ura[36];
int Parity_ura2omote[36];
int max_haba_stack;
struct HASH_LIST **hash_table;
struct HASH_LIST *Hash_List;
int stack_cnt,stack_tail;
int hash_cnt;
int haba;
struct MATRIX *haba_stack;
int min_depth;
int mode=1;
enum Dir {U,L,D,R};
int DirectionX[4] = {0, -1, 0, 1};
int DirectionY[4] = {-1, 0, 1, 0};
char Direction[4] = {'U', 'L', 'D', 'R'};
void dump_harr(){
int i,j;
printf("arr_num:%d\n",HArr.arr_num);
for(i=0;i<HArr.arr_num;i++){
printf("[%d(arr_len:%d) ->",i,HArr.arr_len[i]);
for(j=0;j<HArr.arr_len[i];j++){
printf(" %d",HArr.arr[i][j]);
}
printf("]\n");
}
}
void dump_matrix(struct MATRIX *m){
int i;
char c,p;
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf("\n");
for(i=0;i<matrix_size;i++){
p = m->mval[i];
if(p > 8){
c = p + 'A' - 9;
} else if(p == -2){
c = '=';
} else if(p == -1){
c = '.';
} else {
c = p + '1';
}
printf("%c",c);
if(i%matrix_size_x == matrix_size_x - 1){
printf("\n");
}
}
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf("\n");
}
void dump_matrix2(struct MATRIX *m){
int i,x,y;
char c,p;
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf(" ");
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf("\n");
for(y=0;y<matrix_size_y;y++){
for(x=0;x<matrix_size_x;x++){
i = y*matrix_size_x+x;
p = m->mval[i];
if(p > 8){
c = p + 'A' - 9;
} else if(p == -2){
c = '=';
} else if(p == -1){
c = '.';
} else {
c = p + '1';
}
printf("%c",c);
}
printf(" ");
for(x=0;x<matrix_size_x;x++){
i = y*matrix_size_x+x;
p = m->mval[i];
if(p == -2){
c = '=';
} else if(i == matrix_size-1){
c = '.';
} else if(i > 8){
c = i + 'A' - 9;
} else {
c = i + '1';
}
printf("%c",c);
}
printf("\n");
}
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf(" ");
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf("\n");
}
void mv_koma(int this_r){
int sp_pos,new_sp_pos;
int tgt;
sp_pos = Matrix.sp_pos;
new_sp_pos = New_Pos[sp_pos][this_r];
tgt = Matrix.mval[new_sp_pos];
Matrix.mval[sp_pos] = tgt;
Matrix.mval[new_sp_pos] = -1;
Matrix.sp_pos = new_sp_pos;
}
void make_goal(struct MATRIX *tgt, struct MATRIX *org){
int i,j;
for(i=0, j=0; i<matrix_size; i++){
if(org->mval[i] == -2){
tgt->mval[i] = -2;
} else {
tgt->mval[i] = i;
j=i;
}
}
tgt->mval[j] = -1;
tgt->sp_pos = org->sp_pos;
}
void check_matrix(struct MATRIX *m){
int i;
for(i=0;i<matrix_size;i++){
if(m->mval[i] == -1){
return;
}
}
printf("ERR: not found space\n");
fflush(stdout);
sleep(100);
}
int fix_mval(char p){
int c;
if(p > 8){
c = p + 'A' - 9;
} else if(p == -2){
c = '=';
} else {
c = p + '1';
}
return c;
}
void dump_matrix_parity(struct MATRIX *m){
int i;
char c,p;
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf("\n");
for(i=0;i<matrix_size;i++){
p = m->mval[Parity_omote2ura[i]];
if(p > 8){
c = p + 'A' - 9;
} else if(p == -2){
c = '=';
} else {
c = p + '1';
}
printf("%c",c);
if(i%matrix_size_x == matrix_size_x-1){
printf("\n");
}
}
for(i=0;i<matrix_size_x;i++){
printf("-");
}
printf("\n");
}
int comp(const void *a, const void *b)
{
return R_Distance[matrix_size-1][*(int*)b] - R_Distance[matrix_size-1][*(int*)a];
}
int next_harr_saiki(int *stack_cnt, int *stack, int crr, struct MATRIX *m){
int px, py, cx, cy,nx,ny;
int r1,r2;
int p_cnt;
m->mval[crr] = -2;
stack[stack_cnt[0]] = crr;
stack_cnt[0]++;
px = crr % matrix_size_x;
py = crr / matrix_size_x;
for ( r1 = 0; r1 < 4; r1++ ){
cx = px + DirectionX[r1];
cy = py + DirectionY[r1];
if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
continue;
}
if(m->mval[cy*matrix_size_x+cx] == -2){
continue;
}
p_cnt=0;
for(r2 = 0;r2 < 4;r2++){
nx = cx + DirectionX[r2];
ny = cy + DirectionY[r2];
if ( nx < 0 || ny < 0 || nx >= matrix_size_x || ny >= matrix_size_y ){
continue;
}
if(m->mval[ny*matrix_size_x+nx] == -2){
continue;
}
p_cnt++;
}
if(p_cnt < 2 || m->mval[matrix_size-1] == -2){
next_harr_saiki(stack_cnt, stack, cy*matrix_size_x+cx ,m);
}
}
return 0;
}
int add_harr(int list_len, int *ranked_list, struct MATRIX *mtr){
int stck[36];
int cnt,i,j,found;
cnt = 0;
next_harr_saiki(&cnt,stck,ranked_list[0],mtr);
if(cnt <= 0){
exit(0);
}
for(i=0;i<cnt;i++){
HArr.arr[HArr.arr_num][i] = stck[i];
}
HArr.arr_len[HArr.arr_num] = cnt;
HArr.arr_num++;
for(i=0;i<cnt;i++){
found = 0;
for(j=0;j<list_len;j++){
if(found == 1){
ranked_list[j-1] = ranked_list[j];
} else if(ranked_list[j] == stck[i]){
found = 1;
}
}
}
return list_len - cnt;
}
void make_harr(struct MATRIX *m){
int x,y,i,j,list_len;
int ranked_list[36];
int ranked_list_tmp[36];
struct MATRIX tmp_m;
CrrHarrIdx=0;
HArr.arr_num = 0;
for(i=0,j=0;i<matrix_size-1;i++){
if(m->mval[i] != -2){
ranked_list[j++] = i;
}
}
list_len = j;
if(step_dist == 1){
/*do nothing*/
} else if(step_dist == 2){
for(i=0;i<matrix_size;i++) ranked_list_tmp[i] = ranked_list[i];
for(x=0;x<matrix_size_x;x++)
for(y=0;y<matrix_size_y;y++)
ranked_list[y*matrix_size_x+x] = ranked_list_tmp[y*matrix_size_x+x];
} else {
qsort(ranked_list,list_len,sizeof(int),comp);
}
tmp_m = Matrix;
while(1){
if(list_len <= 0){
break;
}
list_len = add_harr(list_len, ranked_list, &tmp_m);
}
}
void set_m_distance(){
int i,j;
for ( i = 0; i < matrix_size; i++ ){
for ( j = 0; j < matrix_size; j++ ){
M_Distance[i][j] = abs(i/matrix_size_x-j/matrix_size_x) + abs(i%matrix_size_x-j%matrix_size_x);
}
}
}
int pair_saiki(int depth, int pre_r,int crr, int end){
int ret;
int px, py, cx, cy;
int r;
int diff;
int d;
if ( crr == end ){
return 1;
}
d = M_Distance[crr][end];
if ( depth + d > Pair_Threshold ){
return 0;
}
px = crr % matrix_size_x;
py = crr / matrix_size_x;
for ( r = 0; r < 4; r++ ){
cx = px + DirectionX[r];
cy = py + DirectionY[r];
if(pre_r > r){
diff = pre_r - r;
} else {
diff = r - pre_r;
}
if(diff == 2){
continue;
}
if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
continue;
}
if(Matrix.mval[cy*matrix_size_x+cx] == -2){
continue;
}
ret = pair_saiki( depth+1, r , cy*matrix_size_x+cx, end);
if (ret) {
return 1;
}
}
return 0;
}
void set_r_distance(struct MATRIX *m){
int i,j,ret;
ret = 0;
for ( i = 0; i < matrix_size; i++ ){
if(m->mval[i] == -2) continue;
for ( j = 0; j < matrix_size; j++ ){
if(m->mval[j] == -2) continue;
for ( Pair_Threshold = M_Distance[i][j]; Pair_Threshold <= MAX_STACK_LEVEL; Pair_Threshold += 2 ){
ret = pair_saiki(0, -4,i,j);
if ( ret ){
R_Distance[i][j] = Pair_Threshold;
break;
}
}
if(ret < 0){
printf("ERR: R_Distance not fund for [%d][%d]",i,j);
exit(1);
}
}
}
}
int inv_distance1(){
int i,j,inv,val1,val2;
inv = 0;
for (i=0; i<matrix_size; i++) {
val1 = Matrix.mval[i];
if (val1 == -1) continue;
if (val1 == -2) val1 = i;
for (j=i+1; j<matrix_size; j++) {
val2 = Matrix.mval[j];
if (val2 == -1) continue;
if (val2 == -2) val2 = j;
if (val2<val1){
inv++;
}
}
}
return inv;
}
int inv_distance2(){
int i,j,inv,val1,val2;
inv = 0;
for (i=0; i<matrix_size; i++) {
val1 = Matrix_Parity.mval[i];
if (val1 == -1) continue;
if (val1 == -2) val1 = i;
for (j=i+1; j<matrix_size; j++) {
val2 = Matrix_Parity.mval[j];
if (val2 == -1) continue;
if (val2 == -2) val2 = j;
if (val2<val1){
inv++;
}
}
}
return inv;
}
int i_distance(){
int inv1,inv2;
inv1 = inv_distance1();
inv2 = inv_distance2();
return IDTBL1[inv1]+IDTBL2[inv2];
}
int m_distance(){
int md;
int i;
md = 0;
for(i = 0; i < matrix_size; i++){
if ( Matrix.mval[i] < 0 )continue;
md += R_Distance[i][(int)Matrix.mval[i]];
}
return md;
}
int w_distance(){
int md;
int id;
md = m_distance();
id = i_distance();
return MAX(md,id);;
}
int step_distance(){
int sum;
int i,j,k;
char c;
sum = 0;
for(i = 0; i < HArr.arr_len[CrrHarrIdx]; i++){
k = HArr.arr[CrrHarrIdx][i];
c = k;
for(j=0;j<matrix_size;j++){
if(Matrix.mval[j] == c){
sum += R_Distance[j][k];
}
}
}
return sum;
}
int check_goal(){
int i;
for ( i = matrix_size-2; i >= 0; i-- ){
if ( Matrix.mval[i] != i && Matrix.mval[i] != -2 ){
return 0;
}
}
return 1;
}
int check_step_goal(){
int i,j;
for (i=0;i<HArr.arr_len[CrrHarrIdx];i++){
j = HArr.arr[CrrHarrIdx][i];
if ( Matrix.mval[j] != j && Matrix.mval[j] != -2){
return 0;
}
}
return 1;
}
int heuristic_distance(){
return 0;
}
int get_r(char *c){
int this_r;
if(*c=='U' || *c=='u') this_r = 0;
else if(*c=='L' || *c=='l') this_r = 1;
else if(*c=='D' || *c=='d') this_r = 2;
else if(*c=='R' || *c=='r') this_r = 3;
else this_r = -1;
return this_r;
}
int steploop(int pre_depth, int depth, int pre_r){
int i;
int this_r;
int sp_pos,new_sp_pos;
int stack_dir;
int crr_depth;
char *npp;
int found;
int tgt;
int sd;
int harr_arr_len;
struct MATRIX tmp;
harr_arr_len = HArr.arr_len[CrrHarrIdx];
tmp = Matrix;
found = 0;
crr_depth = 0;
stack_dir = DOWN;
sp_pos = Matrix.sp_pos;
stock_arr[crr_depth].sp_pos = sp_pos;
sd = step_distance();
if(sd == 0){
found = 1;
return 1;
}
stock_arr[crr_depth].sd = sd;
if ( sd > Threshold - crr_depth ){
return 0;
}
memcpy(stock_arr[crr_depth].new_pos,New_Pos[Matrix.sp_pos],sizeof(char)*4);
npp = stock_arr[crr_depth].new_pos;
for(i=0;i<4;i++){
if(pre_r - i == 2 || i - pre_r == 2){
npp[i] = -1;
break;
}
}
for(this_r=-1,i=0;i<4;i++){
if(npp[i] >= 0){
this_r = i;
break;
}
}
if(this_r >= 0){
npp[this_r] = -1;
stack_dir = DOWN;
} else {
fprintf(stderr,"ERR11\n");
return 0;
}
while(1){
if(stack_dir == DOWN){
/* use stack_dir, this_r, sp_pos */
if(crr_depth >= MAX_STACK_LEVEL){
fprintf(stderr, "ERR: crr_depth over\n");
return 0;
}
crr_depth++;
if(count_hanpuku > max_count){
hanpuku_done = 1;
return 0;
}
count_hanpuku++;
stock_arr[crr_depth].r = this_r;
new_sp_pos = New_Pos[sp_pos][this_r];
stock_arr[crr_depth].sp_pos = new_sp_pos;
tgt = Matrix.mval[new_sp_pos];
Matrix.mval[sp_pos] = tgt;
Matrix.mval[new_sp_pos] = -1;
Matrix.sp_pos = new_sp_pos;
sd = stock_arr[crr_depth-1].sd;
for(i=0;i<harr_arr_len;i++){
if(HArr.arr[CrrHarrIdx][i] == tgt){
sd += R_Distance[sp_pos][tgt] - R_Distance[new_sp_pos][tgt];
break;
}
}
if(sd == 0){
found = 1;
break;
}
stock_arr[crr_depth].sd = sd;
if ( sd > Threshold - crr_depth ){
sp_pos = new_sp_pos;
stack_dir = UP;
continue;
}
memcpy(stock_arr[crr_depth].new_pos,New_Pos[new_sp_pos],sizeof(char)*4);
npp = stock_arr[crr_depth].new_pos;
for(i=0;i<4;i++){
if(this_r - i == 2 || i - this_r == 2){
npp[i] = -1;
break;
}
}
if(npp[0] >= 0) this_r = 0;
else if(npp[1] >= 0) this_r = 1;
else if(npp[2] >= 0) this_r = 2;
else if(npp[3] >= 0) this_r = 3;
else this_r = -1;
sp_pos = new_sp_pos;
if(this_r >= 0){
npp[this_r] = -1;
stack_dir = DOWN;
} else {
stack_dir = UP;
}
} else { // UP
if(crr_depth == 0){
return 0;
}
crr_depth--;
new_sp_pos = stock_arr[crr_depth].sp_pos;
Matrix.mval[sp_pos] = Matrix.mval[new_sp_pos];
Matrix.mval[new_sp_pos] = -1;
Matrix.sp_pos = new_sp_pos;
npp = stock_arr[crr_depth].new_pos;
for(this_r = -1,i=0;i<4;i++){
if(npp[i] >= 0){
this_r = i;
break;
}
}
sp_pos = new_sp_pos;
if(this_r >= 0){
npp[this_r] = -1;
stack_dir = DOWN;
} else {
stack_dir = UP;
}
}
}
if(found){
for(i=0;i<crr_depth;i++){
StackPath[pre_depth+i] = stock_arr[i+1].r;
}
StackPath[pre_depth+i] = 0;
}
return 1;
}
int stepsaiki(int depth, int pre_r){
int ret;
int px, py, cx, cy;
int r;
int diff;
int wd;
struct MATRIX tmp;
wd = step_distance();
if(wd == 0){
Matrix_backup = Matrix;
return 1;
}
if ( depth + wd > Threshold ){
return 0;
}
count_hanpuku++;
if(count_hanpuku > max_count){
return 0;
}
px = Matrix.sp_pos % matrix_size_x;
py = Matrix.sp_pos / matrix_size_x;
for ( r = 0; r < 4; r++ ){
cx = px + DirectionX[r];
cy = py + DirectionY[r];
if(pre_r > r){
diff = pre_r - r;
} else {
diff = r - pre_r;
}
if(diff == 2){
continue;
}
if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
continue;
}
if(Matrix.mval[cy*matrix_size_x+cx] == -2){
continue;
}
tmp = Matrix;
Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
Matrix.mval[cy*matrix_size_x+cx] = -1;
Matrix.sp_pos = cy*matrix_size_x+cx;
ret = stepsaiki( depth+1, r );
if (ret) {
StackPath[depth] = r;
return 1;
}
Matrix = tmp;
}
return 0;
}
int check_pre_result_path(){
int i,x;
char *c;
int done;
int px,py,cx,cy;
c = pre_result_string;
if(c == NULL || strncmp(c,"not",3)==0){
printf("not checked\n");
return 0;
}
for(x=0;c[x];x++){
done = 0;
for(i=0;i<4;i++){
if(Direction[i] == c[x]){
done = 1;
break;
}
}
if(done == 0){
printf(":ERR0: no direction[%d][%s]\n",x,c);
return 0;
}
px = Matrix.sp_pos % matrix_size_x;
py = Matrix.sp_pos / matrix_size_x;
cx = px + DirectionX[i];
cy = py + DirectionY[i];
if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
printf(":ERR1: bad direction[%d][%s]\n",x,c);
return 0;
}
if(Matrix.mval[cy*matrix_size_x+cx] == -2){
printf(":ERR2: bad direction[%d][%s]\n",x,c);
continue;
}
Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
Matrix.mval[cy*matrix_size_x+cx] = -1;
Matrix.sp_pos = cy*matrix_size_x+cx;
}
if ( m_distance() ){
printf(":ERR3: bad path[%s]\n",c);
return 0;
} else {
printf("%s ok\n",mondai);
return 1;
}
}
int check_id(int inv1, int inv2, struct MATRIX *m){
if( inv1 != inv_distance1()){
return 0;
}
if( inv2 != inv_distance2()){
return 0;
}
return 1;
}
void make_new_pos(struct MATRIX *mtr){
int px, py, cx, cy,i,r;
int npos;
for(i=0;i<matrix_size;i++){
for(r=0;r<4;r++){
px = i % matrix_size_x;
py = i / matrix_size_x;
cx = px + DirectionX[r];
cy = py + DirectionY[r];
npos = cy*matrix_size_x+cx;
if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
New_Pos[i][r] = -1;
continue;
}
if(Matrix.mval[npos] == -2){
New_Pos[i][r] = -1;
continue;
}
New_Pos[i][r] = npos;
}
}
}
void fix_new_pos(struct MATRIX *mtr){
int px, py, cx, cy,i,r;
int npos;
for(i=0;i<matrix_size;i++){
for(r=0;r<4;r++){
px = i % matrix_size_x;
py = i / matrix_size_x;
cx = px + DirectionX[r];
cy = py + DirectionY[r];
npos = cy*matrix_size_x+cx;
if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
New_Pos[i][r] = -1;
continue;
}
if(Matrix.mval[npos] == -2){
New_Pos[i][r] = -1;
continue;
}
New_Pos[i][r] = npos;
}
}
}
int hash_func(struct MATRIX *matrix){
int hash,i;
hash = 1;
for(i=0;i<matrix_size;i++){
hash += 137 + (matrix->mval[i]+13)*i;
}
return hash % max_haba_stack;
}
void dump_hash(){
int i;
struct HASH_LIST *hlp;
for(i=0;i<max_haba_stack;i++){
for (hlp = hash_table[i]; hlp != NULL; hlp = hlp->next){
printf("key:%d\n",i);
dump_matrix(hlp->matrix);
}
}
}
struct MATRIX *get_hash(struct MATRIX *this_matrix, int hash_val){
int found,i;
struct HASH_LIST *hlp;
char *mval;
if(hash_val < 0){
hash_val = hash_func(this_matrix);
}
for (hlp = hash_table[hash_val]; hlp != NULL; hlp = hlp->next){
found = 1;
mval = hlp->matrix->mval;
/**/
for(i=0;i<matrix_size;i++){
if(mval[i] != this_matrix->mval[i]){
found = 0;
break;
}
}
if(found == 1){
return hlp->matrix;
}
}
return NULL;
}
int set_hash(struct MATRIX *this_matrix, int this_r){
int sp_pos,new_sp_pos;
int tgt;
struct HASH_LIST *hash_list, *hlp;
struct MATRIX *m;
int hash_val;
hash_list = &Hash_List[hash_cnt];
memcpy(&haba_stack[stack_tail],this_matrix,sizeof(struct MATRIX));
this_matrix = &haba_stack[stack_tail];
sp_pos = this_matrix->sp_pos;
new_sp_pos = New_Pos[sp_pos][this_r];
tgt = this_matrix->mval[new_sp_pos];
this_matrix->mval[sp_pos] = tgt;
this_matrix->mval[new_sp_pos] = -1;
this_matrix->sp_pos = new_sp_pos;
hash_val = hash_func(this_matrix);
m = get_hash(this_matrix,hash_val);
if(m != NULL){
return 1;
}
hash_list->matrix = &haba_stack[stack_tail];
hash_list->next = NULL;
hash_cnt++;
stack_tail++;
if (hash_table[hash_val] == NULL) {
hash_table[hash_val] = hash_list;
} else {
hlp = hash_table[hash_val];
while (hlp->next != NULL)
hlp = hlp->next;
hlp->next = hash_list;
}
return 0;
}
int haba_tansaku(){
int i;
struct MATRIX *this_matrix;
char *npp;
stack_cnt=0;
stack_tail=0;
haba_stack = malloc(sizeof(struct MATRIX)*max_haba_stack);
if(haba_stack == NULL){
fprintf(stderr,"ERR: cant allocate memmory\n");
exit(0);
}
hash_table = malloc(sizeof(struct HASH_LIST **)*max_haba_stack);
if(hash_table == NULL){
fprintf(stderr,"ERR: cant allocate memmory\n");
exit(0);
}
bzero(hash_table,sizeof(struct HASH_LIST **)*max_haba_stack);
Hash_List = malloc(sizeof(struct HASH_LIST)*max_haba_stack);
if (Hash_List == NULL) {
fprintf(stderr, "ERR: cant alloc memmory\n");
exit(1);
}
this_matrix = &haba_stack[stack_tail];
memcpy(this_matrix,&Matrix,sizeof(struct MATRIX));
stack_tail++;
while(stack_cnt < stack_tail){
this_matrix = &haba_stack[stack_cnt];
npp = New_Pos[this_matrix->sp_pos];
for(i=0;i<4;i++){
if(npp[i] >= 0){
count_hanpuku++;
if(count_hanpuku >= max_count){
return 1;
}
stack_cnt++;
if(stack_tail >= max_haba_stack){
return 1;
}
set_hash(this_matrix,i);
}
}
}
return 0;
}
void free_hash(){
free(hash_table);
free(haba_stack);
free(Hash_List);
hash_table=NULL;
haba_stack=NULL;
Hash_List=NULL;
}
int loop(int depth, int pre_r){
int i;
int wd;
int id;
int md;
int this_r;
int sp_pos,sp_pos_p,new_sp_pos;
int stack_dir;
int crr_depth;
char *npp;
int found;
int tgt;
#ifdef INVD
int new_sp_pos_p;
int val;
int tgt_p;
#endif
int inv1,inv2;
int id1,id2;
struct MATRIX tmp;
struct MATRIX tmp_p;
struct MATRIX *hash_ret;
tmp = Matrix;
tmp_p = Matrix_Parity;
found = 0;
crr_depth = 0;
stack_dir = DOWN;
sp_pos = Matrix.sp_pos;
stock_arr[crr_depth].sp_pos = sp_pos;
sp_pos_p = Parity_omote2ura[sp_pos];
md = m_distance();
inv1 = inv_distance1();
inv2 = inv_distance2();
id1 = IDTBL1[inv1];
id2 = IDTBL2[inv2];
id = id1+id2;
wd = MAX(md,id);
if(wd == 0){
found = 1;
return 1;
}
if(haba == 1){
hash_ret = get_hash(&Matrix, -1);
if(hash_ret != NULL){
return 0;
}
}
#ifdef DEBUG
level_max_md_counter[crr_depth] = md;
level_min_md_counter[crr_depth] = md;
#endif
stock_arr[crr_depth].md = md;
stock_arr[crr_depth].id = id;
stock_arr[crr_depth].inv1 = inv1;
stock_arr[crr_depth].inv2 = inv2;
stock_arr[crr_depth].wd = wd;
if ( wd > Threshold - crr_depth ){
return -1;
}
memcpy(stock_arr[crr_depth].new_pos,New_Pos[Matrix.sp_pos],sizeof(char)*4);
npp = stock_arr[crr_depth].new_pos;
for(this_r=-1,i=0;i<4;i++){
if(npp[i] >= 0){
this_r = i;
break;
}
}
if(this_r >= 0){
npp[this_r] = -1;
stack_dir = DOWN;
} else {
fprintf(stderr,"ERR11\n");
return -1;
}
while(1){
if(stack_dir == DOWN){
/* use stack_dir, this_r, sp_pos */
if(crr_depth >= MAX_STACK_LEVEL){
return -1;
}
crr_depth++;
count_hanpuku++;
level_counter[crr_depth]++;
if(count_hanpuku > max_count){
hanpuku_done = 1;
if(shurink > 0){
return -1;
}
}
stock_arr[crr_depth].r = this_r;
new_sp_pos = New_Pos[sp_pos][this_r];
stock_arr[crr_depth].sp_pos = new_sp_pos;
tgt = Matrix.mval[new_sp_pos];
Matrix.mval[sp_pos] = tgt;
Matrix.mval[new_sp_pos] = -1;
Matrix.sp_pos = new_sp_pos;
md = stock_arr[crr_depth-1].md - R_Distance[new_sp_pos][tgt] + R_Distance[sp_pos][tgt];
if(md > level_max_md_counter[crr_depth]) level_max_md_counter[crr_depth] = md;
if(md < level_min_md_counter[crr_depth]){
level_min_md_counter[crr_depth] = md;
Matrix_Min = Matrix;
min_depth = crr_depth;
for(i=0;i<crr_depth;i++) StackPath_Min[i] = stock_arr[i+1].r;
}
#ifdef INVD
sp_pos_p = Parity_omote2ura[sp_pos];
new_sp_pos_p = Parity_omote2ura[new_sp_pos];
tgt_p = Matrix_Parity.mval[new_sp_pos_p];
Matrix_Parity.mval[sp_pos_p] = tgt_p;
Matrix_Parity.mval[new_sp_pos_p] = -1;
inv1 = stock_arr[crr_depth-1].inv1;
inv2 = stock_arr[crr_depth-1].inv2;
if(this_r == U){
for(i=new_sp_pos+1;i<sp_pos;i++){
if(Matrix.mval[i] < 0){
val = i;
} else {
val = Matrix.mval[i];
}
if (val > tgt){
inv1++;
} else {
inv1--;
}
}
} else if(this_r == D){
for(i=sp_pos+1;i<new_sp_pos;i++){
if(Matrix.mval[i] < 0){
val = i;
} else {
val = Matrix.mval[i];
}
if (val > tgt){
inv1--;
} else {
inv1++;
}
}
} else if(this_r == L){
for(i=new_sp_pos_p+1;i<sp_pos_p;i++){
if(Matrix_Parity.mval[i] < 0){
val = i;
} else {
val = Matrix_Parity.mval[i];
}
if (val > tgt_p){
inv2++;
} else {
inv2--;
}
}
} else /* R */{
for(i=sp_pos_p+1;i<new_sp_pos_p;i++){
if(Matrix_Parity.mval[i] < 0){
val = i;
} else {
val = Matrix_Parity.mval[i];
}
if (val > tgt_p){
inv2--;
} else {
inv2++;
}
}
}
id1 = IDTBL1[inv1];
id2 = IDTBL2[inv2];
id = id1+id2;
stock_arr[crr_depth].id1 = id1;
stock_arr[crr_depth].id2 = id2;
stock_arr[crr_depth].inv1 = inv1;
stock_arr[crr_depth].inv2 = inv2;
wd = MAX(id,md);
stock_arr[crr_depth].wd = wd;
/**/ md = wd;
#endif
if(md == 0){
found = 1;
break;
}
stock_arr[crr_depth].md = md;
if(haba == 1){
hash_ret = get_hash(&Matrix, -1);
if(hash_ret != NULL){
found = crr_depth;
break;
}
}
if ( md > Threshold - crr_depth ){
sp_pos = new_sp_pos;
stack_dir = UP;
continue;
}
memcpy(stock_arr[crr_depth].new_pos,New_Pos[new_sp_pos],sizeof(char)*4);
npp = stock_arr[crr_depth].new_pos;
for(i=0;i<4;i++){
if(this_r - i == 2 || i - this_r == 2){
npp[i] = -1;
continue;
}
}
# ifdef YOKO_YUSEN
if(npp[1] >= 0) this_r = 1;
else if(npp[0] >= 0) this_r = 0;
else if(npp[3] >= 0) this_r = 3;
else if(npp[2] >= 0) this_r = 2;
else this_r = -1;
# else
if(npp[0] >= 0) this_r = 0;
else if(npp[1] >= 0) this_r = 1;
else if(npp[2] >= 0) this_r = 2;
else if(npp[3] >= 0) this_r = 3;
else this_r = -1;
# endif
sp_pos = new_sp_pos;
if(this_r >= 0){
npp[this_r] = -1;
stack_dir = DOWN;
} else {
stack_dir = UP;
}
} else {
if(crr_depth == 0){
return -1;
}
crr_depth--;
new_sp_pos = stock_arr[crr_depth].sp_pos;
Matrix.mval[sp_pos] = Matrix.mval[new_sp_pos];
Matrix.mval[new_sp_pos] = -1;
Matrix.sp_pos = new_sp_pos;
#ifdef INVD
sp_pos_p = Parity_omote2ura[sp_pos];
new_sp_pos_p = Parity_omote2ura[new_sp_pos];
Matrix_Parity.mval[sp_pos_p] = Matrix_Parity.mval[new_sp_pos_p];
Matrix_Parity.mval[new_sp_pos_p] = -1;
#endif
npp = stock_arr[crr_depth].new_pos;
for(this_r = -1,i=0;i<4;i++){
if(npp[i] >= 0){
this_r = i;
break;
}
}
sp_pos = new_sp_pos;
if(this_r >= 0){
npp[this_r] = -1;
stack_dir = DOWN;
} else {
stack_dir = UP;
}
}
}
if(found){
for(i=0;i<crr_depth;i++){
StackPath[i] = stock_arr[i+1].r;
}
StackPath[i] = 0;
}
Matrix = tmp;
return found;
}
int saiki(int depth, int pre_r){
int ret;
int px, py, cx, cy;
int r;
int diff;
int wd;
struct MATRIX tmp;
if ( check_goal() ){
return 1;
}
wd = m_distance();
if ( depth + wd > Threshold ){
return 0;
}
count_hanpuku++;
if(count_hanpuku > max_count){
return 0;
}
px = Matrix.sp_pos % matrix_size_x;
py = Matrix.sp_pos / matrix_size_x;
for ( r = 0; r < 4; r++ ){
cx = px + DirectionX[r];
cy = py + DirectionY[r];
if(pre_r > r){
diff = pre_r - r;
} else {
diff = r - pre_r;
}
if(diff == 2){
continue;
}
if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
continue;
}
if(Matrix.mval[cy*matrix_size_x+cx] == -2){
continue;
}
tmp = Matrix;
Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
Matrix.mval[cy*matrix_size_x+cx] = -1;
Matrix.sp_pos = cy*matrix_size_x+cx;
ret = saiki( depth+1, r );
if (ret) {
StackPath[depth] = r;
Matrix = tmp;
return 1;
}
Matrix = tmp;
}
return 0;
}
int HanpukuShinka(){
int i;
int sdcnt[3],sdsum[3],max=0,maxi=0;
count_hanpuku = 0;
hanpuku_done = 0;
struct MATRIX matrix_backup, matrix_goal;
int ret;
matrix_backup = Matrix;
if(pre_result_threshold > 0){
Threshold = pre_result_threshold;
} else {
Threshold = m_distance();
}
for (ret = 0 ; Threshold <= MAX_STACK_LEVEL; Threshold += 2 ){
if(haba == 1){
make_goal(&matrix_goal,&Matrix);
Matrix = matrix_goal;
haba_tansaku();
Matrix = matrix_backup;
}
#ifdef DEBUG
for(i=0;i<MAX_STACK_LEVEL;i++) level_counter[i] = 0;
for(i=0;i<MAX_STACK_LEVEL;i++) level_max_md_counter[i] = 0;
for(i=0;i<MAX_STACK_LEVEL;i++) level_min_md_counter[i] = 100000;
#endif
ret = loop(0, -4);
if(haba == 1){
free_hash();
if(ret >= 0){
for ( i = 0; i < ret; i++ ) printf("%c",Direction[StackPath[i]]);
fflush(stdout);
break;
}
}
if (ret >= 0){
for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[i]]);
printf("\n");
fflush(stdout);
return 1;
} else {
if(hanpuku_done > 0) {
if(shurink > 0){
hanpuku_done=0;
count_hanpuku = 0;
Matrix=Matrix_Min;
if(shurink_mask > 0){
for(i=0;i<3;i++){
max=0;
maxi=0;
step_dist = i;
make_harr(&Matrix);
sdsum[i] = 0;
for(CrrHarrIdx=0;CrrHarrIdx<HArr.arr_num;CrrHarrIdx++){
if(step_distance() == 0){
sdsum[i] += HArr.arr_len[i];
} else {
break;
}
}
sdcnt[i] = CrrHarrIdx;
if(sdsum[i] > max){
max = sdsum[i];
maxi = i;
}
}
step_dist = maxi;
make_harr(&Matrix);
if(shurink_mask > 1 && sdsum[maxi] > 0){
for(CrrHarrIdx=0;CrrHarrIdx<sdcnt[maxi];CrrHarrIdx++){
for(i=0;i<HArr.arr_len[CrrHarrIdx];i++){
Matrix.mval[HArr.arr[CrrHarrIdx][i]] = -2;
}
}
}
}
Threshold = m_distance();
for ( i = 0; i < min_depth; i++ ) printf("%c",Direction[StackPath_Min[i]]);
shurink--;
continue;
}
break;
}
}
}
if(ret < 2){
printf(" not found in HanpukuShinka(start distance(%d),count_hanpuku(%lld)) for Threshold:%d\n",m_distance(),count_hanpuku,Threshold+2);
fflush(stdout);
return 0;
}
Threshold = m_distance();
for ( ; Threshold <= MAX_STACK_LEVEL; Threshold += 2 ){
haba = 0;
ret = loop(0, -4);
haba = 1;
if (ret != 0){
for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[i]]);
printf("\n");
fflush(stdout);
return 1;
} else {
if(hanpuku_done > 0) {
break;
}
}
}
printf(" not found in HabaYusen & HanpukuShinka(start distance(%d),count_hanpuku(%lld)) for Threshold:%d\n",m_distance(),count_hanpuku,Threshold+2);
fflush(stdout);
return 0;
}
int StepShinka(){
int i;
int ret;
int this_r;
int pre_depth;
count_hanpuku = 0;
this_r = -4;
pre_depth = 0;
for(CrrHarrIdx=0;CrrHarrIdx<HArr.arr_num;CrrHarrIdx++){
ret = 0;
for ( Threshold = step_distance(); Threshold <= MAX_STACK_LEVEL; Threshold++ ){
Matrix_backup = Matrix;
ret = steploop(pre_depth, 0, this_r);
if ( ret > 0 ){
break;
}
if(count_hanpuku > max_count){
break;
}
Matrix = Matrix_backup;
}
if(ret == 0){
printf(" not found in StepShinka(count_hanpuku(%lld)) for Threshold(%d),CrrHarrIdx(%d)\n",count_hanpuku,Threshold+1,CrrHarrIdx);
fflush(stdout);
return 0;
}
for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[pre_depth+i]]);
if(simflg) for ( i = 0; i < Threshold; i++ ) moving_history[mh_cnt++] = StackPath[pre_depth+i];
pre_depth += Threshold;
this_r = StackPath[Threshold-1];
for(i=0;i<HArr.arr_len[CrrHarrIdx];i++){
Matrix.mval[HArr.arr[CrrHarrIdx][i]] = -2;
}
fix_new_pos(&Matrix);
}
printf("\n");
fflush(stdout);
return 1;
}
int get_tgt(char c){
if(c == '='){
c = -2;
} else if('Z' >= c && c >= 'A'){
c = c - 'A' + 9;
} else if('z' >= c && c >= 'a'){
c = c - 'a' + 9;
} else if('9' >= c && c >= '1'){
c = c - '1';
} else if(c == '.' || c == '0'){
c = -1;
} else {
c = -3;
}
return c;
}
void sim(){
int md,i,j;
char buff[MAXIDTBL];
int mode2=-1;
int this_r;
char *c;
int tgt;
struct MATRIX Matrix_org,Matrix_tmp,Matrix_stp;
int ret;
char New_Pos_org[36][4];
Matrix_tmp = Matrix;
Matrix_org = Matrix;
memcpy(New_Pos_org,New_Pos,sizeof(New_Pos));
mh_cnt = 0;
if(kaitou){
printf("%s %s\n",mondai,kaitou);
} else {
printf("%s\n",mondai);
}
printf("\n");
dump_matrix2(&Matrix);
if(kaitou){
c = kaitou;
while(*c){
this_r = get_r(c);
if(this_r < 0) continue;
if(New_Pos[Matrix.sp_pos][this_r]>=0){
mv_koma(this_r);
moving_history[mh_cnt++] = this_r;
}
c++;
}
printf("\n");
dump_matrix2(&Matrix);
}
if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
while(fgets(buff,MAXIDTBL-1,stdin) != NULL){
for(i=0;buff[i];i++){
if(mode == 0){
if(i==0){
if(buff[0] == 'c'){
mode = 1;
dump_matrix2(&Matrix);
if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
break;
}
}
if(buff[i] == '\n'){
dump_matrix2(&Matrix);
if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
break;
}
this_r = -1;
if(buff[i]=='U' || buff[i]=='u') this_r = 0;
if(buff[i]=='L' || buff[i]=='l') this_r = 1;
if(buff[i]=='D' || buff[i]=='d') this_r = 2;
if(buff[i]=='R' || buff[i]=='r') this_r = 3;
if(buff[i] == 0x1b && buff[i+1] == '['){
if(buff[i+2] == 'A'){this_r = 0; i+=2;}
if(buff[i+2] == 'B'){this_r = 2; i+=2;}
if(buff[i+2] == 'C'){this_r = 3; i+=2;}
if(buff[i+2] == 'D'){this_r = 1; i+=2;}
}
if(this_r < 0) continue;
if(this_r < 0) continue;
if(New_Pos[Matrix.sp_pos][this_r]>=0){
mv_koma(this_r);
moving_history[mh_cnt++] = this_r;
}
md = m_distance();
if(md == 0){
dump_matrix2(&Matrix);
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
printf("\n");
printf("done\n");
return;
}
} else { //command mode
if(buff[i] == '\n'){
if(mode2 == STEP){
Matrix_stp = Matrix;
ret = StepShinka();
if(ret <=0){
Matrix = Matrix_stp;
}
md = m_distance();
if(md == 0){
dump_matrix2(&Matrix);
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
printf("\n");
printf("done\n");
return;
}
}
dump_matrix2(&Matrix);
if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
mode2 = -1;
break;
}
if(i==0){
if(buff[0] == 'm') {
if(buff[1] == '\n'){
mode = 0;
if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
break;
} else {
mode2 = MOVE;
}
}else if(buff[0] == 'h') mode2 = HANPUKU;
else if(buff[0] == 's'){
mode2 = STEP;
HArr.arr_num = 1;
HArr.arr_len[0] = 0;
}else if(buff[0] == 'S') mode2 = STEP_TARGET;
else if(buff[0] == 'i'){
printf("mh_cnt:[%d]\n",mh_cnt);
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
printf("\n");
}else if(buff[0] == 'f') mode2 = FIX;
else if(buff[0] == 'F') mode2 = UNFIX;
else if(buff[0] == 'U'){
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
printf("\n");
Matrix = Matrix_org;
Matrix_tmp = Matrix;
memcpy(New_Pos,New_Pos_org,sizeof(New_Pos));
mh_cnt = 0;
if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
break;
}else if(buff[0] == 'm'){
mode2 = MOVE;
}else if(buff[0] == 'N'){
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
printf("\n");
return;
}else if(buff[0] == 'b') {
}else {
dump_matrix(&Matrix);
printf("bad command...ignored.\n");
if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
break;
}
continue;
}
if(mode2 == MOVE){
this_r = -1;
if(buff[i]=='U' || buff[i]=='u') this_r = 0;
if(buff[i]=='L' || buff[i]=='l') this_r = 1;
if(buff[i]=='D' || buff[i]=='d') this_r = 2;
if(buff[i]=='R' || buff[i]=='r') this_r = 3;
if(buff[i] == 0x1b && buff[i+1] == '['){
if(buff[i+2] == 'A'){this_r = 0; i+=2;}
if(buff[i+2] == 'B'){this_r = 2; i+=2;}
if(buff[i+2] == 'C'){this_r = 3; i+=2;}
if(buff[i+2] == 'D'){this_r = 1; i+=2;}
}
if(this_r < 0) continue;
if(New_Pos[Matrix.sp_pos][this_r]>=0){
mv_koma(this_r);
moving_history[mh_cnt++] = this_r;
}
md = m_distance();
if(md == 0){
dump_matrix2(&Matrix);
for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
printf("done\n");
return;
}
}
if(mode2 == STEP){
tgt = get_tgt(buff[i]);
if(tgt >= 0){
HArr.arr[0][HArr.arr_len[0]] = tgt;
HArr.arr_len[0]++;
}
}
if(mode2 == FIX){
tgt = get_tgt(buff[i]);
if(tgt >=0){
if(Matrix.mval[tgt] >= 0){
Matrix_tmp.mval[tgt] = Matrix.mval[tgt];
Matrix.mval[tgt] = -2;
}
}
}
if(mode2 == UNFIX){
tgt = get_tgt(buff[i]);
if(tgt >=0){
if(Matrix_tmp.mval[tgt] >= 0){
Matrix.mval[tgt] = Matrix_tmp.mval[tgt];
Matrix_tmp.mval[tgt] = -3;
}
}
}
//}//for
}//command mode
}
}
}
int set_data(char *in_file){
int i,j;
char *c,*p,*t;
static char buf[1024];
static char str[1024];
int len;
static FILE *fp=NULL;
int x,y;
char *ret;
if(fp == NULL){
fp = fopen(in_file, "r");
#ifdef INVD
for(i=0; i<MAXIDTBL; i++){
IDTBL3[i] = (i/2);
IDTBL4[i] = (i/3) + (i%3);
IDTBL5[i] = (i/4) + (i%4)/2;
IDTBL6[i] = (i/5) + (i%5)/3 + ((i%5)%3);
}
#endif
}
if(fp == NULL){
printf("ERR: cant open [%s]\n",in_file);
exit(0);
}
while(1){
ret = fgets( buf, 1023, fp );
if(ret == NULL){
return 0;
}
if(strchr(buf,',')){
break;
}
}
len = strlen(buf);
buf[len-1] = 0;
if(strstr(buf,"input ")){
strcpy(str,&buf[6]);
mondai = &buf[6];
} else {
strcpy(str,buf);
mondai = buf;
}
t=strchr(mondai,' ');
if(t){
*t++ = 0;
kaitou = t;
if((t =strchr(kaitou,' ')) != NULL){
*t = 0;
}
} else {
kaitou = NULL;
}
// file format
// [4,5,5G3486F7092C1ADJEHBI:not found in HanpukuShinka for Threshold:201]
// [6,5,82935=174ABCD=RHTNJKFLI0PQSOGM ULDDRUULLULULLDRURRDDDLURDRDLLUURDRDRULDR]
str[1] = 0;
str[3] = 0;
matrix_size_x = atoi(str);
matrix_size_y = atoi(&str[2]);
matrix_size = matrix_size_x * matrix_size_y;
c = &str[4];
t = strchr(c,' ');
if(t){
*t++ = 0;
pre_result_string = t;
} else {
pre_result_string = NULL;
}
if(t){
p = strchr(t,':');
} else {
p = NULL;
}
if(p){
*p++ = 0;
pre_result_threshold = atoi(p);
} else {
pre_result_threshold = 0;
}
for ( i = 0; i < matrix_size; i++ ){
if(c[i] == '='){
c[i] = -2;
} else if(c[i] >= 'A'){
c[i] = c[i] - 'A' + 9;
} else {
c[i] = c[i] - '1';
}
Matrix.mval[i] = c[i];
if(c[i] == -1){
Matrix.sp_pos = i;
}
}
for(i=0;i<matrix_size;i++){
x = i % matrix_size_x;
y = i / matrix_size_x;
Parity_omote2ura[i] = x*matrix_size_y+y;
x = i % matrix_size_y;
y = i / matrix_size_y;
Parity_ura2omote[i] = x*matrix_size_x+y;
}
for(i=0;i<matrix_size;i++){
j = Matrix.mval[Parity_ura2omote[i]];
if(j == -1){
Matrix_Parity.mval[i] = j;
} else if(j == -2){
Matrix_Parity.mval[i] = j;
} else {
Matrix_Parity.mval[i] = Parity_omote2ura[j];
}
}
if(matrix_size_x == 3) IDTBL1 = IDTBL3;
if(matrix_size_x == 4) IDTBL1 = IDTBL4;
if(matrix_size_x == 5) IDTBL1 = IDTBL5;
if(matrix_size_x == 6) IDTBL1 = IDTBL6;
if(matrix_size_y == 3) IDTBL2 = IDTBL3;
if(matrix_size_y == 4) IDTBL2 = IDTBL4;
if(matrix_size_y == 5) IDTBL2 = IDTBL5;
if(matrix_size_y == 6) IDTBL2 = IDTBL6;
set_m_distance();
set_r_distance(&Matrix);
make_harr(&Matrix);
make_new_pos(&Matrix);
return 1;
}
int main(int ac, char **av){
char *in;
int ret;
int i,cnt;;
if(ac < 3){
printf("useage:cmd inputfile how [max_count]\n");
exit(0);
}
in = av[1];
if(ac >= 4){
max_count = (long long)atoi(av[3]) * (long long)10000;
} else {
max_count = (long long)MAX_HANPUKU * (long long)10000;
}
haba_stack = malloc(sizeof(struct MATRIX)*max_haba_stack);
if(haba_stack == NULL){
fprintf(stderr,"ERR: cant allocate memmory\n");
exit(0);
}
hash_table = malloc(sizeof(struct HASH_LIST **)*max_haba_stack);
if(hash_table == NULL){
fprintf(stderr,"ERR: cant allocate memmory\n");
exit(0);
}
bzero(hash_table,sizeof(struct HASH_LIST **)*max_haba_stack);
Hash_List = malloc(sizeof(struct HASH_LIST)*max_haba_stack);
while(1){
ret = set_data(in);
if(ret == 0){
exit(0);
}
if(matrix_size_x < 3 || matrix_size_x > 6 || matrix_size_y < 3 || matrix_size_y > 6){
continue;
}
if(strcmp(av[2],"check") == 0){
check_pre_result_path();
continue;
}
if(strcmp(av[2],"sim") == 0){
simflg = 1;
sim();
continue;
}
if(kaitou){
for(cnt=0,i=0;kaitou[i];i++){
if(kaitou[i] != 'U' && kaitou[i] != 'L' && kaitou[i] != 'D' && kaitou[i] != 'R') cnt++;
}
if(cnt == 0){
printf("input %s %s\n", mondai,kaitou);
fflush(stdout);
continue;
}
}
if(strcmp(av[2],"md") == 0){
printf("%d\t%s\n",m_distance(),mondai);
continue;
}
printf("input %s ", mondai);
fflush(stdout);
if(strcmp(av[2],"hanpuku") == 0){
HanpukuShinka();
continue;
}
if(strcmp(av[2],"shurink") == 0){
if(ac >= 5){
shurink = atoi(av[4]);
} else {
shurink = 1;
}
if(ac >=6){
shurink_mask = atoi(av[5]);
} else {
shurink_mask = 0;
}
HanpukuShinka();
continue;
}
if(strcmp(av[2],"haba") == 0){
if(ac >= 5){
max_haba_stack = atoi(av[4]) * 1024*1024/(sizeof(struct MATRIX)*sizeof(struct HASH_LIST **)*2);
} else {
max_haba_stack = 1024*1024/(sizeof(struct MATRIX)*sizeof(struct HASH_LIST **)*2);
}
haba = 1;
HanpukuShinka();
continue;
}
if(strcmp(av[2],"step") == 0){
if(ac >= 5){
step_dist = atoi(av[4]);
} else {
step_dist = 0;
}
StepShinka();
}
if(strcmp(av[2],"matrix") == 0){
dump_matrix(&Matrix);
continue;
}
}
exit(0);
}
0 件のコメント:
コメントを投稿