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

土下座しながら探索中

主に競技プログラミング

AOJ 2447 : A Two Floors Dungeon

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

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

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

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

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

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

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

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

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

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

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

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