問題
http://community.topcoder.com/stat?c=problem_statement&pm=12504&rd=15496
解き方
各はしごの数について昇順で調べることができる。
通常の経路探索に、はしごの長さを考慮すればよい。
コード
class ArcadeManao {
public:
int shortestLadder(vector<string> level, int coinRow, int coinColumn) {
int h=level.size(),w=level[0].size();
int used[h][w];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
for(int len=0;len<50;len++){
queue<pair<int,int> > q;
q.push(make_pair(h-1,0));
memset(used,0,sizeof(used));
used[h-1][0]=1;
while(!q.empty()){
int r=q.front().first,c=q.front().second;
q.pop();
FORE(i,0,4)for(int j=0;j<=len;j++){
int nr=r+dx[i]*j,nc=c+dy[i];
if(0<=nr && nr<h && 0<=nc && nc<w && !used[nr][nc] && level[nr][nc]=='X'){
used[nr][nc]=1;
q.push(make_pair(nr,nc));
}
}
}
if(used[coinRow-1][coinColumn-1])return len;
}
return 50;
}
};
public:
int shortestLadder(vector<string> level, int coinRow, int coinColumn) {
int h=level.size(),w=level[0].size();
int used[h][w];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
for(int len=0;len<50;len++){
queue<pair<int,int> > q;
q.push(make_pair(h-1,0));
memset(used,0,sizeof(used));
used[h-1][0]=1;
while(!q.empty()){
int r=q.front().first,c=q.front().second;
q.pop();
FORE(i,0,4)for(int j=0;j<=len;j++){
int nr=r+dx[i]*j,nc=c+dy[i];
if(0<=nr && nr<h && 0<=nc && nc<w && !used[nr][nc] && level[nr][nc]=='X'){
used[nr][nc]=1;
q.push(make_pair(nr,nc));
}
}
}
if(used[coinRow-1][coinColumn-1])return len;
}
return 50;
}
};