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; }