AOJ 2342 Light Road

問題

hxwのグリッドで表される部屋がある。
Sのマスから下向きにレーザーが出る。
このレーザーを、部屋の適切なマスに鏡を置くことでGのマスに誘導したい。


鏡は'.'のマスにのみ置くことができる。
レーザーは'#'のマスは通ることができないが、Sのマスを通ることはできる。

鏡は二種類あり/と\がn枚ずつある。それぞれ裏表どちらでもレーザーを反射することができる。
レーザーをゴールへ誘導することができるとき、鏡を置く最小の枚数を求めよ。
できないとき-1を返せ。

制約条件

h, w≦100

方針

現在の位置, 方向, /の枚数, \の枚数、を状態として、
鏡を置いた合計枚数をコストとしてダイクストラ


光線は鏡を貫通することはできないが、
基本的に同じ状態を2度通る必要はないので、それは考慮しなくていい。


ただし、例外があって、それは、光線がSを縦に通過しない場合。
光線が縦にSを通過するには、どうやっても鏡を貫通しなくてはいけないので、
その場合だけを取り除く。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int m[4][4];

int h, w, n;
char in[100][101];
bool v[100][100][4][11][11];

int main(){
	m[0][3] = m[1][2] = m[3][0] = m[2][1] = 1;
	
	cin >> h >> w >> n;
	int y, x;
	rep(i, h){
		cin >> in[i];
		rep(j, w) if(in[i][j] == 'S') y = i, x = j;
	}
	priority_queue<pair<int, pi> > Q;
	Q.push(mp(0, mp(2 * h * w + y * w + x, n * 11 + n)));
	
	while(!Q.empty()){
		int co = -Q.top().first;
		int cd = Q.top().second.first / h / w;
		y = Q.top().second.first / w % h; x = Q.top().second.first % w;
		int p = Q.top().second.second / 11, q = Q.top().second.second % 11;
		Q.pop();
		
		if(v[y][x][cd][p][q]) continue;
		v[y][x][cd][p][q] = 1;
		
		//cerr<<y<<" "<<x<<" "<<cd<<" "<<p<<" "<<q<<" "<<co<<endl;
		
		if(in[y][x] == 'G'){
			cout << co << endl;
			return 0;
		}
		rep(d, 4) if(d != (cd ^ 2)){
			if(in[y][x] == 'S' && cd != d) continue;
			if(in[y][x] == 'S' && co && dy[d]) continue;
			
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || ny >= h || nx < 0 || nx >= w || in[ny][nx] == '#') continue;
			int np = p - 1 + m[cd][d], nq = q - m[cd][d], nc = co;
			
			if(d == cd) np = p, nq = q;
			else nc++;
			if(np < 0 || nq < 0) continue;
			
			if(!v[ny][nx][d][np][nq]) Q.push(mp(-nc, mp(d * h * w + ny * w + nx, np * 11 + nq)));
		}
	}
	cout << -1 << endl;
	
	return 0;
}