Google Developer 2011 DevQuiz

Google Developer Day 2011 Japan を開催します - Google Japan Developer Relations Blog

Google Developer Day 2011 Japanというイベントがあって、それに参加するためには事前にクイズで高得点をとる必要がある。想定解法でなさそうなのが多いけど、私の解答。ちゃんと正攻法で解いた方が楽しかったし、勉強になったかもしれない。

ウォームアップクイズ

多肢選択式の問題が5問。人によって問題が違うらしい。全通りの組み合わせを試す時間は無いけど、1問ずつ回答を変えていけば間に合う。

Web Game

Chrome Extensionの作り方を調べるのをサボって、ただのJavascriptで解いた。全ての組み合わせを試せば良い。

javascript:n=$(".card").length;for(var i=0;i<n;i++)for(var j=i+1;j<n;j++)conc.flip(i),conc.flip(j);

これをオムニボックスにひたすらコピペ。Chromeの場合、「javascript://」とコピペすることができないので、「avascript://〜」とクリップボードに入れておいて、Ctrl+L(オムニボックスにカーソル)→j→Ctrl+V→Enterを繰り返した。最後の方は全部開けるまでに数分かかって面倒。

Go!

PNG画像を展開して、mapに各色を突っ込むコードを書いた。Go言語は変数の定義と代入で記号が違ったり、関数が複数の値を返せたり、あちこち工夫されていて覚えれば便利そう。はてなシンタックスハイライトは対応している。

package main

import (
    "fmt"
    "io"
    "strings"
    "image/png"
)

func CountColor(png_ io.Reader) int {
    img,_ := png.Decode(png_)
    b := img.Bounds()
    m := map[uint32] int{}
    for y:=b.Min.Y;y<b.Max.Y;y++{
        for x:=b.Min.X;x<b.Max.X;x++{
            c := img.At(x,y)
            r,g,b,_ := c.RGBA()
            m[r*256*256+g*256+b] = 1
        }
    }
    return len(m)
}

Android

なぜかプログラム中にソースコードが残っている。*.apkは拡張子を.zipにすると展開できる。com/google/android/apps/gddquiz/gddquiz11serviceにソースがある。解答コード生成部分もあるので、それを呼び出すプログラムを書けば、Androidのシミュレータすら要らない。

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class Android
{
    public static void main(String[] args)
    {
        String mail = "mailaddress@example.com";
        String pass = "passcode00";
        Android a = new Android();
        System.out.println(a.generateAnswerCodeFromPassPhrase(mail,pass));
    }
    
    private String generateAnswerCodeFromPassPhrase(String email, String passPhrase) {
        //  com/google/android/apps/gddquiz/gddquiz11service/DevQuiz11ServiceActivity.java.org
        //  から中身をコピペ
    }
}

class MyUtil
{
    public static String getHexStringFromBytes(byte[] b)
    {
        String r = "";
        for ( int i=0; i<b.length; i++ )
            r += String.format("%02x",b[i]);
        return r;
    }
}

Google Apps Script

以下のPythonスクリプトで変換して手作業でコピペ。シートが20枚なので、できない量ではないけど、面倒。

import json

data = '入力をここに貼り付け'
d = json.loads(data)

for x in d:
    print x["city_name"]
    for y in x["data"]:
        print "%s\t%s\t%s%%"%(y["capacity"],y["usage"],float(y["usage"])/y["capacity"]*100)

一人ゲーム

入力データ中の整数が高々1000000なので、全ての数を半分にする操作を20回繰り返すと全部0になる。後はどこで5の倍数を取り除くかだけなので、全探索することが可能。最初に解いた時はメモ化していたけど、考えてみれば同じ数字の組み合わせになることが、あまりない。

def solve(a):
    if len(a)==0:
        return 0
    else:
        return min(
            solve([x/2 for x in a])+1 if any(x>0 for x in a) else 9999,
            solve([x for x in a if x%5!=0])+1 if any(x%5==0 for x in a) else 9999)

for t in range(input()):
    N = input()
    print solve(map(int,raw_input().split()))

スライドパズル

各ピースの元の位置と現在の位置の間の距離の和をヒューリスティックにした、反復深化A*。使用メモリも少なくて済むし、そのおかげでCPUのキャッシュにも載るだろうから、普通のA*より速いと思う。試してはいないけど。

