根据历史传说记载，国际象棋起源于古印度，至今见诸于文献最早的记录是在萨珊王朝时期用波斯文写的。据说，有位印度教宗师见国王自负虚浮，决定给他一个教训。他向国王推荐了一种在当时尚无人知晓的游戏。国王当时整天被一群溜须拍马的大臣们包围，百无聊赖，很需要通过游戏方式来排遣郁闷的心情。
国王对这种新奇的游戏很快就产生了浓厚的兴趣，高兴之余，他便问那位宗师，作为对他忠心的奖赏，他需要得到什么赏赐。宗师开口说道：请您在棋盘上的第一个格子上放1粒麦子，第二个格子上放2粒，第三个格子上放4粒，第四个格子上放8粒……即每一个次序在后的格子中放的麦粒都必须是前一个格子麦粒数目的倍数，直到最后一个格子第64格放满为止，这样我就十分满足了。 “好吧！”国王哈哈大笑，慷慨地答应了宗师的这个谦卑的请求。
然而等到麦子成熟时，国王才发现，按照与宗师的约定，全印度的麦子竟然连棋盘一半的格子数目都不够。这位宗师索要的麦粒数目实际上是天文数字。
无奈的国王只好和这位宗师协商换一种奖励方式。
1、将棋盘扩大为N行N列；
2、将大量的麦子随机放在这个棋盘中；
3、宗师可以选择从任意一边出发，按照国际象棋中国王的移动规则从一个格子移动的另一个格子，并从相对的另一边离开；
4、宗师可以将自己到达的格子中的麦子收归自己所有
5、宗师必须在收获N个格子的麦子后从另一边正常离开棋盘，否则所有的收获无效。
聪明的宗师仔细地观察了棋盘，顺利获得了自己的最大收益。
请您编程看看他最多可获得多少粒麦子。
求解题思路，用了暴力dfs时间超限了。
这是一道典型的搜索题，但是暴力dfs肯定会超时，因为数据范围较大。因此我们需要优化搜索算法。
一个优化的思路是：在搜索过程中，我们可以记录下宗师到每个格子的最大收益，这样可以避免重复搜索同一格子。另外，我们可以采用记忆化搜索的方式，记录下已经搜索过的状态，避免重复搜索。
具体实现时，我们可以采用递归的方式进行搜索，每次递归时传入当前格子的位置、当前已获得的麦子数目、宗师到达当前格子的方向（左上、上、右上、左、右、左下、下、右下八个方向中的一个）。然后根据宗师到达当前格子的方向，判断宗师能够继续前进的方向，对每个可行的方向进行递归搜索，记录下搜索到的最大收益。
具体实现细节可以参考以下代码，其中dp[i][j][k]表示宗师到达(i, j)位置时，从k方向进入时能够获得的最大收益：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
int n, m;
int a[N][N];
int dp[N][N][8];
int dfs(int x, int y, int k, int cnt) {
if (cnt == n) return 0;
if (dp[x][y][k] != -1) return dp[x][y][k];
int res = 0;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (i != k && i != (k+4)%8) continue;
res = max(res, dfs(nx, ny, i, cnt+1) + a[nx][ny]);
}
return dp[x][y][k] = res;
}
int main() {
cin >> n >> m;
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < 8; k++) {
res = max(res, dfs(i, j, k, 1) + a[i][j]);
}
}
}
cout << res << endl;
return 0;
}
输入格式:
输入第一行给出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个结点为终点的最短路径的前一个节点，存在目的是为了后续打印最短路径
其他的都是根据题目随机应变