回复 10楼 xzlxzlxzl
不必先去弄最优解啊~弄个其中一个解出来就已经很强大了~~我在你的另一个贴说了一下简单的设想~这只是我的设想而已~现阶段实现不了就不要强求~当我什么都没有说~
[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
#include <stdio.h> #include <string.h> #include <stdlib.h> #define NUM 5 typedef struct bgMatrix { int v, w; char matrix[NUM][NUM]; int pre; int f; int g; bool isVisited; }Matrix; typedef struct bgQueue { Matrix* data; int length; int maxLength; int head; int tail; }BGQueue; typedef BGQueue* Queue; typedef struct bgStack { Matrix* data; int top; }BGStack; typedef BGStack* Stack; char srcMatrix[NUM][NUM] = { {'*', '*', '*', '*', '*'}, {'*', '2', '8', '3', '*'}, {'*', '1', '6', '4', '*'}, {'*', '7', '0', '5', '*'}, {'*', '*', '*', '*', '*'} }; char dstMatrix[NUM][NUM] = { {'*', '*', '*', '*', '*'}, {'*', '1', '2', '3', '*'}, {'*', '8', '0', '4', '*'}, {'*', '7', '6', '5', '*'}, {'*', '*', '*', '*', '*'} }; int dx[4] = {0, 0, -1, 1}; int dy[4] = {1, -1, 0, 0}; int cnt = -1; Queue queue; Stack stack; bool astar(Matrix matrix); int getG(Matrix matrix); void initQueue(int length); void putQueue(Matrix matrix); Matrix getQueue(void); int isQueueEmpty(void); int isQueueFull(void); void initStack(int length); void pushStack(Matrix matrix); Matrix popStack(void); int isStackEmpty(void); int matrixCmp(char src[][NUM], char dst[][NUM]); void matrixCpy(char dst[][NUM], char src[][NUM]); void matrixPrint(char matrix[][NUM]); int main(int argc, char *argv[]) { Matrix src; initQueue(3628800+1); initStack(3628800+1); src.v = 3; src.w = 2; matrixCpy(src.matrix, srcMatrix); src.pre = cnt; src.f = 0; src.g = getG(src); astar(src); return 0; } bool astar(Matrix matrix) { Matrix t, s; int v, w; int direction; putQueue(matrix); while (!isQueueEmpty()) { s = getQueue(); cnt++; for (direction = 0; direction < 4; direction++) { t = s; v = t.v + dx[direction]; w = t.w + dy[direction]; if (srcMatrix[v][w] != '*') { char c = t.matrix[t.v][t.w]; t.matrix[t.v][t.w] = t.matrix[v][w]; t.matrix[v][w] = c; t.v = v; t.w = w; t.pre = cnt; t.f = s.f + 1; t.g = getG(t); t.isVisited = false; int h = 0; for (; h < queue->tail; h++) { if (matrixCmp(queue->data[h].matrix, t.matrix)) { break; } } if (h == queue->tail) { putQueue(t); if (matrixCmp(t.matrix, dstMatrix)) { pushStack(t); for (int father = t.pre; !matrixCmp(queue->data[father].matrix, srcMatrix); father = queue->data[father].pre) { pushStack(queue->data[father]); } puts("PathFind = "); matrixCpy(t.matrix, srcMatrix); pushStack(t); while (!isStackEmpty()) { s = popStack(); matrixPrint(s.matrix); } return true; } } } } } return false; } int getG(Matrix matrix) { int g = 0; for (int i = 0; i < NUM; i++) { for (int j = 0; j < NUM; j++) { if (matrix.matrix[i][j] != '*' && matrix.matrix[i][j] != dstMatrix[i][j]) { g++; } } } return g; } void initQueue(int length) { queue =(bgQueue* ) malloc(sizeof(BGQueue)); queue->data =(bgMatrix* ) malloc(sizeof(Matrix) * length); queue->length = 0; queue->maxLength = length; queue->head = 0; queue->tail = 0; } void putQueue(Matrix matrix) { queue->data[queue->tail++] = matrix; queue->tail = queue->tail % queue->maxLength; queue->length++; Matrix* a =(bgMatrix* ) malloc(sizeof(Matrix) * queue->maxLength); Matrix* b =(bgMatrix* ) malloc(sizeof(Matrix) * queue->maxLength); int an = 0; int bn = 0; int i=0; for (i = 0; i < queue->length; i++) { if (queue->data[i].isVisited) { a[an++] = queue->data[i]; } else { b[bn++] = queue->data[i]; } } for (i = 0; i < bn-1; i++) { for (int j = bn-1; j > i; j--) { int h1 = b[j-1].f + b[j-1].g; int h2 = b[j].f + b[j].g; if (h1 > h2) { Matrix t = b[j-1]; b[j-1] = b[j]; b[j] = t; } } } for (i = 0; i < an; i++) { queue->data[i] = a[i]; } for (i = 0; i < bn; i++) { queue->data[an+i] = b[i]; } free(a); free(b); } Matrix getQueue(void) { queue->data[queue->head].isVisited = true; Matrix ret; ret = queue->data[queue->head++]; queue->head = queue->head % queue->maxLength; return ret; } int isQueueEmpty(void) { return queue->head == queue->tail; } int isQueueFull(void) { return ((queue->tail+1) % queue->maxLength) == queue->head; } void initStack(int length) { stack = (bgStack* )malloc(sizeof(BGStack)); stack->data =(bgMatrix* ) malloc(sizeof(Matrix) * length); stack->top = 0; } void pushStack(Matrix matrix) { stack->data[stack->top++] = matrix; } Matrix popStack(void) { Matrix ret; ret = stack->data[--stack->top]; return ret; } int isStackEmpty(void) { return (stack->top == 0); } int matrixCmp(char src[][NUM], char dst[][NUM]) { int i, j, s, t, ret; char srcString[30] = {0}; char dstString[30] = {0}; s = 0; t = 0; for (i = 0; i < NUM; i++) { for (j = 0; j < NUM; j++) { srcString[s++] = src[i][j]; dstString[t++] = dst[i][j]; } } ret = !strcmp(srcString, dstString); return ret; } void matrixCpy(char dst[][NUM], char src[][NUM]) { int i, j; for (i = 0; i < NUM; i++) { for (j = 0; j < NUM; j++) { dst[i][j] = src[i][j]; } } } void matrixPrint(char matrix[][NUM]) { char s[60] = {0}; int i, j, k; k = 0; for (i = 0; i < NUM; i++) { for (j = 0; j < NUM; j++) { s[k++] = matrix[i][j]; } s[k++] = '\r'; s[k++] = '\n'; } s[k++] = '\r'; s[k++] = '\n'; puts(s); }
[此贴子已经被作者于2017-6-10 04:22编辑过]