単に実装して、1問30秒の時間制限で、3638問。あとは最短解という保証は無いけど、なんとか答えを探す。ヒューリスティックを距離の和ではなく、距離の1.5乗(この値はなんとなく)の和にすることで、+810問。距離が遠いピースを優先して動かすようになるはず。細い道がある問題が解けていなかったので、(元に戻す動きを除いた)可能な動きが1つしかなかったら、探索深さを増やさないようにして、+180問。盤面を2分割して片方ずつ、3分割して、……で、+260問。詰まることがないように、半分を揃えてもう半分を揃える時に揃った半分のピースも動かした。それでもダメな問題は1ピースずつ、普通に探索、距離の1.5乗の和で探索、狭い道で探索深さを増やさないようにして探索として、+64問。探索時間を倍にして+14問。それでも解けなかった34問は手動で途中まで解いて、残りをプログラムで計算した。5000問全問回答。

#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <map>
#include <vector>

#pragma warning(disable:4996)       //  sprintf

using namespace std;

typedef unsigned long long qword;



class Board
{
private:
    const static int    W   = 8;        //  幅
    const static int    H   = 8;        //  高さ
    const static int    S   = W*H;      //  面積
    const static int    Dir[4];         //  方向(数字)
    const static char   Dirs[4];        //  方向(文字)
    const static int    Heur2[32];      //  距離をこの関数で変換
    
    int     B[S];       //  盤面(-1:壁 0:空)
    bool    mask[S];    //  trueのピースのみ揃える
    int     D[S][S];    //  最短経路長
    int     space;      //  空白の位置
    int     heur;       //  各ピースと目標位置の距離の和
    int     heur2;
    int     moves[512]; //  手順
    int     step;       //  手数

    void    movec( int m );

    friend ostream &operator<<( ostream &o, const Board &b );
public:
            Board( string b, string m="" );
    bool    canmove( int m ) const;
    void    move( int m );
    void    move( string m );
    void    undo();
    int     getheur() const { return heur; }
    int     getheur2() const { return heur2; }
    bool    finish() const { return heur==0; }
    char    getdir( int d ) const { return Dirs[d]; }
};
ostream &operator<<( ostream &o, const Board &b );



//  それぞれの段階で解けた個数
int step[20] = {0};



string  solve( string problem );
string  itdeep( Board *b, int time, bool heur, bool narrow );
bool    search( Board *b, int depth, int maxdepth );
string  makemask( string problem, int num, int den );



int main()
{
    ifstream in("slide_in.txt");
    ofstream out("slide_out.txt");
    ofstream err("slide_err.txt");

    int LX, RX, UX, DX, N;
    in >> LX >> RX >> UX >> DX >> N;

    //N = 100;

    vector<string> temp(N);
    //  既に計算済みの結果の読み込み
    ifstream tempf("slide_temp.txt");
    for ( int i=0; i<N; i++ )
        getline( tempf, temp[i] );

    int L, R, U, D;
    L = R = U = D = 0;
    int solved = 0;

    int i;
    for ( i=0; i<N; i++ )
    {
        string l;  in >> l;

        cout << i << " " << l << endl;

        string ans;
        if ( temp[i]=="" )
            ans = solve(l);
        else
            ans = temp[i];
        
        int dl, dr, du, dd;
        dl = dr = du = dd = 0;

        for ( int j=0; j<(int)ans.length(); j++ )
        {
            if ( ans[j]=='L' )  dl++;
            if ( ans[j]=='R' )  dr++;
            if ( ans[j]=='U' )  du++;
            if ( ans[j]=='D' )  dd++;
        }

        //if ( L+dl>LX || R+dr>RX || U+du>UX || D+dd>DX )
        //  break;

        L+=dl, R+=dr, U+=du, D+=dd;

        out << ans << endl;
        cout << ans << " " << ans.length() << endl;

        if ( ans != "" )
            solved++;

        if ( ans == "" )
            err << l << endl;

        if ( i % 10 == 9 )
        {
            printf( "%.2f s\n", (double)clock()/CLOCKS_PER_SEC );
            printf( "L %5d/%5d (%6.2f%%)\n", L, LX, (double)L/LX*100 );
            printf( "R %5d/%5d (%6.2f%%)\n", R, RX, (double)R/RX*100 );
            printf( "U %5d/%5d (%6.2f%%)\n", U, UX, (double)U/UX*100 );
            printf( "D %5d/%5d (%6.2f%%)\n", D, DX, (double)D/DX*100 );
            printf( "solved %5d/%5d (%6.2f%%)\n", solved, i+1, (double)solved/(i+1)*100 );

            for ( int i=0; i<sizeof step/sizeof step[0]; i++ )
                cout << " " << step[i];
            cout << endl;
        }
    }
}



