求助，用C语言并用回溯算法编写的有关蛇吃苹果走迷宫的程序，题目如下：
发布网友
发布时间：2022-10-08 05:05
共1个回答
热心网友
时间：2023-11-04 06:04
* snake
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DEBUG 0
#define printpos() \
printf("File: %s\tLine: %d\n", __FILE__, __LINE__); fflush(stdout);
#define CALLOC(ARRAY, NUM, TYPE)\
ARRAY = (TYPE*) calloc(NUM, sizeof(TYPE));\
if (ARRAY == NULL) {\
printf("File: %s, Line: %d: ", __FILE__, __LINE__); \
printf("Allocating memory failed.\n");\
exit(0);\
}
#define REALLOC(ARRAY, NUM, TYPE)\
ARRAY = (TYPE*) realloc(ARRAY, (NUM)*sizeof(TYPE));\
if (ARRAY == NULL) {\
printf("File: %s, Line: %d: ", __FILE__, __LINE__); \
printf("Allocating memory failed.\n");\
exit(0);\
}
const int START = -1;
const int HOME = -2;
#if DEBUG
int m=4, n=4;
int a[4][4] = {{7, 0, 4, 18}, {4, 0, 1, 1}, {15, 7, 11, -1}, {0, 12, -2, 0}};
#else
int m=0, n=0;
int **a=NULL;
#endif
struct pos {
int x;
int y;
};
typedef struct pos pos;
struct node {
pos p;
int mv;
int n;
};
typedef struct node node;
const pos mv[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
/*
* get m, n, a and check them
*/
int setup()
{
int nstart=0, nhome=0;
int i, j;
#if DEBUG
#else
//get the dimension of the matrix and allocate memory
printf("Please input the number of rows of the matrix: ");
scanf("%d", &m);
if (m<=0) {
printf("Number of rows must be greater than 0.\n");
exit(0);
}
a = (int**) calloc(m, sizeof(int*));
if (a == NULL) {
printf("Allocate memory failed.\n");
exit(1);
}
printf("Please input the number of columns of the matrix: ");
scanf("%d", &n);
if (n<=0) {
printf("Number of columns must be greater than 0.\n");
exit(0);
}
for (i=0; i<m; i++) {
a[i] = (int*) calloc(n, sizeof(int));
if (a[i] == NULL) {
printf("Allocate memory failed.\n");
exit(1);
}
}
//get the matrix
printf("Please input the matrix, entities seperated by blank:\n");
for (i=0; i<m; i++) {
for (j=0; j<n; j++) {
scanf("%d", &a[i][j]);
}
}
#endif
//check the matrix
for (i=0; i<m; i++) {
for (j=0; j<n; j++) {
if (a[i][j] == START) {
nstart++;
if (nstart > 1) {
printf("More than 1 starting point.\n");
exit(0);
}
} else if (a[i][j] == HOME) {
nhome++;
if (nhome > 1) {
printf("More than 1 home point.\n");
exit(0);
}
} else if (a[i][j] < 0) {
printf("a[%d][%d] = %d has no meaning.\n", i, j, a[i][j]);
exit(0);
}
}
}
if (nstart == 0) {
printf("No starting point.\n");
exit(0);
}
if (nhome == 0) {
printf("No home point.\n");
exit(0);
}
//output the matrix
printf("The matrix (%d X %d):\n", m, n);
for (i=0; i<m; i++) {
for (j=0; j<n; j++) {
printf("%d\t", a[i][j]);
}
printf("\n");
}
return 0;
}
int solve(node** optpath)
{
pos dest;//destinating point
node* curpath = NULL;//current path
node** sol = NULL;
int nsol = 0;
int nsteps;//number of steps
int i, j;
int curmv = -1;
int sucmv = 0;//sucessfully moved
int sum;
int maxsum=0;
//setup starting point
for (i=0; i<m; i++) {
for (j=0; j<n; j++) {
if (a[i][j] == START) {
dest.x = i;
dest.y = j;
break;
}
}
}
nsteps = 0;
CALLOC(curpath, nsteps+1, node);
curpath[0].p.x = dest.x;
curpath[0].p.y = dest.y;
curpath[0].mv = -1;
a[dest.x][dest.y] = 0;
curmv = 0;
while (1) {
for (sucmv=0, curmv=curpath[nsteps].mv+1; curmv<4; curmv++) {
dest.x = curpath[nsteps].p.x + mv[curmv].x;
dest.y = curpath[nsteps].p.y + mv[curmv].y;
if (dest.x < 0 || dest.x >= m || dest.y < 0 || dest.y >= n) {
curpath[nsteps].mv = curmv;
continue;
}
if (a[dest.x][dest.y] == 0) {
curpath[nsteps].mv = curmv;
continue;
}
nsteps++;
REALLOC(curpath, nsteps+1, node);
curpath[nsteps].p.x = dest.x;
curpath[nsteps].p.y = dest.y;
curpath[nsteps-1].mv = curmv;
curpath[nsteps].mv = -1;
curpath[nsteps].n = a[dest.x][dest.y];
a[dest.x][dest.y] = 0;
sucmv = 1;
break;
}
if (sucmv) {
if (curpath[nsteps].n == HOME) {
nsol++;
REALLOC(sol, nsol, node*);
CALLOC(sol[nsol-1], nsteps+1, node);
memcpy(sol[nsol-1], curpath, (nsteps+1)*sizeof(node));
//back
a[curpath[nsteps].p.x][curpath[nsteps].p.y] = curpath[nsteps].n;
nsteps--;
if (nsteps == -1 && curpath[0].mv == 3)break;
REALLOC(curpath, nsteps+1, node);
} else {
continue;
}
} else {
a[curpath[nsteps].p.x][curpath[nsteps].p.y] = curpath[nsteps].n;
nsteps--;
if (nsteps == -1 && curpath[0].mv == 3)break;
REALLOC(curpath, nsteps+1, node);
}
}
//printf("number of solutions: %d\n", nsol);
for (maxsum=0, i=0; i<nsol; i++) {
//printf("Solution %d \n", i);
//printf("\tPath: ");
sum = -1*HOME;
for (j=0; ; j++) {
//printf("(%d, %d)\t", sol[i][j].p.x, sol[i][j].p.y);
sum += sol[i][j].n;
if (sol[i][j].mv == -1) break;
}
//printf("\n\tSum of apples: %d\n", sum);
if (sum>maxsum) {
maxsum = sum;
*optpath = sol[i];
}
}
return 0;
}
int output(node* path)
{
int i=0, sum=0;
printf("Path: ");
sum = -1*HOME;
for (i=0; ; i++) {
printf("(%d, %d)\t", path[i].p.x, path[i].p.y);
sum += path[i].n;
if (path[i].mv == -1) break;
}
printf("\nSum of apples: %d\n", sum);
return 0;
}
int main()
{
node* path=NULL;
setup();
solve(&path);
output(path);
return 0;
}
编译、链接、运行程序，输入与输出如下：
:!gcc -Wall tmp.c -o tmp
:! ./tmp
Please input the number of rows of the matrix: 5
Please input the number of columns of the matrix: 5
Please input the matrix, entities seperated by blank:
1 7 9 7 0
-2 8 10 8 7
0 10 8 2 -1
4 3 0 7 0 9
1 2 5 1 0 7
The matrix (5 X 5):
1 7 9 7 0
-2 8 10 8 7
0 10 8 2 -1
4 3 0 7 0
9 1 2 5 1
Path: (2, 4) (1, 4) (1, 3) (0, 3) (0, 2) (1, 2) (2, 2) (2, 3) (3, 3) (4, 3) (4, 2) (4, 1) (4, 0) (3, 0) (3, 1) (2, 1) (1, 1) (0, 1) (0, 0) (1, 0)
Sum of apples: 108
:!gcc -Wall tmp.c -o tmp
:! ./tmp
Please input the number of rows of the matrix: 4
Please input the number of columns of the matrix: 4
Please input the matrix, entities seperated by blank:
7 0 4 18
4 0 1 1
15 7 11 -1
0 12 -2 0
The matrix (4 X 4):
70418
4011
15711-1
012-20
Path: (2, 3)(1, 3)(0, 3)(0, 2)(1, 2)(2, 2)(2, 1)(3, 1)(3, 2)
Sum of apples: 54
