SRM 382 DIV1 Easy - CollectingRiders (復習×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8319&rd=10805
通常のチェスのナイトの動きを１度にＫ回まで動くことのできるＫ－ナイトをが存在し、
ボード上に配置されている。ボード上の数がＫにあたる。
このとき、すべてのボード上のナイトが同じセルに到達するまでに必要な最小移動回数の合計を求める。
そのようなセルが存在しない場合はー１を返す。
解き方
ボードが１０＊１０なので、全探索で解くことができる。
計算量はＯ（１００００）。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CollectingRiders {
public: int minimalMoves(vector<string> board) {
int w=board[0].size(),h=board.size();
int dx[]={2,2,1,1,-1,-1,-2,-2};
int dy[]={1,-1,2,-2,2,-2,1,-1};
int ret=10000;
FORE(x,0,h){
FORE(y,0,w){
int p[h][w];
FORE(i,0,h)FORE(j,0,w)p[i][j]=10000;
queue<pair<int,int> > q;
q.push(make_pair(x,y));
p[x][y]=0;
while(!q.empty()){
int tx=q.front().first,ty=q.front().second;
q.pop();
FORE(i,0,8){
int nx=tx+dx[i],ny=ty+dy[i];
if(0<=nx&&nx<h&&0<=ny&&ny<w&&p[nx][ny]==10000){
p[nx][ny]=p[tx][ty]+1;
q.push(make_pair(nx,ny));
}
}
}
int cnt=0;
FORE(i,0,h){
FORE(j,0,w){
if(board[i][j]!='.'){
if(p[i][j]==10000)cnt+=100000;
if(p[i][j]!=0)cnt+=(p[i][j]+board[i][j]-'0'-1)/(board[i][j]-'0');
}
}
}
ret=min(ret,cnt);
}
}
return ret==10000 ? -1 : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CollectingRiders {
public: int minimalMoves(vector<string> board) {
int w=board[0].size(),h=board.size();
int dx[]={2,2,1,1,-1,-1,-2,-2};
int dy[]={1,-1,2,-2,2,-2,1,-1};
int ret=10000;
FORE(x,0,h){
FORE(y,0,w){
int p[h][w];
FORE(i,0,h)FORE(j,0,w)p[i][j]=10000;
queue<pair<int,int> > q;
q.push(make_pair(x,y));
p[x][y]=0;
while(!q.empty()){
int tx=q.front().first,ty=q.front().second;
q.pop();
FORE(i,0,8){
int nx=tx+dx[i],ny=ty+dy[i];
if(0<=nx&&nx<h&&0<=ny&&ny<w&&p[nx][ny]==10000){
p[nx][ny]=p[tx][ty]+1;
q.push(make_pair(nx,ny));
}
}
}
int cnt=0;
FORE(i,0,h){
FORE(j,0,w){
if(board[i][j]!='.'){
if(p[i][j]==10000)cnt+=100000;
if(p[i][j]!=0)cnt+=(p[i][j]+board[i][j]-'0'-1)/(board[i][j]-'0');
}
}
}
ret=min(ret,cnt);
}
}
return ret==10000 ? -1 : ret;
}
};
