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