// 2006国内予選C 六角沼の六角大蛇 #include #include #include using namespace std; char dx[] = {0,1,1,0,-1,-1}; char dy[] = {-1,-1,0,1,1,0}; // 蛇の体の座標を片っ端からvectorに突っ込み,setで重複判定を行う. // prev : 今までにチェックした状態の集合 // cur : 前のステップで新たに生成された状態の集合 // next : 現在のステップで新たに生成された状態の集合 set< vector > prev; vector< vector > cur, next; int x[8], y[8], u[100], v[100], n, k, X, Y, ans; // 蛇の胴体を動かしてみる関数. // step : 現在のstep数 // pos : 今動かす胴体の番号 // premove : 1個前の胴体を動かしたか void move(int step, int pos){ if(ans != 20) return; // 全部の胴体を動かしてみた if(pos >= n) { // 蛇の死亡判定をする.全て動かしてからチェックしないと全状態を生成できない(と思う). // 隣り合わないはずの胴体が隣り合ってる for(int i=0;i v; for(int i=0;i 19) continue; if(pos == 1 && step+max(abs(X-x[0]),abs(Y-y[0]))+abs(max(abs(X-nx),abs(Y-ny))-1) > 19) continue; // 胴体重なり判定 for(int j=0;j0){ for(int k=0;k<6;k++) if(x[pos-1]+dx[k] == nx && y[pos-1]+dy[k] == ny) flagF = true; if(!flagF) continue; } if(pos >::iterator it; while(cin >> n, n){ for(int i=0;i> x[i] >> y[i]; cin >> k; for(int i=0;i> u[i] >> v[i]; cin >> X >> Y; ans = 20; // 初期配置を表すvector vector v; for(int i=0;i