- it技术
- C语言利用递归求解迷宫问题
#include <stdio.h>
#include <stdlib.h>
#define M 4
#define N 5
#define MaxSize 15
int mg
[M
+ 2][N
+ 2] = {
{1,1,1,1,1,1,1},
{1,0,1,0,1,1,1},
{1,0,0,0,0,0,1},
{1,1,0,1,0,0,1},
{1,1,0,0,0,0,1},
{1,1,1,1,1,1,1}
};
typedef struct
{
int i
;
int j
;
}Box
;
typedef struct
{
Box data
[MaxSize
];
int length
;
}PathType
;
int count
= 0;
void mgpath(int xi
, int yi
, int xe
, int ye
, PathType path
, int& minPath
) {
int i
, j
, di
, k
;
if (xi
== xe
&& yi
== ye
) {
path
.data
[path
.length
].i
= xi
;
path
.data
[path
.length
].j
= yi
;
path
.length
++;
printf("迷宫路径%d如下：\n", ++count
);
for (k
= 0; k
< path
.length
; k
++) {
printf("\t(%d, %d)", path
.data
[k
].i
, path
.data
[k
].j
);
}
printf("\n");
printf("路径长度为%d\n",path
.length
);
printf("----------------------------------------------------------\n");
if (path
.length
< minPath
) {
minPath
= path
.length
;
}
}
else {
if (mg
[xi
][yi
] == 0) {
di
= 0;
while (di
< 4) {
path
.data
[path
.length
].i
= xi
;
path
.data
[path
.length
].j
= yi
;
path
.length
++;
switch (di
) {
case 0:i
= xi
- 1; j
= yi
; break;
case 1:i
= xi
; j
= yi
+ 1; break;
case 2:i
= xi
+ 1; j
= yi
; break;
case 3:i
= xi
; j
= yi
- 1; break;
}
mg
[xi
][yi
] = -1;
mgpath(i
, j
, xe
, ye
, path
, minPath
);
mg
[xi
][yi
] = 0;
path
.length
--;
di
++;
}
}
}
}
int main() {
PathType path
;
path
.length
= 0;
int minPath
= MaxSize
;
mgpath(1, 1, M
, N
, path
, minPath
);
printf("最短路径长度为%d", minPath
);
return 0;
}
