2011-09-12

CでDevquiz2011スライドパズル

Devquizへの参加記念にソースコードを晒しておきます。

アルゴリズム

1、IDA*
  過去のステップ数と残りの距離見積りの和で与えた閾値を上げながら反復深化
2、双方向探索
ゴールから幅優先探索、前方からIDA*を実行しマッチング
実装中に他の方法で万点取れる目途が付いたので中途半端(というかまだ動いていなかった。。)になっています。
3、端優先
人がパズルを組み立てる時のように端から順に揃えていくアルゴリズム。
4、ステップ実行
指定された回数探索を行い、それまでにゴールに達しなかった場合、過去に見つかった残りの距離見積りが最小のものをスタートに再度探索を繰り返す。(それ以外のノードを捨てる)
5、半自動シミュレーション
上記で解けない問題が7問残った。この残った問題を半自動で解くためのヒントを元に解いていくシュミレーター。

*距離関数としてはブロックを考慮したマンハッタンディスタンスを使用。
*2だけはゴールを広げる程度に幅優先でメモリー使ってますが、基本的にはメモリーを消費しない深さ優先をベースに作っています。辿ったノードを記憶しておく幅優先系ではメモリーが厳しいかなと予想してたんですが、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 件のコメント:

コメントを投稿