大体思路是利用深度优先搜索算法,搜索出口。遇到钥匙,就拿钥匙,从钥匙开始重新搜索出口。
#include <stdio.h>
char maze[50][50];
int fx[] = { 1, -1, 0, 0 };
int fy[] = { 0, 0, -1, 1 };
int p; /*门的数量 */
int xzb[20] = { 0 };
int yzb[20] = { 0 };
int len; /*有效搜索路径的长度 */
int key[10] = { 0 }; /*存储已获得的钥匙 */
int IsGetkey(char n);
int IsKey(char n);
int check(char maze[50][50], int n, int m, int i, int j);
int search(char maze[50][50], char exit,int n, int m, int i, int j, int pi,
int pj);
int
main(void)
{
int i, j;
int n, m;
int ei, ej; /*搜索入口 */
if (freopen("maze.in", "r", stdin) == NULL)
return -1;
scanf("%d%d", &n, &m);
scanf("%d", &p);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
scanf("%c", &maze[i][j]);
if (maze[i][j] == '\n')
scanf("%c", &maze[i][j]);
}
for (i = 0; i < n + 1; i++) {
for (j = 0; j < m; j++) {
printf("%c", maze[i][j]);
}
printf("\n");
}
close(stdin);
for (i = 0; i < n + 1; i++)
for (j = 0; j < m; j++)
if (maze[i][j] == '$') {
ei = i;
ej = j;
i = 100;
j = 100;
}
search(maze, '&', n, m, ei, ej, -1, -1);
}
/*搜索*/
int
search(char maze[50][50], char exit,int n, int m, int i, int j, int pi, int pj)
{
char tmp;
int k, ni, nj; /*ni,nj表示下一个搜索点的坐标 */
if (maze[i][j] == exit) {
printf("到迷宫出口需要%d步\n",len);
printf("出口坐标:<%d,%d>\n\n", i, j);
for (k = 0; k < len; k++)
printf("<%d,%d>\n", xzb[k], yzb[k]);
return 1;
} else if (IsKey(maze[i][j])) {
tmp = maze[i][j];
maze[i][j] = '.';
search(maze, '&',n, m, i, j, -1, -1);
}
for (k = 0; k < 4; k++) {
ni = i + fx[k];
nj = j + fy[k];
if (ni == pi && nj == pj)
continue;
if (check(maze, n, m, ni, nj)) {
xzb[len] = i;
yzb[len] = j;
len += 1;
if (search(maze, '&',n, m, ni, nj, i, j) == 1)
return 1;
}
}
len -= 1;
return -1;}
/*检查下一个搜索点是否有效*/
int
check(char maze[50][50], int n, int m, int i, int j)
{
int flag = 1;
if (i < 0 || i >= n || j < 0 || j >= m)
flag = 0;
else if (maze[i][j] >= 'A' && maze[i][j] <= 'Z'
&& IsGetkey(maze[i][j])) ;
else if (maze[i][j] != '.' && maze[i][j] != '&' && maze[i][j] < 'a')
flag = 0;
return flag;
}
/*IsKey 判断当前搜索点是不是钥匙,是返回1
* 否返回 0
* */
int
IsKey(char n)
{
if (n >= 'a' && n <= 'a' + p - 1) {
key[n - 'a'] += 1;
return 1;
} else
return 0;
}
/*如果当前搜索点是门,判断当前有没有该门钥匙
* */
int
IsGetkey(char n)
{
if (key[n - 65] == 1 || n >= 'a') {
key[n - 65] -= 1; /*每个钥匙只有一次使用机会 */
return 1;
}
return 0;
}