読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1143 : Hexerpents of Hexwamp

問題リンク : Hexerpents of Hexwamp | Aizu Online Judge

問題概要 : 略

解法:

A*

(移動した回数) + (大蛇の頭からゴールまでの距離) > 20 なら枝刈りをした

この問題での2つの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の場合)は単純に6方向みて移動できる場所に移動する
大蛇の長さが2以上の場合は体の偶数番目を動かすか奇数番目を動かすか、
そのノードを動かすか動かさないか、
頭、または尻尾ならば移動する候補が2つあるのでどちらにするか、などを決める再帰を行う
全ての移動先を決定したら、大蛇が死ぬような動きになっていないかどうかを判定する

コード:

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