use Data::Dumper;
use Time::HiRes;
use strict;

## 高速化＆面倒なのでグローバル変数を用意した
my $OPEN  = 0;
my $CLOSE = 1;
my $FORE  = 0;
my $BACK  = 1;
my $START_DISTANCE;
my $GOAL_DISTANCE;
my $PROCESS_S = '';
my $PROCESS_G = '';
my $MAXMV     = 100;
my $MAXMVBK   = 12;
my $MAXLOOP   = 100000;
my $INDEX     = 0;
my $DEBUG     = 1;
my $fh;

## problems.txt を読み込む
unlink 'debug.txt';
unlink 'answer.txt';
open $fh, '<', 'problems.txt';
my $line         = <$fh>;
my $problems_num = <$fh>;
my @problems;
chomp $line;
chomp $problems_num;
my ( $LX, $RX, $UX, $DX ) = $line =~ /^(\d+)\s+(\d+)\s+(\d+)\s+(\d+)$/;

while ( $line = <$fh> ) {
    chomp $line;
    my ( $x, $y, $pattern ) = $line =~ /^(\d+?),(\d+?),(.+)$/;
    push @problems, { cost => $x * $y, line => $line, answer => '' };
}
close $fh;

## 過去に実行した回答をマージする。100手以上の場合はやり直し判定する
my $idx = 0;
if ( -e 'answer_db.txt' ) {
    open $fh, '<', 'answer_db.txt';
    while ( $line = <$fh> ) {
        $line =~ s/[\x01-\x1b]//msxg;
        if ( length $line > 100 ) {
            $line = '';
        }
        if ( $line ne '' ) {
            $problems[$idx]->{answer} = $line;
        }
        $idx++;
    }
    close $fh;
}

## 未回答の部分を処理する
$idx = 0;
for $line (@problems) {
    if ( $line->{answer} eq '' ) {
        $INDEX     = 0;
        $PROCESS_S = '';
        $PROCESS_G = '';
        warn "$line->{line}\n";
        my $begin = time;
        eval { run( $line->{line} ); };
        my $end = time;
        warn "--> time[$INDEX]:", ( $end - $begin ), "\n";
        $line->{answer} = "$PROCESS_S$PROCESS_G";
    }
    open $fh, '>>', 'answer.txt';
    print $fh "$line->{answer}\n";
    close $fh;
}

###--------------------------------------------------------------------------###
# debug
###--------------------------------------------------------------------------###
sub debug {
    my $lv  = shift;
    my $msg = shift;
    return if $lv > $DEBUG;
    open my $fh, '>>', 'debug.txt';
    print $fh $msg;
    close $fh;
}

###--------------------------------------------------------------------------###
# 実行関数
###--------------------------------------------------------------------------###
sub run {
    my $line = shift;
    my ( $x, $y, $pattern ) = $line =~ /^(\d+?),(\d+?),(.+)$/;

    if ( $x * $y <= 9 ) {
        $MAXMV = 10;
    }
    elsif ( $x * $y <= 12 ) {
        $MAXMV = 20;
    }
    elsif ( $x * $y <= 16 ) {
        $MAXMV = 40;
    }
    elsif ( $x * $y <= 20 ) {
        $MAXMV = 60;
    }
    elsif ( $x * $y <= 25 ) {
        $MAXMV = 100;
    }
    elsif ( $x * $y <= 30 ) {
        $MAXMV = 150;
    }
    else {
        $MAXMV = 200;
    }

    my @start = split //, $pattern;
    my @goal;
    for my $e ( sort @start ) {
        push @goal, $e if $e ne '=';
    }
    shift @goal;
    push @goal, '0';

    my $idx = 0;
    for my $e (@start) {
        if ( $e eq '=' ) {
            splice @goal, $idx, 0, '=';
        }
        $idx++;
    }

    a_star_search( join( '', @start ), join( '', @goal ), $x, $y );
}

