問題
http://community.topcoder.com/stat?c=problem_statement&pm=8223&rd=10789
解き方
解くだけ。1度一周して確かめるなど、うまく条件を整理するのがポイント。
コード
class RoadConstruction {
public: int getExitTime(vector<string> lanes) {
int n=lanes.size();
int ret=0;
int flag[n];
memset(flag,0,sizeof(flag));
int at=0,prev=-1;
while(1){
while(at<n && lanes[at].empty())at++;
if(at<n && flag[at]==0){
prev=at;
flag[at]=1;
at++;
}else{
if(at>=n)at=prev;
if(lanes[at][0]=='D')return ret;
ret++;
lanes[at]=lanes[at].substr(1);
flag[at]=0;
at=0,prev=-1;
}
}
return -1;
}
};
public: int getExitTime(vector<string> lanes) {
int n=lanes.size();
int ret=0;
int flag[n];
memset(flag,0,sizeof(flag));
int at=0,prev=-1;
while(1){
while(at<n && lanes[at].empty())at++;
if(at<n && flag[at]==0){
prev=at;
flag[at]=1;
at++;
}else{
if(at>=n)at=prev;
if(lanes[at][0]=='D')return ret;
ret++;
lanes[at]=lanes[at].substr(1);
flag[at]=0;
at=0,prev=-1;
}
}
return -1;
}
};