国王与骑士问题（用java代码实现）

国王与骑士问题
具体要求如下：
（1）：初始状态：一个国王和N个骑士分布在8*8的棋盘上 0 <= N <=63。
（2）：目标状态：国王和所有的骑士走到同一个格子里。
（3）：游戏规则：在一次移动中，国王可以走到相邻的八个格子里；骑士可以走八个方向的“日”字；国王和某个骑士相遇后，可以由骑士带着移动。
（4）：要求：编写算法解决问题，用最少的总移动步数达到目标状态。

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7517490
• 这篇博客你也可以参考下：[C语言]国王的许诺：相传国际象棋是古印度舍罕王的宰相达依尔发明的。舍罕王十分喜欢象棋，决定让宰相西萨自己选择何种赏赐。这位聪明的宰相指着8 × 8共64格的象棋盘说：陛下，请您赏给我一些麦子吧。。。
• 除此之外, 这篇博客: 7-8 城市间紧急救援 (25 分)中的 作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 输入格式:
  输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

  输出格式:
  第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

  输入样例：

  4 5 0 3
  20 30 40 10
  0 1 1
  1 3 2
  0 3 3
  0 2 2
  2 3 2

  输出样例：

  2 60
  0 1 3

  代码如下：

  #include<iostream>
  #include<stack>
  using namespace std;
  
  #define INF 10005
  
  int n,m,c,d;
  
  int edge[510][510]; //储存各城市之间的连通关系
  int weight[510];   //储存各城市的救援队的数目
  int dist[510];  //储存出发点到城市i的最短路径
  int num[510];   //表示从出发点到城市i的最短路径的条数
  int w[510];    //表示从出发点到城市i的救援队数目的和
  int s[510];   //储存已访问的点集
  int path[510]; //保存以第i个结点为终点的最短路径的前一个结点的编号 
   //path的目的是为了后续输出路径的时候有迹可循 
  void Dijkstra(int v){
  	fill(dist,dist + 510,INF);//一系列初始化操作 
  	dist[v] = 0;
  	w[v] = weight[v];
  	num[v] = 1;
  	path[v] = -1;
  	
  	for(int i = 0;i < n;i ++){
  		int u = -1,minx = INF;
  		for(int j = 0;j < n;j ++){
  			if(minx > dist[j] && s[j] == 0){//从未被访问过的节点中找到最小的节点 
  				u = j;
  				minx = dist[j];
  			}
  		}
  		if(u == -1)  break;//不连通
  		s[u] = 1;//将找到的节点设置为已访问
  		for(int j = 0;j < n;j ++){
  			if(s[j] == 0 && edge[u][j] != INF){//u到j可通且未被访问 
  				if(dist[u] + edge[u][j] < dist[j]){//若经过u点再到j点的最短路径比直接从起点到j点的最短路径短，则更新 
  					dist[j] = dist[u] + edge[u][j];
  					num[j] = num[u];
  					w[j] = w[u] + weight[j];//救援队数目增加
  					path[j] = u; 
  				}else if(dist[u] + edge[u][j] == dist[j]){//若经过u点再到j点的最短路径和直接从起点到j点的最短路径一样长，也更新 
  					num[j] = num[j] + num[u];
  					if(w[u] + weight[j] > w[j]){
  						w[j] = w[u] + weight[j];
  						path[j] = u; 
  					}
  				}
  			}
  		} 
  	} 
  } 
   
  int main(){
  	cin >> n >> m >> c >> d;
  	for(int i = 0;i < n;i ++){
  		cin >> weight[i];
  	}
  	for(int i = 0;i < n;i ++){//初始化 
  		for(int j = 0;j < n;j ++){
  			edge[i][j] = INF;
  		}
  	}
  	for(int i = 0;i < m;i ++){
  		int a,b,l;
  		cin >> a >> b >> l;
  		edge[a][b] = edge[b][a] = l;
  	}
  	
  	Dijkstra(c);
  	cout << num[d] << " " << w[d] << endl;
  	stack<int> ss;
  	ss.push(d);
  	while(path[d] != 0){//这里就体现了path的作用,就是为了打印路径 
  		ss.push(path[d]);
  		d = path[d];
  	}
  	cout << c;
  	while(!ss.empty()){
  		cout << " " << ss.top();
  		ss.pop();
  	}
  	return 0;
  }
  

  我感觉这种题目基本上都有这么几个数组
  edge[][] ：存储两个节点之间的连通关系
  dist[] ：存储从起点到第i个点的最短路径，初始时全初始化为INF，因为在运行Dijkstra算法的时候需要不断的更新成一个更小的值（毕竟是找最短路径）
  s[]：这个集合表示已访问的节点，若已访问则为1，未访问则为0，初始时都为0
  path[]：这个数组存储以第i个结点为终点的最短路径的前一个节点，存在目的是为了后续打印最短路径
  其他的都是根据题目随机应变

参照这个思路即可（原文是C++的，你自己改写下）