#include <iostream>
#include <conio.h>
#include <windows.h>
#include <time.h>
using namespace std
#define Height 25//高度，必须为奇数
#define Width 25 //宽度，必须为奇数
#define Wall 1//用1表示墙
#define Road 0//用0表示路
#define Start 2
#define End 3
#define up 72
#define down 80
#define left 75
#define right 78
#define flag 5
int map[Height+2][Width+2]
int x=2,y=1//玩家当前位置，刚开始在入口处
class Migong
{
public:
void gotoxy(int x,int y) //移动坐标的函数声明
void shengcheng(int x,int y) //随机生成迷宫的函数声明
void display(int x,int y) //显示迷宫的函数声明
void chushi()//初始化迷宫的函数声明
}
class Wanjia:public Migong //玩家类由迷宫类派生来
{
public:
void gonglue(int x,int y)
void shang(int x,int y)
void xia(int x,int y)
void zuo(int x,int y)
void you(int x,int y)
void game()//游戏运行包括移动的函数声明
}
void Migong::gotoxy(int x,int y) //移动坐标 这是使光标 到（x，y）这个位置的函数.调用 COORD 需要#include.
{
COORD coord
coord.X=x
coord.Y=y
SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), coord )
}
void Migong::shengcheng(int x,int y) //随机生成迷宫
{
int c[4][2]={0,1,1,0,0,-1,-1,0}//四个方向//数组c 0 1 向右
// 1 0 向下
// -1 0 向上
// 0 -1 向左
int i,j,t
//将方向打乱
for(i=0i<4i++)
{
j=rand()%4 //随机生成j
t=c[i][0]c[i][0]=c[j][0]c[j][0]=t //将c[i][0]和c[j][0]交换
t=c[i][1]c[i][1]=c[j][1]c[j][1]=t //类似上
}
map[x][y]=Road //当前位置设为路
for(i=0i<4i++) //沿四个方向设置
if(map[x+2*c[i][0]][y+2*c[i][1]]==Wall)//沿c[i][0]、c[i][1]方向前2步如果是墙
{
map[x+c[i][0]][y+c[i][1]]=Road //让该方向前一步设为路
shengcheng(x+2*c[i][0],y+2*c[i][1]) //在该方向前两步继续生成地图因为这里是递归函数，当执行到最后一点发现都不能走的时候，
//会返回到上一个函数，也就是上一个点，再次判断是否可以产生地图 ，知道地图上所有点被遍历完。
}
}
void Migong::display(int x,int y) //显示迷宫
{
gotoxy(2*y-2,x-1)
switch(map[x][y])
{
case Start:
cout<<"入"break//显示入口
case End:
cout<<"出"break//显示出口
case Wall:
cout<<"■"break//显示墙
case Road:
cout<<" "break//显示路
case up:
cout<<"↑"break //在攻略中的标记 下同
case down:
cout<<"↓"break
case left:
cout<<"←"break
case right:
cout<<"→"break
case flag:
cout<<" "break //标记，防止攻略遍历时候无线循环
}
}
void Migong::chushi()
{
int i,j
srand((unsigned)time(NULL))//初始化随机种子
for(i=0i<=Height+1i++)
for(j=0j<=Width+1j++)
if(i==0||i==Height+1||j==0||j==Width+1) //初始化迷宫 默认四周是路
map[i][j]=Road
else map[i][j]=Wall
shengcheng(2*(rand()%(Height/2)+1),2*(rand()%(Width/2)+1))//从随机一个点开始生成迷宫，该点行列都为偶数
for(i=0i<=Height+1i++) //边界处理 把最开始默认为路的堵上,以免跑出迷宫
{
map[i][0]=Wall
map[i][Width+1]=Wall
}
for(j=0j<=Width+1j++) //边界处理
{
map[0][j]=Wall
map[Height+1][j]=Wall
}
map[2][1]=Start//给定入口
map[Height-1][Width]=End//给定出口
for(i=1i<=Heighti++)//i初始为1,结束为height,以免画出外围
for(j=1j<=Widthj++) //画出迷宫 同上
display(i,j)
}
void Wanjia::game()
{
int x=2,y=1//玩家当前位置，刚开始在入口处
int c//用来接收按键
while(1)
{
gotoxy(2*y-2,x-1)
cout<<"☆"//画出玩家当前位置
if(map[x][y]==End) //判断是否到达出口
{
gotoxy(30,24) //到达此坐标
cout<<"到达终点，按任意键结束"
getch()
break
c=getch()
}
if(c!=-32)
{
c=getch()
switch(c)
{
case 72: //向上走
if(map[x-1][y]!=Wall)
{
display(x,y)
x--
}
break
case 80: //向下走
if(map[x+1][y]!=Wall)
{
display(x,y)
x++
}
break
case 75: //向左走
if(map[x][y-1]!=Wall)
{
display(x,y)
y--
}
break
case 77: //向右走
if(map[x][y+1]!=Wall)
{
display(x,y)
y++
}
break
case 112://按下P
gonglue(2,1)break //如果按下P执行攻略函数
}
}
}
}
void Wanjia::shang(int x,int y)
{
if(map[x][y]==End) //判断是否到达出口
{
gotoxy(52,20) //到达此坐标
cout<<"到达终点，按任意键结束"
getch()
exit(0)
}
if(map[x-1][y]!=Wall&&map[x-1][y]!=up&&map[x-1][y]!=down&&map[x-1][y]!=left&&map[x-1][y]!=right&&map[x-1][y]!=flag)
{ //当移动后的下一个位置没有被走过且不是墙
map[x][y]=up
display(x,y)
x--
gonglue(x,y) //递归，攻略下一个点
}
}
void Wanjia::xia(int x,int y)
{
if(map[x][y]==End) //判断是否到达出口
{
gotoxy(52,20) //到达此坐标
cout<<"到达终点，按任意键结束"
getch()
exit(0)
}
if(map[x+1][y]!=Wall&&map[x+1][y]!=up&&map[x+1][y]!=down&&map[x+1][y]!=left&&map[x+1][y]!=right&&map[x+1][y]!=flag) //当移动后的下一个位置没有被走过且不是墙
{
map[x][y]=down
display(x,y)
x++
gonglue(x,y) //递归，攻略下一个点
}
}
void Wanjia::zuo(int x,int y)
{
if(map[x][y]==End) //判断是否到达出口
{
gotoxy(52,20) //到达此坐标
cout<<"到达终点，按任意键结束"
getch()
exit(0)
}
if(map[x][y-1]!=Wall&&map[x][y-1]!=up&&map[x][y-1]!=down&&map[x][y-1]!=left&&map[x][y-1]!=right&&map[x][y-1]!=flag) //当移动后的下一个位置没有被走过且不是墙
{
map[x][y]=left
display(x,y)
y--
gonglue(x,y)//递归，攻略下一个点
}
}
void Wanjia::you(int x,int y)
{
if(map[x][y]==End) //判断是否到达出口
{
gotoxy(52,20) //到达此坐标
cout<<"到达终点，按任意键结束"
getch()
exit(0)
}
if(map[x][y+1]!=Wall&&map[x][y+1]!=up&&map[x][y+1]!=down&&map[x][y+1]!=left&&map[x][y+1]!=right&&map[x][y+1]!=flag) //当移动后的下一个位置没有被走过且不是墙
{
map[x][y]=right
display(x,y)
y++
gonglue(x,y)//递归，攻略下一个点
}
}
void Wanjia::gonglue (int x,int y)
{
gotoxy(2*y-2,x-1)
cout<<"☆"//画出玩家当前位置
if(map[x][y]==End) //判断是否到达出口
{
gotoxy(52,20) //到达此坐标
cout<<"到达终点，按任意键结束"
getch()
exit(0)
}
shang(x,y)//上下左右
xia(x,y)
zuo(x,y)
you(x,y)
map[x][y]=flag//当上下左右都无法走的时候，即为死路，因为递归函数开始向后，所以讲死路点值置为flag，变成无形之墙。
display(x,y)
}
int main()
{
cout<<" 移动迷宫 "<<endl
cout<<"--------------------"<<endl
cout<<"欢迎来到移动迷宫游戏"<<endl
cout<<"--------------------"<<endl
cout<<"游戏说明：给定一出口和入口"<<endl
cout<<"玩家控制一个五角星（☆）从入口走到出口"<<endl
cout<<"系统会记录你所走的步数"<<endl
cout<<"按回车进入游戏"
cout<<"(按下P键可以获得攻略。)"
getch()
system("cls") //清屏函数 ，清除开始界面
Wanjia w1
w1.chushi()
w1.game()//开始游戏
//w1.gonglue(2,1) //功略显示
getch()
return 0
}
————————————————
版权声明：本文为CSDN博主「失落之风」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41572774/java/article/details/84035598
喜欢的源码拿走，把小赞赞留下
/** 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=0i<mi++) {
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=0i<mi++) {
for (j=0j<nj++) {
scanf("%d", &a[i][j])
}
}
#endif
//check the matrix
for (i=0i<mi++) {
for (j=0j<nj++) {
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=0i<mi++) {
for (j=0j<nj++) {
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=0i<mi++) {
for (j=0j<nj++) {
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+1curmv<4curmv++) {
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=0i<nsoli++) {
//printf("Solution %d \n", i)
//printf("\tPath: ")
sum = -1*HOME
for (j=0j++) {
//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=0i++) {
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):
7 0 4 18
4 0 1 1
15 7 11 -1
0 12 -2 0
Path: (2, 3) (1, 3) (0, 3) (0, 2) (1, 2) (2, 2) (2, 1) (3, 1) (3, 2)
Sum of apples: 54
迷宫求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
在资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
拜托高手大家些们，我写了个C语言的，但连接编译后才发现25个错误！但我就是找不出来了！麻烦哪位高手给我指点指点！我会追加分的！
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#define N 20
int aa[N][N]
int yes=0
int x[100][2],n=0
void fun1(int (*aa)[N],int (*a)[N])
int fun(int (*a)[N],int i,int j)
void begain(int (*t)[N])
void pr(int (*t)[N],int nn)
void win(int (*t)[N])
void lose()
void main(void)
{
int t[N][N]
begain(t)
pr(t,0)
fun(t,1,1)
if(yes)
win(t)
else
lose()
getch()
}
void fun1(int (*aa)[N],int (*a)[N])
{
int i,j
for(i=0i<Ni++)
for(j=0j<Nj++)
aa[i][j]=a[i][j]
}
int fun(int (*a)[N],int i,int j)
{
if(i==N-2&&j==N-2)
{
yes=1
return
}
a[i][j]=1
fun1(aa,a)
if(aa[i+1][j+1]==0&&!yes)
{
fun(aa,i+1,j+1)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
fun1(aa,a)
if(aa[i+1][j]==0&&!yes)
{
fun(aa,i+1,j)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
fun1(aa,a)
if(aa[i][j+1]==0&&!yes)
{
fun(aa,i,j+1)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
fun1(aa,a)
if(aa[i-1][j]==0&&!yes)
{
fun(aa,i-1,j)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
fun1(aa,a)
if(aa[i-1][j+1]==0&&!yes)
{
fun(aa,i-1,j+1)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
fun1(aa,a)
if(aa[i+1][j-1]==0&&!yes)
{
fun(aa,i+1,j-1)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
fun1(aa,a)
if(aa[i][j-1]==0&&!yes)
{
fun(aa,i,j-1)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
fun1(aa,a)
if(aa[i-1][j-1]==0&&!yes)
{
fun(aa,i-1,j-1)
if(yes)
{x[n][0]=i,x[n++][1]=jreturn}
}
}
void begain(int (*t)[N])
{
int i,j
system(cls)
randomize()
for(i=0i<Ni++)
{
for(j=0j<Nj++)
{
if(i==0||i==N-1||j==0||j==N-1)
t[i][j]=1
else if(i==1&&j==1||i==N-2&&j==N-2)
t[i][j]=0
else
t[i][j]=random(2)
}
}
}
void pr(int (*t)[N],int nn)
{
int i,j,ii
textcolor(RED)
gotoxy(1,1)
for(i=0i<Ni++)
{
for(j=0j<Nj++)
{
if(nn!=1)
printf(%2d,t[i][j])
else
{
for(ii=0ii<nii++)
{
if(x[ii][0]==i&&x[ii][1]==j)
{
cprintf(%2d,t[i][j])
break
}
}
if(ii<n)
continue
if(i==N-2&&j==N-2)
cprintf( 0)
else
printf(%2d,t[i][j])
}
}
printf(\n)
}
}
void win(int (*t)[N])
{
int i,j,ii,jj
for(i=0i<n-1i++)
for(j=i+1j<nj++)
if(x[j][0]==x[i][0]&&x[j][1]==x[i][1])
{
for(jj=j,ii=ijj<njj++,ii++)
{x[ii][0]=x[jj][0]x[ii][1]=x[jj][1]}
n=n-(j-i)
}
printf(\nThe way is:\n)
for(i=n-1i>=0i--)
printf(%3d%3d->,x[i][0],x[i][1])
printf(%3d%3d\n,N-2,N-2)
t[1][1]=0
pr(t,1)
}
void lose()
{
printf(\nNot find way!\n)
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）