SRM 447 DIV1 Easy - KnightsTour

SRM 447 DIV1 Easy - KnightsTour

16:33

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10577&rd=13901

解き方


問題文の条件をすべて洗い出すのが大事。
洗い出すことができれば、あとは正確に実装すればよい。

コード


int used[10][10];
int dr[]={1,1,2,2,-1,-1,-2,-2},dc[]={2,-2,1,-1,2,-2,1,-1};
int h,w;

class KnightsTour {

public:

int calc(vector<string> board,int r,int c){
int cnt=0;
FORE(i,0,8){
int nr=r+dr[i],nc=c+dc[i];
if(0<=nr && nr<h && 0<=nc && nc<w && used[nr][nc]==0 && board[nr][nc]!='*'){
cnt++;
}
}
return cnt;
}

int visitedPositions(vector<string> board) {
h=board.size(),w=board[0].size();

memset(used,0,sizeof(used));

queue<pair<int,int> > q;
FORE(i,0,h)FORE(j,0,w)if(board[i][j]=='K'){
q.push(make_pair(i,j));
used[i][j]=1;
}

int ret=0;
while(!q.empty()){
int r=q.front().first;
int c=q.front().second;
q.pop();
ret=max(ret,used[r][c]);

int nextr=1e+9,nextc=1e+9,cost=1e+9;
FORE(i,0,8){
int nr=r+dr[i],nc=c+dc[i];
if(0<=nr && nr<h && 0<=nc && nc<w && used[nr][nc]==0 && board[nr][nc]!='*'){
if(calc(board,nr,nc)<cost || (calc(board,nr,nc)==cost && nr<nextr) ||
(calc(board,nr,nc)==cost && nr==nextr && nc<nextc)){
cost=calc(board,nr,nc);
nextr=nr;
nextc=nc;
}
}
}
if(cost!=1e+9){
q.push(make_pair(nextr,nextc));
used[nextr][nextc]=used[r][c]+1;
}
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts