UVa 11163 : Jaguar King

問題リンク : http://uva.onlinejudge.org/external/111/11163.html

問題概要：
N匹のジャガーがいる
最初N匹のジャガーは１からNまで昇順に並んでいる
１番のジャガーは王様で問題文中にかかれている様に移動する事ができる
初期の状態から入力で与えられる状態にしたい
最小何手で変更できるか?

解法：
IDA*で解いた
ヒューリスティック関数として
予め全点間の最短距離をFWで求めておいた
ほとんど15-puzzleと同じ
ヒューリスティック関数の計算のやり方がマンハッタン距離から最短距離に変わっただけ

ただ、15-puzzleの様に状態を無理やりunsigned long longに変換してmapで管理する必要はない
15-puzzleの場合は有効だったが今回は有効ではないようだった(0.9秒くらい遅くなる、ただAcceptはできる)

コード；

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<cstdio>
#include<cassert>
#include<climits>

#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 41

using namespace std;

typedef unsigned long long ull;
/*
struct Info
{
  ull array[4];
  Info()
  {
    rep(i,4)array[i] = 0;
  }

  bool operator < (const Info& a)const
  {
    if(array[0] != a.array[0])return array[0] < a.array[0];
    if(array[1] != a.array[1])return array[1] < a.array[1];
    if(array[2] != a.array[2])return array[2] < a.array[2];
    return array[3] < a.array[3];
  }

};
*/
int N,troops[MAX],goal[MAX],gp[MAX],limit,nlimit;
int COST[MAX][MAX];
int dx[4][4] = 
  {
    {-3,-1,+4,-4},
    {+1,+3,+4,-4},
    {+1,-1,+4,-4},
    {+1,-1,+4,-4}
  };
//map<Info,int> mincost;

bool isValid(int x)
{
  return ( 0 <= x && x < N );
}

void makeCOST()
{
  rep(i,MAX)rep(j,MAX)COST[i][j] = ( (i == j) ? 0 : IINF );

  rep(y,MAX)
    {
      int x = y;
      rep(i,4)
	{
	  int nx = x + dx[(x+1)%4][i];
	  if(!isValid(nx))continue;
	  COST[y][nx] = 1;
	}
    }
 
  rep(k,MAX)rep(i,MAX)rep(j,MAX)
    {
      if(COST[i][k] == IINF || COST[k][j] == IINF)continue;
      COST[i][j] = min(COST[i][j],
		       COST[i][k]+COST[k][j]);
    }

}

int heuristic()
{
  int res = 0;
  rep(i,N)
    {
      if(troops[i])
	{
	  int x = gp[troops[i]];
	  res += COST[i][x];
	}
    }
  return res;
}

int heuristic2(int cur,int next)
{
  int x = gp[troops[next]];
  return - COST[next][x] + COST[cur][x];
}

bool finish()
{
  rep(i,N)if(troops[i] != goal[i])return false;
  return true;
}

bool DFS(int g,int h,int king,int pre)
{
  if( g+h > limit )
    {
      nlimit = min(g+h,nlimit);
      return false;
    }

  if(finish())
    {
      return true;
    }
  /*
  Info info;
  rep(i,N)
    {
      info.array[i/10] <<= 6;
      info.array[i/10] += troops[i];
    }
  if(mincost.count(info) && mincost[info] <= g)return false;
  mincost[info] = g;
  */
  rep(i,4)
    {

      if(pre != IINF && pre + dx[(king+1)%4][i] == 0)continue;

      int nx = king + dx[(king+1)%4][i];

      if(!( 0 <= nx && nx < N ))continue;

      int cost = heuristic2(king,nx);

      swap(troops[king],troops[nx]);

      if(DFS(g+1,h+cost,nx,dx[(king+1)%4][i]))
	{
	  return true;
	}
      swap(troops[king],troops[nx]);

    }

  return false;

}

int IDAstar()
{
  limit = heuristic();
  while(true)
    {
      //mincost.clear();
      nlimit = IINF;

      if(DFS(0,heuristic(),0,IINF))
	{
	  return limit;
	}

      if(nlimit == IINF)return -1;

      limit = nlimit;

    }
  return -1;
}

int main()
{
  N = MAX;
  makeCOST();


  int CNT = 1;
  while(scanf("%d",&N),N)
    {
      rep(i,N)
	{
	  scanf("%d",&goal[i]);
	  goal[i]--;
	  gp[goal[i]] = i;
	  troops[i] = i;
	}

      printf("Set %d:",CNT++); puts("");
      int ans = IDAstar();

      if(ans == -1)cout << "No solution" << endl;
      else cout << ans << endl;

    }
  return 0;
}