問題
http://community.topcoder.com/stat?c=problem_statement&pm=10804&rd=14185
N個の次元があり、最初はすべての次元について位置０からスタートする。
各ステップについて、どの次元の座標を＋ーするか与えられる。
このとき、ステップ中にすでに通った道に戻るときはInvalidを、
そうでないときはvalidを返す。
解き方
Nが大きく配列に保存できないため、必要な配列だけを保存する。
同じ場所にもどってくるかどうかは、ある地点を基準にして
各エリアの＋ーがすべて０になったときとなる。
上記ついてすべての地点で判定してあげれば良い。
コード
class RouteIntersection {
public: string isValid(int N, vector<int> coords, string moves) {
int len=coords.size();
FORE(i,0,len){
map<int,int> m;
FORE(j,i,len){
if(moves[j]=='+')m[coords[j]]++;
else m[coords[j]]--;
int invalid=1;
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
if(it->second!=0)invalid=0;
}
if(invalid)return "NOT VALID";
}
}
return "VALID";
}
};
public: string isValid(int N, vector<int> coords, string moves) {
int len=coords.size();
FORE(i,0,len){
map<int,int> m;
FORE(j,i,len){
if(moves[j]=='+')m[coords[j]]++;
else m[coords[j]]--;
int invalid=1;
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
if(it->second!=0)invalid=0;
}
if(invalid)return "NOT VALID";
}
}
return "VALID";
}
};