問題
http://community.topcoder.com/stat?c=problem_statement&pm=8262&rd=10787
解き方
最大ケースの時は5000*5000なのでメモリが足りない。
そのため、なにかしら工夫する必要がある。
今回width,lengthともに3以上のときはwidth-2,lengh-2かつスタート位置(r,c)を(r+1,c+1)に
したものと等しくなる。
最後にwidth<=2もしくはlength<=2となるのでこれは簡単な場合分けで解ける。
コード
class SpiralRoute {
public: vector<int> thronePosition(int width, int length) {
int r=0,c=0;
while(width>=3 && length>=3){
width-=2,length-=2;
r++,c++;
}
if(length==1)r+=width-1;
else if(length==2)c++;
else if(width==1)c+=length-1;
else c++;
vector<int> ans(2);
ans[0]=r,ans[1]=c;
return ans;
}
};
public: vector<int> thronePosition(int width, int length) {
int r=0,c=0;
while(width>=3 && length>=3){
width-=2,length-=2;
r++,c++;
}
if(length==1)r+=width-1;
else if(length==2)c++;
else if(width==1)c+=length-1;
else c++;
vector<int> ans(2);
ans[0]=r,ans[1]=c;
return ans;
}
};