土下座しながら探索中

主に競技プログラミング

AOJ 2447 : A Two Floors Dungeon

AOJ

問題リンク : A Two Floors Dungeon | Aizu Online Judge

問題概要：
H*Wのグリッドが与えられる
自分は上下左右に移動することができる
もし今いる場所が階段なら階段を利用して階を移動することもできる
スイッチがあるマスにいるならばスイッチを押すことができる
これらの行動を１つ行うのに１ステップかかる
スタートからゴールまで移動するのにかかる最小のステップ数を答えよ

グリッドには以下のものが存在する

# : 壁　壁に移動することはできない

: 階段　１階から2階へ、2階から１階へ移動することができる

_ : １階の床
^ : ２階の床
a to j : １階にあるスイッチ
A to J : ２階にあるスイッチ
% : スタート地点
& : ゴール地点

スイッチを押すことでスイッチが影響を与えるマス全ての階が変化する（1階にあった床は２階に、2階にあった床は1階に移動する　そのマスはスイッチなどを含むこともある）

スイッチの情報は a から順番に与えられる
グリッドのまわりはすべて壁で囲まれている

解法：
bfsで探索
mincost[1階か2階か][どのスイッチを押したかをビットで][y][x] := この状態で(x,y)にくる最小ステップ数

スイッチはたかだか１０個しかないのでそれら全ての状態をビットで表現する

今のグリッドの状態がどうなっているのかはこれまでに使ったスイッチの状態からわかる

vector swt[y][x] := (x,y) に影響を与えるスイッチの番号

というvectorを用意して、次に移動するマスを(nx,ny)とすると、swt[ny][nx] の中にある番号のなかでこれまでに使用したスイッチの番号の数を数えそれが奇数なら今いる場所は本来のそのマスの状態とは違う階になっているという感じで移動先だけ復元した

コード：

typedef pair<int,int> ii;

struct P
{
  int x,y,state,cost;
  bool floor;
  P(int x=inf,int y=inf,int state=inf,int cost=inf,bool floor=false):x(x),y(y),state(state),cost(cost),floor(floor){}
  bool operator < (const P& a)const
  {
    return cost > a.cost;
  }
};

int W,H,S;
char G[MAX][MAX];//初期状態のグリッド
vector<int> swt[MAX][MAX];//swt[y][x] := (x,y)に影響を与えるスイッチ
int mincost[2][(1<<10)][MAX][MAX];
ii st;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

bool getFloor(char c)//false -> 1, true -> 2
{
  if(c == '_' || c == '&' || c == '%' || (isalpha(c) && islower(c)))return false;
  if(c == '^' || (isalpha(c) && isupper(c)))return true;

  return true;//stair
}

void compute()
{
  priority_queue<P> Q;
  Q.push(P(st.X,st.Y,0,0,0));//int x | int y | int state | int cost | bool floor
  mincost[0][0][st.Y][st.X] = 0;

  while(!Q.empty())
    {
      P p = Q.top(); Q.pop();

      int x = p.x, y = p.y, state = p.state, cost = p.cost;
      bool floor = p.floor;

      if(G[y][x] == '&')
	{
	  cout << p.cost << endl;
	  return;
	}

      rep(i,4)
	{
	  int nx = x + dx[i];
	  int ny = y + dy[i];
	  if(!( 0 <= nx && nx < W && 0 <= ny && ny < H))continue;
	  if(G[ny][nx] == '#')continue;

	  char nc = G[ny][nx];
	  bool nfloor = getFloor(nc);
	  int cnt = 0;

	  rep(j,swt[ny][nx].size())
	    if((state>>swt[ny][nx][j]) & 1)cnt++;

	  if(cnt%2)nfloor = !nfloor;
	  
	  if(nc == '|')//stair
	    {
	      //same floor
	      if(mincost[floor][state][ny][nx] > cost + 1)
		{
		  mincost[floor][state][ny][nx] = cost + 1;	      
		  Q.push(P(nx,ny,state,cost+1,floor));
		}

	      //move down
	      if(mincost[!floor][state][ny][nx] > cost + 2)
		{	      
		  mincost[!floor][state][ny][nx] = cost + 2;
		  Q.push(P(nx,ny,state,cost+2,!floor));
		}

	      continue;
	    }

	  if(floor != nfloor)continue;
	  
	  if(isalpha(nc))//switch
	    {
	      
	      //dont use
	      if(mincost[floor][state][ny][nx] > cost + 1)
		{
		  mincost[floor][state][ny][nx] = cost + 1;
		  Q.push(P(nx,ny,state,cost+1,floor));
		}
	      
	      //use that
	      nc = tolower(nc);
	      int index = nc - 'a';
	      int nstate = state ^ (1<<index);
	      rep(j,swt[ny][nx].size())
		if(index == swt[ny][nx][j])
		  {
		    nfloor = !nfloor;
		    break;
		  }

	      if(mincost[nfloor][nstate][ny][nx] > cost + 2)
		{
		  mincost[nfloor][nstate][ny][nx] = cost + 2;
		  Q.push(P(nx,ny,nstate,cost+2,nfloor));
		}

	      continue;
	    }
	  
	  	    
	  //other
	  if(mincost[floor][state][ny][nx] > cost + 1)
	    {
	      mincost[floor][state][ny][nx] = cost + 1;
	      Q.push(P(nx,ny,state,cost+1,floor));
	    }
	  
	}

    }

  cout << -1 << endl;

}

void init()
{
  rep(i,H)rep(j,W)swt[i][j].clear();
  rep(l,2)rep(i,(1<<10))rep(j,H)rep(k,W)mincost[l][i][j][k] = inf;
}

int main()
{

  while(cin >> W >> H)
    { 
      init();
      rep(i,H)rep(j,W)
	{
	  cin >> G[i][j];
	  if(G[i][j] == '%')st = ii(j,i);
	}

      cin >> S;
      rep(s,S)
	{
	  char c;
	  rep(y,H)rep(x,W)
	    {
	      cin >> c;
	      if(c == '*')swt[y][x].push_back(s);
	    }
	}
	
      compute();

    }
  return 0;
}