SRM 376 DIV1 Easy - Trainyard

SRM 376 DIV1 Easy - Trainyard

6:18

問題


http://community.topcoder.com/stat?c=problem_statement&pm=6555&rd=10796

解き方


実装問題。システムテストで落ちやすい問題なので、すべて条件文をもれなく書かないといけない。

コード


class Trainyard {

public: int reachableSquares(vector<string> layout, int fuel) {
int h=layout.size(),w=layout[0].size();
int dr[]={1,0,-1,0},dc[]={0,1,0,-1};
int dp[4][10][10];
FORE(i,0,4)FORE(j,0,10)FORE(k,0,10)dp[i][j][k]=-1;

queue<pair<int,pair<int,int> > > q;
FORE(i,0,h)FORE(j,0,w)if(layout[i][j]=='S'){
FORE(k,0,4){
dp[k][i][j]=fuel;
q.push(make_pair(k,make_pair(i,j)));
}
}

while(!q.empty()){
int r=q.front().second.first;
int c=q.front().second.second;
int d=q.front().first;
int cost=dp[d][r][c];
q.pop();

FORE(i,0,4){
if(layout[r][c]=='|' && (i==1 || i==3))continue;
if(layout[r][c]=='-' && (i==0 || i==2))continue;

int nr=r+dr[i],nc=c+dc[i];
if(0<=nr && nr<h && 0<=nc && nc<w && layout[nr][nc]!='.'){
if(layout[nr][nc]!='+'){
if((abs(d-i)%2)!=0 && abs(d-i)==2)continue;
if((i==0 || i==2) && layout[nr][nc]!='|' )continue;
if((i==1 || i==3) && layout[nr][nc]!='-' )continue;
}

if(cost-1>dp[i][nr][nc]){
dp[i][nr][nc]=cost-1;
q.push(make_pair(i,make_pair(nr,nc)));
}
}
}
}

int ret=0;
FORE(i,0,10)FORE(j,0,10){
int valid=0;
FORE(k,0,4)if(dp[k][i][j]>=0)valid=1;
ret+=valid;
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts