题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26766
思路：由于数据不是很大，我们可以枚举骑士最后聚集的位置，然后枚举的时候用bfs搜索即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<vector> 7 using namespace std; 8 #define MAXN 14 9 10 struct Node{ 11 int x,y,step; 12 Node(){} 13 Node(int _x,int _y,int _step):x(_x),y(_y),step(_step){} 14 }; 15 int n,m,min_step; 16 char map[MAXN][MAXN]; 17 bool mark[MAXN][MAXN]; 18 int dir[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}}; 19 vector<pair<int,pair<int,int> > >g; 20 21 int bfs(Node &st,Node &ed) 22 { 23 memset(mark,false,sizeof(mark)); 24 queue<Node>que; 25 que.push(st); 26 mark[st.x][st.y]=true; 27 while(!que.empty()){ 28 Node q,p=que.front(); 29 que.pop(); 30 if(p.x==ed.x&&p.y==ed.y){ 31 return p.step; 32 } 33 for(int i=0;i<8;i++){ 34 q.x=p.x+dir[i][0]; 35 q.y=p.y+dir[i][1]; 36 if(q.x>=0&&q.x<n&&q.y>=0&&q.y<m&&!mark[q.x][q.y]){ 37 mark[q.x][q.y]=true; 38 q.step=p.step+1; 39 que.push(q); 40 } 41 } 42 } 43 return -1; 44 } 45 46 void Solve() 47 { 48 min_step=1000000; 49 for(int i=0;i<n;i++){ 50 for(int j=0;j<m;j++){ 51 bool flag=true; 52 int step=0; 53 for(int k=0;k<g.size();k++){ 54 Node st,ed; 55 int kk=g[k].first;//骑士的种类 56 st.x=g[k].second.first,st.y=g[k].second.second,st.step=0; 57 ed.x=i,ed.y=j; 58 int dd=bfs(st,ed); 59 if(dd==-1){ flag=false;break; } 60 step+=(dd+kk-1)/kk; 61 } 62 if(flag)min_step=min(min_step,step); 63 } 64 } 65 if(min_step==1000000){ 66 puts("-1"); 67 }else 68 printf("%d ",min_step); 69 } 70 71 72 int main() 73 { 74 int _case,t=1; 75 scanf("%d",&_case); 76 while(_case--){ 77 scanf("%d%d",&n,&m); 78 g.clear(); 79 for(int i=0;i<n;i++){ 80 scanf("%s",map[i]); 81 for(int j=0;j<m;j++){ 82 if(map[i][j]>='1'&&map[i][j]<='9')g.push_back((make_pair(map[i][j]-'0',make_pair(i,j)))); 83 } 84 } 85 printf("Case %d: ",t++); 86 Solve(); 87 } 88 return 0; 89 }