//  解く
string solve( string problem )
{
    cout << problem << endl;

    //  途中まで人力で手助け
    const char *assist[][2] = {
        { "6,4,K7123=J===5BDFECH40M=NIG", "URRRRURDLURDLLLLDLUUURRRRDRDLLLLLUURRRRDDLLLLUURRRRDRDDLULDRULDRUUULLLLDDRDLURRRRUULLLLDDRRRRUULLLLDDDRURRRUULLLLDDRDLURDLUUURRRRDDLLLDLUUURRRRDDLLLDLUUURRRRDDLLLDLUUURRRRDRDLLDRURDLLURUULLLLDDDRURR" },
        { "6,6,D762B5AEL31I9NM=04=FHZC=Q8==TUPKVWXY", "DLLLDDRRRRULULLULURRRDRULDRULLLLDRDRRURULLLLLDRRDRRUUULLDDLLURRRURDLURRDDLURDLDLLULDRUUURRRDDLDLLLUUURRRRDDLDLLU" },
        { "6,6,40G9E31DJA56872F=BP===NZVWR=CUXQYTOI", "DDLDDRDRRRRUULDDRUULDRDLLLLLUUURURDLUULDDRURRRURDDDLDRDLURDLLLLLUUURULURDDRULDRUULLDR" },
        { "6,6,721095D=3H=6JK=SICXEGA4=LPQNMTVWR=ZU", "LLLDDRDRRUULURRRDDLLDLLULUURRDRURRDDLDLLLULUURRDRDRDLUUURRDDLLDRURUULLDDRRUULLDDD" },
        { "4,6,D61=9523AI=7N0=8MH=C=EKG", "DDRRUUUULULDLURDLDRDDLUURDDLUUURURDRDDDDLLUUULURURDRDDDDLLULUUUURRDRDDD" },
        { "5,4,BD6A3G=1F9H=E24IJ805", "RUUULLLLDDDRRUUURDLDRDLLLUUURRDDDLLUUURRDDDLLUUURR" },
        { "5,4,B6391C==A2ID045JHFGE", "RUULLLDDRRRUURDLDLLLUURRRRDLDLLLUURRRRDLDLLLUURRR" },
        { "6,6,18F5BA2C9I43D=7HOGKMR0N6L=WSTUJPVXYZ", "LLLDDRRUULLDDRRRULULLDDRRRUUULDDRDLLLUURRUULRRDLURULLLDRULDRRRULLLDRURDLURDRULDRULLDR" },
        { "6,4,271=6CE89BAM=K=53N=0LGHI", "RRUULLLURRDRDRULDDLLUURULDRRDDLLUUURDLLURDDDRR" },
        { "4,6,5234A==8N9=C1D=GHK0J=EMI", "LUULDRULDDRDRRULLULUUURRRDDDDDLLUULUUURRRDDDDDLLULUUUURRRDDDDDLULDRRUUUUULLLDDRDDRRUUUULLL" },
        { "6,6,27=9C=1FMUIH=8EO4ZLK5R=YPABW=SJGVQX0", "UUUULLDRRULLDRRULDLDDDRRUUUULULDDDDDRRUUUULLLDDDLUUURDDDRUUURULDLDDRURULURDDLURDLULDRRULLLULDRDRULDDRUULD" },
        { "6,6,D7365BE=1=4CFJLM=O2R9XSNK0QY=GPVWZUI", "ULURRDLURDRRRUUULLLDDRDRRUUULDRDDDDLLUURRDDLLULUULLUURRDDLLUURRRRDRDDLLDDLUURRRDDLLLUURRRDDLLLULUURRDLDDRRRUULLDLDRRRUULL" },
        { "6,6,=823BUP7=4CHJ==6INLRGO5ZV0KA=YWDSQMX", "DRUULLUURURRDDDLLLUURURRDDDLLDLURRRUUULLDLDDRRRRURUULDDRULDLDDDRRUUULDLDDRRUUULLDDDRRUUUULLDDRRUUULDDDLURDRUUULDDRDLLUURDDLDLDRRRUULULDDDRRUUULLDRULDRRULDRDDLLUURURDDDLLUDLURUURDRDDLL" },
        { "6,5,438C5I12=GLA7=Q6OMD=PRHBJ0SFNT", "LUUURURRDDDDLLLUUURURRRDLURDLDRRUULDLULLLDDDDRRUURURDDLLURRDLURDLLURUULLLDDDDRRRRUULDDRULDRULLDRRUUUULLLLDDDDRRRRLURULLDDRULURDLDR" },
        { "6,5,=E45B6=298ACQJ3TO=DK=0GH=RSFNM", "ULLLDRULDRDRRUUULLDRRDDLLULURUURRDDDDLLULURURDRUULLDR" },
        { "5,4,0H2731B8=4G===56IJFA", "DDDRRRRUUULLDLLDDRRRRUUULLDLULDRRURRDDDLLLLUURRURRDDDLLLLUURRURRDDDLLLLUU" },
        { "6,5,G283C6F1=4BSPANO5RED==TIJH70KQ", "RURUUULLLLDDRRRULURRDDLLLLULURRRRDDLUURDLDLLDDRRRUULLLDDLUURDLUURDRRURDDDLLLUURRURDDDLLLUURRRDDLLLULUURDDDRRRUULLLLDDRRRRUULLLDDRRRUULLLLDDRUULDDRRRRUULLLDDRRRUULLLDDRRRUULLLDDRRRRUUULLDRDDLLLUURRRDDRUULDRUULLDRDDLLLUURRRDDLLLUURRRDDLLLUURRRDDLLLUURRRDDRULDRUULLLLDDRRRUULLLDDRRRUULLLDDRRRUULURRDDDLLLLUURRURRDDDLLLLUURRURRDDDLUULLLDDRRRUULLLDDRRR" },
        { "6,6,E405I=2LA3BC9P8NFO7J1KGZQD=UMHWV=SYT", "LLDDDDDRUULDRDLURULDRULDDRULURULDRDLURRRULLDRRUULLDRUULLDRDRUULLDRRURDDDLULURDRULDRUULLDR" },
        { "4,6,13A=2=CEDF78M95B0L=GIHNK", "URRRUULDRULDLLUURRDDLLUURRDDDLLURRUULLDDDRRUUULLDDRDLURRUULLDDRRRDLUURD" },
        { "4,6,69D8ME1B40HCL2A7N==3KGF5", "DLUURDDLURRRDDDLLLUUURRRDDDLLLUUURRRDDDLLLUU" },
        { "6,4,7LD843E0=2=5KMA1=6=GFINC", "DDRRRRUUULLDDDLULUURRRRDDDLLULLUURRRRDDDLLULDRUUURRDDDLL" },
        { "3,6,12=4D9=H0BACG=865F", "LDLDDRRUULUURDDLURDDDLLUURRULDRDDLLUURRULDRDDLLUURRULDRDDLLUURURDDDLLUURUURDDLUURDDLURDLLDDRRUULLDDRRUULLDDR" },
        { "6,4,E3456C2D1==0KJNF9H87==GI", "ULLLLDDRRRDRUUULLLLDDRRRDRUUULLLLRDDRRDRUUULLLLLDDRRRRDRUUULLLLLDDRRRRDRUUULLLDDLURURRRDDDLULLLUURRRRDDDLULLLLUURRRRRDDDLULLLLUURRRRRDDDLULLL" },
        { "4,4,619=5F23AE=8=07C", "RRUULULDDDRRUULLULDDRURRDDLLUURRDDLLULURDLURRRDDLLUULURRDLDLUURDLDRDR" },
        { "5,5,1C3246980A7E=5=B=JIKGLONM", "LLULDRDLUURRDLURRDDDLDRRULLDLLUUURURRDLLLDDDRRRUUULURDRULDRULLDLURDRRULLDLURDRULDRULLDRRULDLURDLDLDDRRURR" },
        { "6,6,371A4528=G=6=K=HCI=LN=O0WPEXUSVQZRYT", "ULLUURRDDDDLLLULUULURRRRRDDDDLLLULUULURDDDDRRRDLLURDLLUURDLURDRRRUUUULLLLDDDDRULDRDLURDLUURDLLDRURDLURDLLUR" },
        { "6,4,293AH=1=740FLBIKGC=DE=5N", "DLLLLUURRRDDLLLUURRRDDLUULLDDRRRRULLDRUULLLDDRDRUUULLDDRDRU" },
        { "6,6,=93450K72==6VPF8=NDJ=GMCXE===IWQYZUO", "LLLDDLDDDRRRRUUUUULLLDDRDRRDDLLLLULDRUUUUURRRRDDDDDLLLLULDRUUUUURRRRDDDDDLLLL" },
        { "4,6,23481=CF0==75=MJL9GKNIDH", "UURRDRDDLDLLDRRULLDRRULLDRUDRRULLDRULLDRURRULDRDLURUUULURDLRDDDLLLUUUURRDRULLLDDDDRRURUUULLLDDDDDRULDRRUDRULDRUUUUULLLDDDDRRURDDLURDLURULDRDLUURDLD" },
        { "5,4,7C4AF50==J3G6=I21BHD", "URRRDDDLLULULURDLDDRRRRUUULLLLDDDRRRRUUULLLLDDDRRULDRRRUUULLLLDDDRURDR" },
        { "5,5,8GB5A279401=N3E6IO=D==KFH", "DDDLLUURRDDLLULLUURURDDRRDDLLUUUULDRULDLDDRRUUULDLDDRRUULULDDDRRURUULLDRULDLDDRRUUULDLDDRRDRRUUULLLURDLLURDRULLDRRLURDRULLDRRRULDDRUULDRDLULDRRD" },
        { "6,4,9N10567=42IHEK=A3BJDLGMC", "DRULLLLDDDRRRUULULLDDDRRRUULURRDDDLLLLUUURRRDRULDDDLLLUUURRRDDDLLULUURRRDDDLLLUUURRRDDDLLLUUURRRRDDDLLLLUUURRRRDDDLURUULLLLDDDRRRRUUULLLLDDDRRRUUULLLDDDRRRUUULLLDDDRRR" },
        { "6,6,=74638EF9==C2KDGHI50====J=RSTUPVWXYZ", "UUURRRRDDLLLLUURRRRDDLLLUURRRDDLLLLURURRRDDLLLLDLURDLUURDRRRRUULLLLDDDLURRRRRUULLLLDLDRRRRRUULLLLDLDRRRRRUULLLLDDRULDLURDRULLDDRUULDRDLUURDLDDDRR" },
        { "6,6,=2FI8==09OU=DSE354JM=R=AQPWHGB=XK=TZ", "DDDRDLURRRDRUUULULDDDRDRUUULUULDRULDDLLDDRRRDRUUULUULLLDDDDRRRDRUUULUULDDDDRDRUUULLDDRDRUUULLDDRDRUUULLDDLLUURRRRDDDLULLLUULDDRRRRDRUUULLLLLDDRUUUURRDDLLUURDLURRRDDRDDDLULLLUULDDRUUURRRDRDDDLULLLUULDDRUURRDDLLLUURRRRRDDDLULLLULURDDRRUULLURRRDLUURDDLLLUURRRDDLLLURRDLUURDDLULURRDLDRDDLL" },
    };

    for ( int i=0; i<sizeof assist/sizeof assist[0]; i++ )
    if ( assist[i][0] == problem )
    {
        cout << "Assist" << endl;

        Board board(problem);
        board.move(assist[i][1]);

        string a = itdeep( &board, 120, false, false );
        if ( a != "" )
        {
            step[11]++;
            return assist[i][1]+a;
        }
    }

    struct
    {
        const char *name;   //  名前
        int         div;    //  分割数 99で1ピースずつ
        bool        loose;  //  非最短解を許すか
        bool        narrow; //  1本道で深さを増やさない
        int         limit;  //  制限時間
    } param[] = {
        { "Div 1",      1, false, false, 0 },
        { "Div 1 L",    1, true,  false, 0 },
        { "Div 1 N",    1, false, true,  0 },
        { "Div 2",      2, true, false, 0 },
        { "Div 3",      3, true, false, 0 },
        { "Div 4",      4, true, false, 0 },
        { "Div 5",      5, true, false, 0 },
        { "Div 6",      6, true, false, 0 },
        { "1 by 1",    99, false, false, 0 },
        { "1 by 1 L",    99, true, false, 0 },
        { "1 by 1 N",    99, false, true, 0 },
        
    };

    //  制限時間
    int limit[] = { 60, 60, 60, 20, 20, 20, 20, 20, 60, 60, 60 };
    //int limit[] = { 30, 30, 30, 10, 10, 10, 10, 10, 30, 30, 30 };
    //int limit[] = { 3, 3, 3, 1, 1, 1, 1, 1, 3, 3, 3 };

    for ( int i=0; i<sizeof param/sizeof param[0]; i++ )
        param[i].limit = limit[i];

    for ( int i=0; i<sizeof param/sizeof param[0]; i++ )
    {
        cout << param[i].name << endl;

        string answer = "";
        bool f = true;

        int S = (int)problem.length()-4;
        int ln = param[i].div<99 ? param[i].div : S;

        for ( int j=0; j<ln; j++ )
        {
            string m;
            if ( param[i].div < 99 )
                m = makemask(problem,j+1,ln);
            else
                m.resize(j+1,'1'),
                m.resize(S,'0');

            Board board(problem,m);
            board.move(answer);

            string a = itdeep( &board, param[i].limit, param[i].loose, param[i].narrow );

            if ( !board.finish() && a == "" )
            {
                f = false;
                break;
            }

            answer += a;
        }

        if ( f )
        {
            step[i]++;
            return answer;
        }
    }

    return "";
}

