TopCoderOpen 2020 Round3B : Easy VisitALot

Easy/Mediumをあっさり解けたので本番出ておけばよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=16349&rd=18145

問題

R*Cのグリッドのうち、最大3マス移動不可なマスがある。
なお、これらのマスは外周のマスにはない。
左上マスから隣接マスをたどり、同じマスを複数回通らないようにして全マスの半分以上を通過したい。
そのようなパスを1つ構成せよ。

解法

R,Cのいずれか4以下なら、外周を回るだけでok。
そうでない場合、移動不可マスのない列と移動不可マスのない行のどちらかだけで半数のマスを確保できる。
よって、それらの列または行を通るようジグザグに走行しよう。

class VisitALot {
	public:
	string travel(int R, int C, vector <int> obsr, vector <int> obsc) {
		int L=2*(R-1+C-1);
		string S;
		if(L*2>=R*C) {
			int i;
			FOR(i,C-1) S+="E";
			FOR(i,R-1) S+="S";
			FOR(i,C-1) S+="W";
			FOR(i,R-2) S+="N";
			return S;
			
		}
		int NC[51]={};
		int NR[51]={};
		FORR(r,obsr) NR[r]++;
		FORR(c,obsc) NC[c]++;
		// LR
		int x,y;
		L=R;
		FOR(y,R) if(NR[y]==0) L+=C-1;
		if(L*2>=R*C) {
			int side=0;
			FOR(y,R) {
				if(NR[y]==0) {
					FOR(x,C-1) S+="EW"[side];
					side^=1;
				}
				if(y==R-1) break;
				S+="S";
			}
			return S;
		}
		L=C;
		FOR(x,C) if(NC[x]==0) L+=R-1;
		if(L*2>=R*C) {
			int side=0;
			FOR(x,C) {
				if(NC[x]==0) {
					FOR(y,R-1) S+="SN"[side];
					side^=1;
				}
				if(x==C-1) break;
				S+="E";
			}
			return S;
		}
		return "";
		
		
		
	}
}

まとめ

そこまで複雑ではない気もするけど、本番割と落ちてる。