###--------------------------------------------------------------------------###
# 局面の定義
#   board : 局面
#   prev  : 1 手前の局面
#   space : 空き場所の位置
#   move  : 手数を格納
#   kind  : OPEN と CLOSE の種別を格納
#   dir   : 向を表す値 (FORE or BACK) を格納
#   cost  : 手数 + 2 * マンハッタン距離
#   process : 手順(U,D,L,R)
###--------------------------------------------------------------------------###
sub state {
    my $args = shift;

    if ( $args->{dir} == $FORE ) {
        if ( !defined $args->{prev} ) {
            my @board = split //, $args->{board};
            $args->{cost} = $args->{move} ^ 2 + get_distance( \@board, $START_DISTANCE );
        }
        else {
            my @board = split //, $args->{board};
            my $prev  = $args->{prev};
            my $p     = substr( $args->{board}, $prev->{space}, 1 );
            $args->{cost} = $prev->{cost} + 1 - 2 * $START_DISTANCE->{$p}[ $args->{space} ] + 2 * $START_DISTANCE->{$p}[ $prev->{space} ];
        }
    }
    else {
        if ( !defined $args->{prev} ) {
            my @board = split //, $args->{board};
            $args->{cost} = $args->{move} ^ 2 + get_distance( \@board, $GOAL_DISTANCE );
        }
        else {
            my @board = split //, $args->{board};
            my $prev  = $args->{prev};
            my $p     = substr( $args->{board}, $prev->{space}, 1 );
            $args->{cost} = $prev->{cost} + 1 - 2 * $GOAL_DISTANCE->{$p}[ $args->{space} ] + 2 * $GOAL_DISTANCE->{$p}[ $prev->{space} ];
        }
    }
    return $args;
}

###--------------------------------------------------------------------------###
# 距離を求める
###--------------------------------------------------------------------------###
sub get_distance {
    my $board    = shift;
    my $distance = shift;
    my $v        = 0;
    my $size     = scalar @$board - 1;
    for my $i ( 0 .. $size ) {
        my $p = $board->[$i];
        next if $p eq '0';
        next if $p eq '=';
        $v += $distance->{$p}[$i];
    }
    return $v;
}

###--------------------------------------------------------------------------###
# 隣接リスト算出
###--------------------------------------------------------------------------###
sub adjacent {
    my $board = shift;
    my $x     = shift;
    my $y     = shift;
    my $idx   = 0;
    my $len   = $x * $y;
    my @start = split //, $board;
    my %hash;

    ## 壁の場所
    my %ngcel;
    for my $c (@start) {
        $ngcel{$idx} = 1 if $c eq '=';
        $idx++;
    }

    ## 隣接リスト算出
    $idx = 0;
    for ( my $j = 0; $j < $y; $j++ ) {
        for ( my $i = 0; $i < $x; $i++ ) {
            my @d;
            if ( !$ngcel{$idx} ) {
                my $u = $idx - $x;
                my $d = $idx + $x;
                my $r = $idx + 1;
                my $l = $idx - 1;
                push @d, $u if $j > 0      && !$ngcel{$u};
                push @d, $l if $i > 0      && !$ngcel{$l};
                push @d, $r if $i < $x - 1 && !$ngcel{$r};
                push @d, $d if $j < $y - 1 && !$ngcel{$d};
                $hash{$idx} = [@d];
            }
            $idx++;
        }
    }
    return \%hash;
}

###--------------------------------------------------------------------------###
# 距離表の作成
###--------------------------------------------------------------------------###
sub make_distance_table {
    my $board = shift;
    my $wide  = shift;
    my @board = split //, $board;

    my $size  = scalar @board - 1;
    my $table = {};
    for my $i ( 0 .. $size ) {
        my $p = $board[$i];

        next if $p eq '0';
        next if $p eq '=';
        my $x1 = int $i / $wide;
        my $y1 = int $i % $wide;
        for my $j ( 0 .. $size ) {
            my $x2 = int $j / $wide;
            my $y2 = int $j % $wide;
            $table->{$p}[$j] += abs( $x1 - $x2 );    # * abs($x1 - $x2);
            $table->{$p}[$j] += abs( $y1 - $y2 );    # * abs($y1 - $y2);
        }
    }
    return $table;
}

