kojingharangの日記

Facebook Hacker Cup 2015 Qualification C. Laser Maze

15:44 |

• 2次元グリッドに岩と東西南北どれかを向いているレーザー砲とプレイヤーとゴールがある。
• プレイヤーは１ステップで東西南北のうちレーザー砲や壁がない方向に進める。レーザ砲はプレイヤーが動いた直後に時計回りに90度回転して砲撃する。レーザーはレーザー砲や壁は通過しない。プレイヤーはレーザーに当たると死ぬ。
• プレイヤーはゴールに着いてしばらく生きていたい。ゴールまで最小何ステップで行けるか。
• 1≦H, W≦100, 1≦TestCases≦100

• レーザー砲の向き全部の組み合わせはステップ数%4の 4 通りしかないので、プレイヤーの状態 (位置(x, y), ステップ数%4) をノードとみなして単一始点最短路問題に帰着させる。

• Accepted

// struct Dijkstra は略
ll H, W;
vector<string> m;
vector<int> lx, ly, ldir;
int inMap(int x, int y) {
	return 0<=x && x<W && 0<=y && y<H;
}
int isFence(int x, int y) {
	char c=m[y][x];
	return c=='<' || c=='>' || c=='^' || c=='v' || c=='#';
}
int dx[] = {0,1,0,-1}; // up right down left
int dy[] = {-1,0,1,0}; // up right down left
int alive(int x, int y, int phase) {
	REP(li, lx.size()) {
		int clx=lx[li];
		int cly=ly[li];
		int cldir=(ldir[li]+phase)%4;
		while(1) {
			if(clx==x && cly==y) return 0; //shoot
			clx+=dx[cldir];
			cly+=dy[cldir];
			if(!inMap(clx, cly)) break;
			if(isFence(clx, cly)) break;
		}
	}
	return 1;
}

int canMove(int x, int y, int phase, int dir) {
	int nx = x+dx[dir];
	int ny = y+dy[dir];
	if(!inMap(nx, ny)) return 0;
	if(isFence(x, y)) return 0;
	if(isFence(nx, ny)) return 0;
	if(!alive(nx, ny, (phase+1)%4)) return 0;
	return 1;
}

ll node(int x, int y, int phase) {
	assert(0<=x && x<W && 0<=y && y<H && 0<=phase && phase<4);
	return phase*H*W + x*H + y;
}

int main() {
	//ios::sync_with_stdio(false);
	int Cases;
	cin>>Cases;
	REP(CaseID, Cases) {
		cin>>H>>W;
		m = vector<string>(H);
		REP(y, H) cin>>m[y];
		ll start;
		vector<ll> goals;
		lx.clear();
		ly.clear();
		ldir.clear();
		REP(y, H) REP(x, W) {
			if(m[y][x]=='S') start = node(x, y, 0);
			if(m[y][x]=='G') {
				REP(p, 4) goals.PB(node(x, y, p));
			}
			if(m[y][x]=='^') {
				lx.PB(x); ly.PB(y); ldir.PB(0);
			}
			if(m[y][x]=='>') {
				lx.PB(x); ly.PB(y); ldir.PB(1);
			}
			if(m[y][x]=='v') {
				lx.PB(x); ly.PB(y); ldir.PB(2);
			}
			if(m[y][x]=='<') {
				lx.PB(x); ly.PB(y); ldir.PB(3);
			}
		}
//		cout<<m<<endl;
		Dijkstra d(W*H*4);
		REP(y, H) REP(x, W) REP(p, 4) REP(dir, 4) {
			if(canMove(x, y, p, dir)) {
				int nx = x+dx[dir];
				int ny = y+dy[dir];
			    d.add_edge(node(x, y, p), node(nx, ny, (p+1)%4), 1);
			}
		}
		d.run(start, -1);
		ll ans = 1LL<<60;
		REP(ni, W*H*4) {
			REP(gi, 4) if(d.V[goals[gi]] < (1<<30)) ans=min<ll>(ans, d.V[goals[gi]]);
		}
		if(ans==1LL<<60) {
			cout<<"Case #"<<CaseID+1<<": "<<"impossible"<<endl;
		} else {
			cout<<"Case #"<<CaseID+1<<": "<<ans<<endl;
		}
//		break;
	}
	
	return 0;
}

ツイートする