string  answer;     //  正解手順
clock_t endtime;    //  終了時刻
clock_t curtime;    //  現在時刻
qword   count;      //  反復深化の関数を呼んだ回数
bool    heur;
bool    narrow;

//  反復深化
string itdeep( Board *b, int time, bool heur, bool narrow )
{
    answer = "";
    count = 0;
    ::heur = heur;
    ::narrow = narrow;

    endtime = clock() + CLOCKS_PER_SEC*time;
    curtime = clock();

    for ( int depth=1; depth<=500; depth++ )
    {
        cout << " " << depth;
        if ( search(b,0,depth) )
            break;
        if ( curtime >= endtime )
            break;
    }
    
    cout << endl;
    
    return answer;
}

//  反復深化
bool search( Board *b, int depth, int maxdepth )
{
    //  時間制限
    count++;
    if ( count % 0x100000 == 0 )
        curtime = clock();
    if ( curtime >= endtime )
        return false;

    //  解けた
    if ( b->finish() )
        return true;
    //  深さ制限
    if ( depth == maxdepth )
        return false;
    //  ヒューリスティック
    if ( depth+b->getheur() > maxdepth )
        return false;
    if ( heur && depth+b->getheur2() > maxdepth )
        return false;
    
    //  narrowが真で、1本道なら深さを増やさない
    int dn = 1;
    if ( narrow )
    {
        int c = 0;
        for ( int i=0; i<4; i++ )
            if ( b->canmove(i) )
                c++;
        if ( c == 1 )
            dn = 0;
    }
    
    //  探索する方向をランダムに
    int r = maxdepth%4;

    for ( int d=0; d<4; d++ )
    if ( b->canmove(d^r) )
    {
        b->move(d^r);

        bool f = search(b,depth+dn,maxdepth);

        b->undo();

        if ( f )
        {
            answer = b->getdir(d^r) + answer;
            return true;
        }
    }

    return false;
}