###--------------------------------------------------------------------------###
# start -> goal の回答表示
###--------------------------------------------------------------------------###
sub print_answer {
    my $state = shift;
    my $x     = shift;
    if ( defined $state ) {
        print_answer( $state->{prev} );

        $PROCESS_S .= $state->{process};
        debug( 0, $state->{board} );
        debug( 0, " : " );
        debug( 0, "[S]$PROCESS_S" );
        debug( 0, "\n" );
    }
}

###--------------------------------------------------------------------------###
# goal -> start の回答表示
###--------------------------------------------------------------------------###
sub print_answer_goal {
    my $state_org = shift;
    my $x         = shift;
    my $process   = shift;
    $PROCESS_G = $process;

    my $state = {%$state_org};
    while ( defined $state ) {
        $PROCESS_G .= ( $state->{process} || '' );
        debug( 0, $state->{board} );
        debug( 0, " : " );
        debug( 0, "[G]$PROCESS_S $PROCESS_G" );
        debug( 0, "\n" );
        $state = $state->{prev};
    }
    my @mv = split //, "$PROCESS_S$PROCESS_G";
    for my $i (@mv) {
        if ( $i eq 'L' ) {
            $LX--;
        }
        elsif ( $i eq 'R' ) {
            $RX--;
        }
        elsif ( $i eq 'D' ) {
            $DX--;
        }
        elsif ( $i eq 'U' ) {
            $UX--;
        }
    }
    if ( $LX <= 0 || $RX <= 0 || $UX <= 0 || $DX <= 0 ) {
        warn "$LX, $RX, $UX, $DX\n";
        exit;
    }
    warn "$PROCESS_S$PROCESS_G\n";
}

