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

土下座しながら探索中

主に競技プログラミング

AOJ 0247 : Ice Maze

問題リンク : Ice Maze | Aizu Online Judge

問題概要:
日本語なので略

解法:
反復深化で解いた

氷の塊の情報をvectorで管理した
入力をとった後に氷の塊に番号を付けていき、氷の塊の分だけvectorの要素を確保する
氷の塊の番号とvectorのインデックスが対応しており、その氷の塊を何回踏んだかを記録する
これと今の場所を組み合わせた情報をsetで管理し、同じ状態になったら枝刈りする

反復深化を始める前にあらかじめ全ての場所からゴールまでの単純な最短コストを求めておく
単純な最短コストは、氷の塊を何回踏んだかを考えないでその場所からゴールまでにかかる最短のコストのことを意味する
これを使って反復深化中に
 ・今のコスト + 今いる場所からゴールまでの最短コスト >= 最大の答え
となったら枝刈りし、

 ・今のコスト + 今いる場所からゴールまでの最短コスト >= 深さ
となったら要素をキューに戻し、その深さでの計算を終了する

などを行う
ここで、最大の答えとは与えられるグラフにでてくる'.'の数と'X'の数の和である
同じ場所を2度通ることは無駄でしかないので、最大でも'.'と'X'の数分しか動くことはないからである

そして反復深化をするのだが、
次の状態に遷移する際に、4方向すべて見るのではなく3方向だけにする
4方向のうち1つの方向は必ず前にいた場所に戻る方向が含まれているのでそれはあらかじめcontinueするようにした
setでfindする手間がはぶけるので結構速くなった
後はそんな感じで反復深化を行う

1つの深さが終わる毎にsetはclearすること!
これをしないとかなりメモリをくってしまいMLEをおこす(と思う、自分はそうだった)
結局setをclearしても深さで探索していくので最初のほうに訪れた場所に戻ることはない

コード:

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 12
#define sinf (30000)
#define cinf (254)

using namespace std;

typedef unsigned short us;
typedef unsigned char uc;

struct Pox
{
  vector<uc> array;
  us cost;
  us prev;
  Pox(vector<uc> array=vector<uc>(),us cost=cinf,us prev=cinf):array(array),cost(cost),prev(prev){}
};

uc dx[] = {1,0,-1,0};
uc dy[] = {0,-1,0,1};
uc max_ans;
uc ev[MAX*MAX][MAX*MAX];//評価値 ev[a][b] := aからbまでの最短コスト
char g[MAX][MAX];
us st[2],h,w,ice_number;
int ice[MAX*MAX];
uc ice_cnt[MAX*MAX];
set<vector<uc> > mincost;
deque<Pox> Q;

void init()
{
  max_ans = 0;
  ice_number = 0;
  rep(i,h)rep(j,w)
    {
      ice[j+i*w] = inf;
      ice_cnt[j+i*w] = cinf;
    }
}

void getInput()
{
  rep(i,h)
    {
      getchar();
      rep(j,w)
	{
	  scanf("%c",&g[i][j]);
	  if(g[i][j] == 'S')
	    {
	      st[0] = j + i * w;
	      g[i][j] = '.';
	    }
	  if(g[i][j] == 'G')
	    {
	      st[1] = j + i * w;
	      g[i][j] = '.';
	    }
	  if(g[i][j] == '.')max_ans++;
	}
    }
}

void make_ev()
{
  rep(sp,h*w)
    {
      ev[sp][sp] = 0;
      deque<us> deq;
      deq.push_back(sp);

      while(!deq.empty())
	{
	  uc cur = deq.front(); deq.pop_front();
	  if(cur == st[1])break;
	  rep(i,4)
	    {
	      uc nx = cur % w + dx[i];
	      uc ny = cur / w + dy[i];
	      if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
	      if(g[ny][nx] == '#')continue;
	      if(ev[sp][nx+ny*w] > ev[sp][cur]+1)
		{
		  ev[sp][nx+ny*w] = ev[sp][cur]+1;
		  deq.push_back(nx+ny*w);
		}
	    }
	}
    }
}

void draw(uc cur,uc id,int &cnt)
{
  if(ice[cur] != inf)return;
  ice[cur] = id;
  cnt++;
  rep(i,4)
    {
      uc nx = cur % w + dx[i];
      uc ny = cur / w + dy[i];
      if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
      if(g[ny][nx] != 'X')continue;
      draw(nx+ny*w,id,cnt);
    }
}

bool compute(us depth)
{
  while(!Q.empty())
    {
      Pox pox = Q.front(); Q.pop_front();
      
      if(st[1] == pox.array[ice_number])
	{
	  cout << pox.cost << endl;
	  return true;
	}

      if(pox.cost + ev[pox.array[ice_number]][st[1]] >= max_ans)
	{
	  continue;
	}
      
      if(pox.cost + ev[pox.array[ice_number]][st[1]] >= depth)
	{
	  Q.push_back(pox);
	  return false;
	}
      

      rep(i,4)
	{
	  if(pox.prev != -1 && pox.prev == (i+2)%4)continue;
	  uc nx = pox.array[ice_number] % w + dx[i];
	  uc ny = pox.array[ice_number] / w + dy[i];
	  if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
	  if(g[ny][nx] == '#')continue;

	  vector<uc> next = pox.array;	
	  next[ice_number] = nx+ny*w;  

	  if(g[ny][nx] == 'X')
	    {
	      if(ice_cnt[ice[nx+ny*w]] < 2*(pox.array[ice[nx+ny*w]] + 1))continue;

	      next[ice[nx+ny*w]]++;
	    }


	  if(mincost.find(next) == mincost.end())
	    {
	      mincost.insert(next);
	      if(Q.front().cost > pox.cost+1)
		Q.push_front(Pox(next,pox.cost+1,i));
	      else
		Q.push_back(Pox(next,pox.cost+1,i));
	    }
	}
    }
  return false;
}

int main()
{
  while(cin >> w >> h,w|h)
    {
      init();
      getInput();
      make_ev();

      rep(y,h)rep(x,w)
	if(g[y][x] == 'X' && ice[x+y*w] == inf)
	    {
	      int cnt = 0;
	      draw(x+y*w,ice_number,cnt);
	      ice_cnt[ice_number] = cnt;
	      ice_number++;      
	    }

      rep(i,ice_number)max_ans += ice_cnt[i]/2;

      vector<uc> initial_array(ice_number+1,0);
      initial_array[ice_number] = st[0];
      Q.push_back(Pox(initial_array,0,-1));
      mincost.insert(initial_array);
      us depth = 0;
      while(!compute(depth++))mincost.clear();

      while(!Q.empty())Q.pop_back();
      mincost.clear();
    }
  return 0;
}