TopCoder SRM 637 Div2 Medium PathGameDiv2

ここはまだ簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13506

問題

縦２行横何列かのグリッドがある。
各セルは白マスか黒マスのいずれかであり、黒マスは移動できない。

初期状態では、左端の上下いずれかのセルから、右端の上下いずれかのセルに隣接する白マスをたどって移動可能なことが保証されている。
ここでいくつかの白マスをさらに黒マスにしても、左端から右端に移動可能なようにしたい。
最大何マスを黒マスにできるか。

解法

左端から右端に至る最短ルートを求めれば、それ以外を黒マスにしてしまってよい。

まず最初に上下どちらを選ぶかだが、一番上下列で最左の黒マスが遠い方を選べばよい。
あとは黒マスに到達するまで右に移動し、黒マスにぶつかりそうなら上下移動で行を変えていく。

class PathGameDiv2 {
	public:
	int calc(vector <string> board) {
		int W=board[0].size();
		int x1,x2,x,c;
		FOR(x1,W) if(board[0][x1]=='#') break;
		FOR(x2,W) if(board[1][x2]=='#') break;
		
		c=x1<x2;
		FOR(x,W) {
			board[c][x]='X';
			if(x<W-1 && board[c][x+1]=='#') board[c^=1][x]='X';
		}
		return count(board[0].begin(),board[0].end(),'.') + count(board[1].begin(),board[1].end(),'.');
		
	}
}

まとめ

ここらへんはすんなり。