SRM 237 DIV1 Hard MirrorPlacement

問題 Editorial

問題

H*Wのマップが与えられる。
マップはそれぞれ '.': 空白, '#': 壁, '/': "／"の形の鏡, '`': "＼"の形の鏡
マップの周囲は壁に囲われており、ちょうど2つだけ穴があいている。
一方の穴からもう一方の穴へ光を通したい。
光は壁に当たると吸収され、鏡に当たると直角に反射する。
鏡に裏表はなく、どちらからでも反射する。
鏡を空白のマスにいくつか置ける。
一方の穴からもう一方の穴へ光を通すとき、置く鏡の数を最小化せよ。
ただしどうやっても光を通せない場合は-1を返せ

解答

まず、鏡を置いたマスを2回以上通ることは最適ではない。
なぜなら、2回が直角の角度で来る場合は鏡の角度を変えればショートカットでき、水平の場合はループしてるか最初の穴に戻るだけだからである。
なので、単に鏡の置いた枚数を距離としたBFSをすれば良い

コメント

Example6のケースを考慮してなくて、Exampleに救われた。これは駄目だね。もしExampleになかったら！
その後も遅すぎて駄目だ。もしバグったりミスしたら、どうすればいいか一回"本当に"冷静に考えよう！

コード

#include <string>
#include <vector>
#include <queue>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;

struct MirrorPlacement {
	int mirrors(vector <string> a) {
		int h = a.size(), w = a[0].size();
		vpii holes;
		reu(i, 1, h-1) {
			if(a[i][0]=='.') holes.pb(mp(i, 0));
			if(a[i][w-1]=='.') holes.pb(mp(i, w-1));
		}
		reu(j, 1, w-1) {
			if(a[0][j]=='.') holes.pb(mp(0, j));
			if(a[h-1][j]=='.') holes.pb(mp(h-1, j));
		}
		static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
		deque<pair<int,pair<pii,int> > > q;
		{
			pii p = holes[0];
			int d = p.second==0 ? 0 : p.second==w-1 ? 2 : p.first==0 ? 1 : 3;
			q.pb(mp(0, mp(p, d)));
		}
		static int dist[4][55][55];
		mset(dist, INF);
		while(!q.empty()) {
			pair<pii,int> st = q.back().second;
			int ww = q.back().first, d = st.second, y = st.first.first, x = st.first.second;
			q.pop_back();
			if(dist[d][y+1][x+1] <= ww) continue;
			dist[d][y+1][x+1] = ww;
			#define BOUND(y,x) (0<=(y)&&(y)<h&&0<=(x)&&(x)<w)
			#define OK(y,x) (BOUND(y,x)&&a[y][x]!='#')
			if(st.first == holes[1] && !BOUND(y+dy[d], x+dx[d])) return ww;
			if(!BOUND(y+dy[d], x+dx[d])) continue;
			static const int mirror1[4] = {3,2,1,0}, mirror2[4] = {1,0,3,2};
			int nd = d;
			if(a[y][x] == '/') nd = mirror1[d];
			else if(a[y][x] == '`') nd = mirror2[d];
			if(OK(y + dy[nd], x + dx[nd])) q.push_back(mp(ww, mp(mp(y + dy[nd], x + dx[nd]), nd)));
			if(a[y][x] == '.') rep(mirror, 2) {
				nd = (mirror==0 ? mirror1 : mirror2)[d];
				q.push_front(mp(ww + 1, mp(mp(y, x), nd)));
			}
		}
		return -1;
	}
};