SRM 646 DIV2 Middle - TheGridDivTwo

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13628&rd=16278

・2次元の座標が与えられる。
・(0,0)がスタート地点になり、各ターン上下左右のいずれかに移動することができる。
・ただし複数の障害物が与えられ、障害物がある方向には移動することができない。
・Kターン移動するとき、最後に移動することができる最大のx座標の値を求める。

解き方


問題文を見るとk=1000なので前探索できそう。

ただしマイナスの方向にも移動するので、座標変換が必要。
今回は最小で−1000なので、x,y座標ともに1000を足してあげて、最後の答えから1000を引けば良い。

コード


int dp[2010][2010];

class TheGridDivTwo {

public: int find(vector<int> x, vector<int> y, int k) {
queue<pair<int,int> > q;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

memset(dp,0,sizeof(dp));
FORE(i,0,x.size())dp[x[i]+1000][y[i]+1000]=-1;
dp[1000][1000]=1;
q.push(make_pair(1000,1000));

while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
if(dp[x][y]==k+1)break;
q.pop();
FORE(i,0,4){
int cx=x+dx[i];
int cy=y+dy[i];
if(dp[cx][cy]==0){
dp[cx][cy]=dp[x][y]+1;
q.push(make_pair(cx,cy));
}
}
}

int ret=-3000;
FORE(i,0,2010)FORE(j,0,2010)if(dp[i][j]>0)ret=max(ret,i);

return ret-1000;
}

};
このエントリーをはてなブックマークに追加