問題
http://community.topcoder.com/stat?c=problem_statement&pm=10451&rd=14174
迷路とプレイヤーが１ターンで移動できる方向のマスが与えられる。
このとき、プレイヤーがゴールできない位置、もしくはゴールできるときは
一番遠い位置にゴールを置きたい。
ゴールできない位置におけるときはー１を、そうでないときは
もっとも遠いターン数を求める。
解き方
幅優先探索で全探索すればよい。
幅優先探索なのでセルの値の更新は一度だけでよい。
コード
class MazeMaker {
public: int longestPath(vector<string> maze, int startRow, int startCol, vector<int> moveRow, vector<int> moveCol) {
int h=maze.size(),w=maze[0].size(),n=moveRow.size();
int used[h][w];
memset(used,-1,sizeof(used));
queue<pair<int,int> > q;
q.push(make_pair(startRow,startCol));
used[startRow][startCol]=0;
while(!q.empty()){
int r=q.front().first;
int c=q.front().second;
int turn=used[r][c];
q.pop();
FORE(i,0,n){
int nr=r+moveRow[i],nc=c+moveCol[i];
if(0<=nr && nr<h && 0<=nc && nc<w && maze[nr][nc]!='X' && used[nr][nc]==-1){
q.push(make_pair(nr,nc));
used[nr][nc]=turn+1;
}
}
}
int ret=0;
FORE(i,0,h)FORE(j,0,w)if(maze[i][j]=='.'){
if(used[i][j]==-1)return -1;
ret=max(ret,used[i][j]);
}
return ret;
}
};
public: int longestPath(vector<string> maze, int startRow, int startCol, vector<int> moveRow, vector<int> moveCol) {
int h=maze.size(),w=maze[0].size(),n=moveRow.size();
int used[h][w];
memset(used,-1,sizeof(used));
queue<pair<int,int> > q;
q.push(make_pair(startRow,startCol));
used[startRow][startCol]=0;
while(!q.empty()){
int r=q.front().first;
int c=q.front().second;
int turn=used[r][c];
q.pop();
FORE(i,0,n){
int nr=r+moveRow[i],nc=c+moveCol[i];
if(0<=nr && nr<h && 0<=nc && nc<w && maze[nr][nc]!='X' && used[nr][nc]==-1){
q.push(make_pair(nr,nc));
used[nr][nc]=turn+1;
}
}
}
int ret=0;
FORE(i,0,h)FORE(j,0,w)if(maze[i][j]=='.'){
if(used[i][j]==-1)return -1;
ret=max(ret,used[i][j]);
}
return ret;
}
};