//  盤面のnum/denのマスクを作成
string  makemask( string problem, int num, int den )
{
    int w = problem[0]-'0';
    int h = problem[2]-'0';

    string m = "";

    int x, y;

    if ( h==den || w!=den && w<h )
    {
        //  縦に分割
        for ( y=0; y<h*num/den; y++ )
            for ( x=0; x<w; x++ )
                m += '1';
        for ( ; y<h; y++ )
            for ( x=0; x<w; x++ )
                m += '0';
    }
    else
    {
        //  横に分割
        for ( y=0; y<h; y++ )
        {
            for ( x=0; x<w*num/den; x++ )
                m += '1';
            for ( ; x<w; x++ )
                m += '0';
        }
    }

    return m;
}



//  Boardの実装
const int   Board::Dir[4]   = { -1, 1, -W, W };
const char  Board::Dirs[4]  = { 'L', 'R', 'U', 'D' };
const int   Board::Heur2[32]= { 0, 1, 2, 5, 8, 11, 14, 18, 22, 27, 31, 36, 41, 46, 52, 58, 64, 70, 76, 82, 89, 96, 103, 110, 117, 125, 132, 140, 148, 156, 164, 172, };

//  場面を示す文字列から構築
Board::Board( string b, string m/*=""*/ )
{
    int w = b[0]-'0';
    int h = b[2]-'0';

    //  盤面
    for ( int p=0; p<S; p++ )
        B[p] = -1;
    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
    {
        char c = b[y*w+x+4];
        int p = (y+1)*W+(x+1);

        switch ( c )
        {
        case '0':  B[p] = 0;  break;
        case '=':  B[p] = -1;  break;
        default: { int t=c<='9'?c-'1':c-'A'+9; B[p] = (t/w+1)*8+t%w+1;  break; }
        }
    }

    //  mask
    for ( int p=0; p<S; p++ )
        mask[p] = true;
    if ( m != "" )
        for ( int y=0; y<h; y++ )
        for ( int x=0; x<w; x++ )
            mask[(y+1)*W+(x+1)] = m[y*w+x]=='1';
    
    //  最短経路長
    for ( int p=0; p<S; p++ )
    for ( int q=0; q<S; q++ )
        D[p][q] = 9999;
    for ( int p=0; p<S; p++ )
    if ( B[p]>=0 )
    {
        D[p][p] = 0;
        for ( int d=0; d<4; d++ )
        if ( B[p+Dir[d]]>=0 )
            D[p][p+Dir[d]] = 1;
    }
    for ( int p=0; p<S; p++ )
    for ( int q=0; q<S; q++ )
    for ( int r=0; r<S; r++ )
        D[q][r] = min( D[q][r], D[q][p]+D[p][r] );

    //  現在の空白の位置・ヒューリスティック
    heur = 0;
    heur2 = 0;
    for ( int p=0; p<S; p++ )
    {
        if ( B[p]==0 )  space = p;
        if ( B[p]>0 && mask[B[p]] )  heur += D[p][B[p]];
        if ( B[p]>0 && mask[B[p]] )  heur2 += Heur2[D[p][B[p]]];
    }

    //  手数
    step = 0;
}

