本文共 1967 字，大约阅读时间需要 6 分钟。
有一个6*6的棋盘，每个棋盘上都有一个数值，现在又一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：
1、只能沿上下左右四个方向移动 2、总代价是没走一步的代价之和 3、每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积 4、初始状态为1每走一步，状态按如下公式变化：（走这步的代价%4）+1。
第一行有一个正整数n，表示有n组数据。
每组数据一开始为6*6的矩阵，矩阵的值为大于等于1小于等于10的值，然后四个整数表示起始坐标和终止坐标。输出最小代价。
11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 10 0 5 5
23
思路：
本题我开始不会做，参考了别人的博客做出来的。
此题比较好的办法是用BFS，求的过程中要适当剪枝。
DFS也可求解。
参考的博客地址：
http://blog.csdn.net/gladyoucame/article/details/8803904
里面分别用C++实现了BFS和DFS。
我的C代码：
#include#include #define INF (1e9)#define M (6*6*4+1) typedef struct node { int x, y; int sum; int state;} Point; int cost[6][6][4];int value[6][6];Point begin, end;int dir[4][2] = { {0, 1},{1, 0},{0, -1},{-1, 0}};Point *queue[M];int front, rear; void initQueue(){ front = rear = 0;} int isEmpty(){ return front == rear;} void push(Point *a){ queue[rear] = a; rear = (rear+1)%M;} Point *top(){ return queue[front];} void pop(){ front = (front+1)%M;} void BFS(){ int i; push(&begin); while (!isEmpty()) { Point *p = top(); pop(); for (i=0; i<4; i++) { int tx = p->x + dir[i][0]; int ty = p->y + dir[i][1]; if (tx>=0 && tx<6 && ty>=0 && ty<6) { int tcost = p->state * value[tx][ty]; int costNow = p->sum + tcost; if (costNow < cost[tx][ty][tcost%4] && costNow < cost[end.x][end.y][tcost%4]) { cost[tx][ty][tcost%4] = costNow; Point *p1 = (Point *)malloc(sizeof(Point)); p1->x = tx; p1->y = ty; p1->sum = costNow; p1->state = tcost%4 + 1; push(p1); } } } if (p != &begin) free(p); }} int Min(int a, int b){ return (a