###--------------------------------------------------------------------------###
# 双方向の A* アルゴリズム
###--------------------------------------------------------------------------###
sub a_star_search {
    my $start = shift;
    my $goal  = shift;
    my $x     = shift;
    my $y     = shift;

    my $adjacent = adjacent( $start, $x, $y );
    my @q;
    my $qlist;
    my %table;
    my $key;
    my $state;

    ## ゴールの登録
    $GOAL_DISTANCE = make_distance_table( $start, $x );
    $state = state( { board => $goal, space => index( $goal, "0" ), prev => undef, move => 0, dir => $BACK, kind => $OPEN } );
    push @q, $state->{cost};
    push @{ $qlist->{ $state->{cost} } }, $state;
    $table{ $state->{board} } = $state;

    ## スタートの登録
    $START_DISTANCE = make_distance_table( $goal, $x );
    $state = state( { board => $start, space => index( $start, "0" ), prev => undef, move => 0, dir => $FORE, kind => $OPEN } );
    push @q, $state->{cost};
    push @{ $qlist->{ $state->{cost} } }, $state;
    $table{ $state->{board} } = $state;

    while (@q) {
        $INDEX++;
        my $begin = [Time::HiRes::gettimeofday];
        ## コストキューをsortする。単純数値比較なのでperlでも非常に高速処理可能
        @q = sort { $a <=> $b } @q;
        my $qmin = shift @q;

        ## 大胆な枝狩り。キューを一定数以上ためない
        splice @q, $MAXMV * 50;

        ## 最小コストの局面はどれを処理するかはランダムで運にお任せ
        my $qlistlen = scalar @{ $qlist->{$qmin} } - 1;
        $state = splice @{ $qlist->{$qmin} }, int( rand($qlistlen) ), 1;
        #$state = pop @{ $qlist->{$qmin} };

        ## goalからある手数まで局面を生成したら、startからの局面でマッチングを待ち受けるため処理終了
        if ( $state->{dir} == $BACK && $state->{move} > $MAXMVBK ) {
            next;
        }

        ## 廃棄オブジェクト(未生成の継続ノードがない)
        if ( defined $state->{kind} && $state->{kind} == $CLOSE ) {
            next;
        }
        ## 最大移動制限数をオーバーしたらその手順から先の探索を諦める
        if ( $state->{move} > $MAXMV ) {
            $state->{kind} = $CLOSE;
            next;
        }
        ## 総数5万手以上はあきらめる
        if ( $INDEX > $MAXLOOP ) {
            warn "GIVE UP!!\n";
            undef %table;
            undef $qlist;
            undef @q;
            undef $state;
            return;
        }

        ## 移動先候補
        my $cels = $adjacent->{ $state->{space} };
        for my $c (@$cels) {
            ## work の中でセルの入れ替え
            my @board = split //, $state->{board};
            $board[ $state->{space} ] = $board[$c];
            $board[$c] = 0;
            $key = join '', @board;

            my $process = '';
            ## start->goalの場合の手順記憶
            if ( $state->{dir} == $FORE ) {
                my $dt = $c - $state->{space};
                $process = $dt == -1 ? 'L' : $dt == 1 ? 'R' : $dt < 0 ? 'U' :'D';
            }
            ## goal->startの場合の手順記憶
            else {
                my $dt = $c - $state->{space};
                $process = $dt == -1 ? 'R' : $dt == 1 ? 'L' : $dt < 0 ? 'D' :'U';
            }

            ## 同一局面がある
            my $state_processed;
            if ( exists $table{$key} ) {
                $state_processed = $table{$key};
                ## FORE = BACK で突合されたら終了
                if ( $state->{dir} != $state_processed->{dir} ) {
                    if ( $state->{dir} == $FORE ) {
                        print_answer( $state, $x );
                        print_answer_goal( $state_processed, $x, $process );
                    }
                    else {
                        print_answer( $state_processed, $x );
                        print_answer_goal( $state, $x, $process );
                    }
                    undef %table;
                    undef $qlist;
                    undef @q;
                    undef $state;
                    return;
                }

                ## 同一方向で同じ局面に遭遇した。過去の手数が多いときの処理。過去手順の探索は終了させる。
                if ( $state_processed->{move} > $state->{move} + 1 ) {
                    if ( $state_processed->{kind} == $OPEN ) {
                        $state_processed->{kind} = $CLOSE;
                        $table{$key} = state( { process => $process, board => $key, space => $c, prev => $state, move => $state->{move} + 1, dir => $state->{dir} } );
                        ## goalから局面を生成するコストはある手順以内は 1 にする
                        my $cost = $table{$key}->{cost};
                        $cost = 1 if $state->{dir} == $BACK && $state->{move} < $MAXMVBK;
                        push @q, $cost;
                        push @{ $qlist->{$cost} }, $table{$key};
                    }
                    else {
                        $state_processed->{prev} = $state;
                        $state_processed->{cost} = $state_processed->{cost} - $state_processed->{move} + $state->{move} + 1;
                        $state_processed->{move} = $state->{move} + 1;
                        $state_processed->{kind} = $OPEN;
                        ## goalから局面を生成するコストはある手順以内は 1 にする
                        my $cost = $state_processed->{cost};
                        $cost = 1 if $state->{dir} == $BACK && $state->{move} < $MAXMVBK;
                        push @q, $cost;
                        push @{ $qlist->{$cost} }, $state_processed;
                    }
                }
            }
            ## 同一局面がないので手順に加える
            else {
                $table{$key} = state( { process => $process, board => $key, space => $c, prev => $state, move => $state->{move} + 1, dir => $state->{dir}, kind => $OPEN } );
                ## goalから局面を生成するコストはある手順以内は 1 にする
                my $cost = $table{$key}->{cost};
                $cost = 1 if $table{$key}->{dir} == $BACK && $table{$key}->{move} < $MAXMVBK;
                push @q, $cost;
                push @{ $qlist->{$cost} }, $table{$key};
            }
        }
        ## 現手順の子ノードは展開済みで探査終了
        $state->{kind} = $CLOSE;
        if ( $INDEX % 1000 == 0 ) {
            my $elapsed = Time::HiRes::tv_interval($begin);
            my $len     = scalar @q;
            #warn "dir=$state->{dir}  IDX=$INDEX($len): time=$elapsed : mv=board=$state->{move} : board=$state->{board}\n";
        }
    }
    undef %table;
    undef $qlist;
    undef @q;
    undef $state;
}