TopCoder SRM 576 Div1 Easy ArcadeManao

今回から、Div2のEasyとMediumは省略することにします。
Mediumは大抵Div1Easyと大差ないし、Div2Easyは早解きの練習としては良いけどわざわざここに書くほどでもないかな…と。

なので今後はDiv1Easy・MediumとDiv2Hardを中心にやっていきます。
ここに書かないだけで練習にD2Eも解きはするけどね。

ではSRM576。今回は不参加だけど、出てたらEasyしか解けなかったな。
http://community.topcoder.com/stat?c=problem_statement&pm=12504

問題

マス目状に地形が与えられる。
一部のマスには床がある。横方向に隣接するマスに床がある場合、互いに移動可能である。
ここで、高さLのはしごがある場合、最大Lマス以内の縦方向の床があるマスを移動できる。

目的の位置が与えられたとき、そこに達するのに必要な最短のはしごの長さを答える。

解法

Lを1から順次増やして、到達可能か試せばよい。
現在移動可能な床に、BFSで横方向および高さL以内の床を追加していくだけ。

class ArcadeManao {
	vector<string> L;
	int X,Y,W,H;
	public:
	
	int ok(int LH) {
		int vis[51][51];
		queue<pair<int,int> > Q;
		
		ZERO(vis);
		Q.push(make_pair(0,H-1));
		vis[H-1][0]=1;
		while(!Q.empty()) {
			pair<int,int> p=Q.front();
			Q.pop();
			
			int cx=p.first;
			int cy=p.second;
			
			if(cx>0 && L[cy][cx-1]=='X' && vis[cy][cx-1]==0) {
				vis[cy][cx-1]=1;
				Q.push(make_pair(cx-1,cy));
			}
			if(cx<W-1 && L[cy][cx+1]=='X' && vis[cy][cx+1]==0) {
				vis[cy][cx+1]=1;
				Q.push(make_pair(cx+1,cy));
			}
			
			for(int ty=cy-LH;ty<=cy+LH;ty++) {
				if(ty<0 || ty>=H) continue;
				if(L[ty][cx]=='X' && vis[ty][cx]==0) {
					vis[ty][cx]=1;
					Q.push(make_pair(cx,ty));
				}
			}
		}
		
		return vis[Y][X];
	}
	
	
	int shortestLadder(vector <string> level, int coinRow, int coinColumn) {
		int i;
		L=level;
		H=L.size();
		W=L[0].size();
		X=coinColumn-1;
		Y=coinRow-1;
		
		FOR(i,100) if(ok(i)) return i;
		return 100;
	}

};

まとめ

実装ゲーかな。割と解法は自明な気も。
意外と平均スコアは低めなのはコード量が増えるから？