//  動きmが可能か
bool Board::canmove( int m ) const
{
    return B[space+Dir[m]] >= 0  &&                     //  壁ではない
           ( step == 0  ||  m != (moves[step-1]^1) );   //  直前の動きの逆ではない
}

//  動かす
void Board::move( int m )
{
    movec( m );
    moves[step] = m;
    step++;
}

//  動かす(文字列で指定)
void Board::move( string m )
{
    for ( int i=0; i<(int)m.length(); i++ )
        for ( int d=0; d<4; d++ )
        if ( Dirs[d]==m[i] )
            move(d),
            step = 0;       //  長手数になりうるので履歴は削除
}

//  元に戻す
void Board::undo()
{
    step--;
    int m = moves[step];
    movec( m^1 );
}

//  実際に動かす
void Board::movec( int m )
{
    int f = space;          //  (空白の)移動元
    int t = space+Dir[m];   //  (空白の)移動先
    int mp = B[t];          //  移動するピース

    B[f] = mp;
    B[t] = 0;
    space = t;
    if ( mask[mp] )
        heur += D[f][mp] - D[t][mp],
        heur2 += Heur2[D[f][mp]] - Heur2[D[t][mp]];
}

//  出力
ostream &operator<<( ostream &o, const Board &b )
{
    for ( int y=0; y<Board::H; y++ )
    {
        for ( int x=0; x<Board::W; x++ )
        {
            char t[16];
            sprintf( t, "%3d", b.B[y*Board::W+x] );
            cout << t;
        }
        cout << endl;
    }
    cout << endl;
    return o;
}