AOJ 1143 : Hexerpents of Hexwamp
問題リンク : Hexerpents of Hexwamp | Aizu Online Judge
問題概要 : 略
解法：
A*
(移動した回数) + (大蛇の頭からゴールまでの距離) > 20 なら枝刈りをした
この問題での２つの6角座標の距離は以下のように計算する
(x1,y1) から (x2,y2) への距離distを求める (xn,yn) = (x2-x1,y2-y1) dist = max( abs(xn+yn), abs(xn), abs(yn) )
この距離は点(x1,y1)から岩などは無視して最小何回移動すれば(x2,y2)に到達できるのかを表す
平面上でいうマンハッタン距離
後はこれを利用してdijkstraするだけ
なのだが実装が結構大変
大蛇の動き方は割と愚直に実装しても通るっぽい
現在の大蛇の状態から作る亊ができる全ての状態を再帰で作った
大蛇の状態は以下のコードでは struct Data として定義した
vector<Point> snake;//大蛇本体 string next; //next[pos]はsnake[pos]からみてsnake[pos+1]がどの方向にあるのかを表す int cost; //移動した回数
大蛇が頭しかない場合(n == 1の場合)は単純に６方向みて移動できる場所に移動する
大蛇の長さが２以上の場合は体の偶数番目を動かすか奇数番目を動かすか、
そのノードを動かすか動かさないか、
頭、または尻尾ならば移動する候補が２つあるのでどちらにするか、などを決める再帰を行う
全ての移動先を決定したら、大蛇が死ぬような動きになっていないかどうかを判定する
コード:
#include<iostream> #include<vector> #include<cmath> #include<map> #include<set> #include<cstdio> #include<cassert> #include<climits> #include<queue> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define IINF (INT_MAX) #define MAX_N 9 using namespace std; struct Point { int x,y; Point(int x=IINF,int y=IINF):x(x),y(y){} bool operator < (const Point& a)const { if(x != a.x)return x < a.x; return y < a.y; } bool operator == (const Point& a)const { return ( x == a.x && y == a.y ); } }; struct Data { vector<Point> snake; string next; int cost; Data(int cost=IINF):cost(cost){} bool operator < (const Data& a)const { return cost > a.cost; } }; int dx[] = {+0,+1,+1,+0,-1,-1}; int dy[] = {-1,-1,+0,+1,+1,+0}; int n,k; vector<Point> snake; Point goal; string next; set<Point> stone; set<vector<Point> > used; int getDist(const Point& from,const Point& to) { Point np = Point(to.x-from.x,to.y-from.y); return max((int)abs(np.x+np.y), max((int)abs(np.x),(int)abs(np.y))); } bool check(vector<Point>& nsnake,int limit) { set<Point> body; rep(i,limit+1)body.insert(nsnake[i]); if(body.size() != limit+1)return false; rep(i,limit+1) { int cnt = 0; rep(j,6) { int nx = nsnake[i].x + dx[j]; int ny = nsnake[i].y + dy[j]; if(body.find(Point(nx,ny)) != body.end())cnt++; } if(i == 0 && cnt != 1)return false; if(i == n-1 && cnt != 1)return false; if(i == 0 || i == n-1)continue; if(cnt != 2)return false; } return true; } void makeNewSnake(vector<Data>& nsks,vector<Point> &nsnake,string &nnext,const int& cost,int pos,bool sec) { if(pos >= n) { if(check(nsnake,n-1)) { Data d(cost); d.snake = nsnake; d.next = nnext; nsks.push_back(d); } return; } if(n == 1) { Point pre = nsnake[0]; rep(i,6) { int nx = pre.x + dx[i]; int ny = pre.y + dy[i]; nsnake[0] = Point(nx,ny); if(stone.find(nsnake[0]) != stone.end())continue; if(getDist(nsnake[0],goal) + cost > 20)continue; makeNewSnake(nsks,nsnake,nnext,cost,pos+1,sec); } return; } if(sec) { char prec; if(pos != 0) { prec = nnext[pos-1]; rep(j,6) { int x = nsnake[pos-1].x + dx[j]; int y = nsnake[pos-1].y + dy[j]; if(Point(x,y) == nsnake[pos]) { nnext[pos-1] = (char)('0'+j); break; } } } makeNewSnake(nsks,nsnake,nnext,cost,pos+1,!sec); if(pos != 0)nnext[pos-1] = prec; return; } makeNewSnake(nsks,nsnake,nnext,cost,pos+1,!sec); Point pre = nsnake[pos]; char prec = ( pos-1 >= 0 ?nnext[pos-1] : 'X' ); if(pos == 0 || pos == n-1) { int dir; if(pos == 0)dir = ( nnext[pos] - '0' ) % 6; else dir = ( nnext[pos-1] - '0' + 3) % 6; int dd[2] = {+1,-1}; rep(i,2) { int ndir = (dir + dd[i] + 6) % 6; int nx = pre.x + dx[ndir]; int ny = pre.y + dy[ndir]; nsnake[pos] = Point(nx,ny); if(stone.find(nsnake[pos]) != stone.end())continue; if(pos == 0 && getDist(nsnake[pos],goal) + cost > 20)continue; if(pos == n-1) { rep(j,6) { int x = nsnake[pos-1].x + dx[j]; int y = nsnake[pos-1].y + dy[j]; if(Point(x,y) == nsnake[pos]) { nnext[pos-1] = (char)('0'+j); break; } } } makeNewSnake(nsks,nsnake,nnext,cost,pos+1,!sec); } nsnake[pos] = pre; if(pos == n-1)nnext[pos-1] = prec; } else { if(nnext[pos] == nnext[pos-1])return; int dir = ( nnext[pos-1] - '0' + 3 ) % 6 ; int fdir = IINF; if( ( dir + 2 ) % 6 == nnext[pos] - '0' ) { fdir = ( dir + 1 ) % 6; } else if( (nnext[pos] - '0' + 2) % 6 == dir ) { fdir = ( nnext[pos] - '0' + 1 ) % 6; } assert(fdir != IINF); Point pre = nsnake[pos]; nsnake[pos] = Point(pre.x+dx[fdir],pre.y+dy[fdir]); if(stone.find(nsnake[pos]) != stone.end()) { nsnake[pos] = pre; nnext[pos-1] = prec; return; } rep(j,6) { int x = nsnake[pos-1].x + dx[j]; int y = nsnake[pos-1].y + dy[j]; if(Point(x,y) == nsnake[pos]) { nnext[pos-1] = (char)('0'+j); break; } } makeNewSnake(nsks,nsnake,nnext,cost,pos+1,!sec); nsnake[pos] = pre; nnext[pos-1] = prec; } } void compute() { priority_queue<Data> Q; { Data d(0); d.next = next; d.snake.resize(n); rep(i,n) { d.snake[i] = snake[i]; } Q.push(d); used.insert(snake); } while(!Q.empty()) { Data data = Q.top(); Q.pop(); if(data.snake[0] == goal) { printf("%d\n",data.cost); return; } int h = getDist(data.snake[0],goal); if(data.cost + h > 20)continue; vector<Data> nsks; vector<Point> nsnake(n); string nnext = data.next; nsnake = data.snake; makeNewSnake(nsks,nsnake,nnext,data.cost+1,0,false); nnext = data.next; nsnake = data.snake; makeNewSnake(nsks,nsnake,nnext,data.cost+1,0,true); rep(i,nsks.size()) { if(used.find(nsks[i].snake) == used.end()) { used.insert(nsks[i].snake); Q.push(nsks[i]); } } } } int main() { while(scanf("%d",&n),n) { snake.resize(n); stone.clear(); next.clear(); used.clear(); rep(i,n) { scanf("%d %d",&snake[i].x,&snake[i].y); if(i) { bool found = false; rep(j,6) { int nx = snake[i-1].x + dx[j]; int ny = snake[i-1].y + dy[j]; if(nx == snake[i].x && ny == snake[i].y) { found = true; next += (char)('0'+j); break; } } assert(found); } } assert(next.size() == n-1); scanf("%d",&k); rep(i,k) { int u,v; scanf("%d %d",&u,&v); stone.insert(Point(u,v)); } scanf("%d %d",&goal.x,&goal.y); compute(); } return 0; }
