AtCoder ARC #044 : C - ビーム

ちょっと苦戦したけど何とか解けた。
http://arc044.contest.atcoder.jp/tasks/arc044_c

問題

H*Wのグリッドがある。
途中時刻T[i]に縦１列または横１行分のサイズのビームがグリッドを貫く時がある(同時刻に複数ビームが貫く場合もある)

プレイヤーは任意のセルで開始し、任意のタイミングで任意の回数隣接セルを辿って移動できる。
ビームに貫かれないような最小移動マス数を求めよ。

解法

この問題は縦ビームを横に避ける場合と、横ビームを縦に避ける場合は別々に扱える。
よってそれぞれの方向における最小移動マス数の和を取ればよい。

以下では縦ビームを横に避けるケースを考える。
ある時点までに置いて、各X座標にいる場合の最小移動回数をDP[x]とする。

ある時刻に何本か縦ビームが貫く時、プレイヤーはその座標にいられない。
よってビームの来るX座標にいるプレイヤーは右か左に避けるしかない。
そこでDPの要領で左右に動かそう。

ビームが複数来る場合、連続して数マス避ける可能性があるので、ビームの座標を左から順に処理して右に避けるケースを処理し、次に逆に右から判定して左に避けるケースを処理すればよい。
ビームが貫いた後は、そのX座標の最小移動回数DP[x]は無限と見なす。

int S[2],Q;
vector<int> E[2][101010];
int dp[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S[0]>>S[1]>>Q;
	FOR(i,Q) {
		cin>>j>>x>>y;
		E[x][j].push_back(y-1);
	}
	
	ll tot=0;
	FOR(j,2) {
		ZERO(dp);
		
		FOR(i,100100) if(E[j][i].size()) {
			sort(ALL(E[j][i]));
			if(E[j][i].size()==S[j]) return _P("-1\n");
			
			FORR(x,E[j][i]) {
				if(x) dp[x-1]=min(dp[x-1],dp[x]+1);
				if(x<S[j]-1) dp[x+1]=min(dp[x+1],dp[x]+1);
			}
			reverse(ALL(E[j][i]));
			FORR(x,E[j][i]) {
				if(x) dp[x-1]=min(dp[x-1],dp[x]+1);
				if(x<S[j]-1) dp[x+1]=min(dp[x+1],dp[x]+1);
			}
			FORR(r,E[j][i]) dp[r]=1<<30;
		}
		
		tot+=*min_element(dp,dp+S[j]);
	}
	
	cout<<tot<<endl;
}

まとめ

結構迷ったけど面白い問題でした。