#define MAXSIZE 100
using namespace std
struct stack{
int iway
int jway
int dire
}
stack maze[MAXSIZE]
int top
int map[14][28]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1},
{1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}
void findway(int xS,int yS,int xE,int yE)
{
top=0
maze[top].iway=xS
maze[top].jway=yS
map[xS][yS]=-1
int i,j,di,find
while(top>-1)
{
i=maze[top].iway
j=maze[top].jway
di=maze[top].dire
if(i==xE&&j==yE)
{
cout<<"***********************************\n"
cout<<"path"<<":"<<endl
cout<<"("<<maze[0].iway<<","<<maze[0].jway<<")"
for(int val=1val<top+1val++)
{
cout<("<<maze[val].iway<<","<<maze[val].jway<<")"
if((val+1)%5==0)
cout<<endl
}
cout<<endl
cout<<"***********************************\n"
return
}
find=0
while(find==0&&di<4)
{
di++
switch(di)
{
case(0):i=maze[top].iway
j=maze[top].jway+1
break
case(1):i=maze[top].iway
j=maze[top].jway-1
break
case(2):i=maze[top].iway+1
j=maze[top].jway
break
case(3):i=maze[top].iway-1
j=maze[top].jway
break
}
if(map[i][j]==0)
{
find=1
}
}
if(find==1)
{
maze[top].dire=di
top++
maze[top].iway=i
maze[top].jway=j
maze[top].dire=-1
map[i][j]=-1
}
else
{
map[maze[top].iway][maze[top].jway]=0
top--
}
}
}
int main()
{
for(int i=0i<14i++) //迷宫图形化输出
{
for(int j=0j<28j++)
{
if(map[i][j]==1)
cout<<"■"
else cout<<"□"
}
cout<<endl
}
int xStart,yStart,xEnd,yEnd
cout<<"请输入迷宫起点坐标,用空格隔开(左上角坐标为(0,0)):"
cin>>xStart>>yStart
cout<<"请输入迷宫终点坐标,用空格隔开(右上角坐标为(13,27)):"
cin>>xEnd>>yEnd
findway(xStart,yStart,xEnd,yEnd)
return 0
}
满意请采纳!
#include <stdio.h>#include <mem.h>void main() { int a[100][100]//0:blocked 1:passage 2:finish -1:visitedint b[10000][2]int m=0,n=0int sttop=0int i,j,k,lmemset(a,0,sizeof(a))printf("Please Input m,n:")scanf("%d%d",&m,&n)printf("Input the start:")scanf("%d%d",&i,&j)b[0][0]=i-1b[0][1]=j-1printf("Input the Map:\n")for (i=0i<mi++) for (j=0j<nj++) { scanf("%d",&a[i][j])} printf("Input the Finish:")scanf("%d%d",&i,&j)a[i-1][j-1]=2i=b[sttop][0]j=b[sttop][1]a[i][j]=-1while (sttop!=-1) { if (i>0) { //can up? if (a[i-1][j]==1) { a[--i][j]=-1b[++sttop][0]=ib[sttop][1]=jcontinue}else if (a[i-1][j]==2) { b[++sttop][0]=--ib[sttop][1]=jbreak} } if (i<m-1) { //can up? if (a[i+1][j]==1) { a[++i][j]=-1b[++sttop][0]=ib[sttop][1]=jcontinue}else if (a[i+1][j]==2) { b[++sttop][0]=++ib[sttop][1]=jbreak} } if (j>0) { //can left? if (a[i][j-1]==1) { a[i][--j]=-1b[++sttop][0]=ib[sttop][1]=jcontinue}else if (a[i][j-1]==2) { b[++sttop][0]=ib[sttop][1]=--jbreak} } if (j<m-1) { //can up? if (a[i][j+1]==1) { a[i][++j]=-1b[++sttop][0]=ib[sttop][1]=jcontinue}else if (a[i][j+1]==2) { b[++sttop][0]=ib[sttop][1]=j++break} } sttop--} if (sttop+1) { for (i=0i<sttopi++) printf("(%d,%d)->",b[i][0]+1,b[i][1]+1)printf("(%d,%d)\n",b[i][0]+1,b[i][1]+1)} else printf("Can't Reach The Finish Spot!\n")return} 用非嵌套的方法做的栈,起点 终点自己定 输入数据规则如下: 先输入m n(m为行数,n为列数) 再输入起点(最左上角为(1,1)(前者行号,后者列号)则输入"1 1"(不含引号)其他依次类推) 再输入地图(0为被阻挡,1为通路)(起点被默认为通路,无论输入0还是1) 再输入终点(规则和起点一样) 回车后出结果,结果的表达方式以(x,y)->(x,y)->....->(x,y)(坐标任以1,1为左上角) 或者Can't Reach The Finish Spot! 呈现 其他的修改的话可以随便咯(规模m,n<=100,太大栈放不下了)//寻路_带权重_带障碍_最短_文件地图_不闪------wlfryq------//#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
typedef struct
{
int x
int y
} _PT
_PT pt
int row=0,col=0
//设置CMD窗口光标位置
void setxy(int x, int y)
{
COORD coord = {x, y}
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord)
}
//获取当前CMD当前光标所在位置
void getxy()
{
HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE)
COORD coordScreen = {0, 0} //光标位置
CONSOLE_SCREEN_BUFFER_INFO csbi
if (GetConsoleScreenBufferInfo(hConsole, &csbi))
{
pt.x=csbi.dwCursorPosition.X
pt.y=csbi.dwCursorPosition.Y
}
}
typedef struct
{
int x
int y
int type
int v
}PT
PT **s=NULL,stack[50],start,end,c
int pos=0
void prt()
{
int i,j
system("cls")
for(i=0i<rowi++)
{
for(j=0j<colj++)
{
if(s[i][j].type==1)
{
printf("■")
}
else if(i==end.x && j==end.y)
{
printf("★")
}
else if(i==c.x && j==c.y)
{
printf("◎")
}
else
{
printf(" ")
}
}
printf("\n")
}
Sleep(500)
}
void stack_in(PT a)
{
stack[pos++]=a
}
PT stack_out()
{
int i
PT t
t=stack[0]
for(i=0i<pos-1i++)
{
stack[i]=stack[i+1]
}
pos--
return t
}
void fun()
{
PT a
int x,y,v
while(1)
{
if(pos==0)
{
break
}
a=stack_out()
x=a.x
y=a.y
if(x==start.x && y==start.y)
{
break
}
v=s[x][y].v
if(x-1>=0 && s[x-1][y].type==0 && (s[x-1][y].v==-1 || s[x-1][y].v>v+1))
{
s[x-1][y].v=v+1
stack_in(s[x-1][y])
}
if(x+1<=row-1 && s[x+1][y].type==0 && (s[x+1][y].v==-1 || s[x-1][y].v>v+1))
{
s[x+1][y].v=v+1
stack_in(s[x+1][y])
}
if(y-1>=0 && s[x][y-1].type==0 && (s[x][y-1].v==-1 || s[x-1][y].v>v+1))
{
s[x][y-1].v=v+1
stack_in(s[x][y-1])
}
if(y+1<=col-1 && s[x][y+1].type==0 && (s[x][y+1].v==-1 || s[x-1][y].v>v+1))
{
s[x][y+1].v=v+1
stack_in(s[x][y+1])
}
}
}
void go(int x, int y)
{
printf("\n按任意键开始\n")
getchar()
int v
while(1)
{
if(x==end.x && y==end.y)
{
setxy(0,y+2)
printf("end....")
return
}
v=s[x][y].v
if(v==0)
{
return
}
if(x-1>=0 && s[x-1][y].v==v-1)
{
c=s[x-1][y]
setxy(y*2,x)
x=x-1
printf(" ")
setxy(y*2,x)
printf("◎")
Sleep(500)
continue
}
else if(x+1<=row-1 && s[x+1][y].v==v-1)
{
c=s[x+1][y]
setxy(y*2,x)
x++
printf(" ")
setxy(y*2,x)
printf("◎")
Sleep(500)
continue
}
else if(y-1>=0 && s[x][y-1].v==v-1)
{
c=s[x][y-1]
setxy(y*2,x)
y--
printf(" ")
setxy(y*2,x)
printf("◎")
Sleep(500)
continue
}
else if(y+1<=col-1 && s[x][y+1].v==v-1)
{
c=s[x][y+1]
setxy(y*2,x)
y++
printf(" ")
setxy(y*2,x)
printf("◎")
Sleep(500)
continue
}
}
printf("\nreturn go\n")
system("pause")
}
void GetMapFromFile()
{
int i,j,x,y,len
char ch[50]={'\0'}
FILE* fp=fopen("e:\\map1.txt","r")
if(fp==NULL)
{
printf("open file failed.\n")
return
}
x=0
while(!feof(fp))
{
fgets(ch,50,fp)
row++
}
col=strlen(ch)
fseek(fp,0L,SEEK_SET)
while(!feof(fp))
{
fgets(ch,50,fp)
if(s==NULL)
{
len=strlen(ch)
for(i=len-1i>0i--)
{
if(ch[i]!='0' && ch[i]!='1')
{
ch[i]='\0'
}
else
{
break
}
}
len=strlen(ch)
s=(PT**)malloc(sizeof(PT*)*row)
for(j=0j<lenj++)
{
*(s+j)=(PT*)malloc(sizeof(PT)*len)
}
}
y=0
for(i=0i<leni++)
{
s[x][y].type=ch[i]-48
s[x][y].x=x
s[x][y].y=y
s[x][y].v=-1
y++
}
x++
}
start=s[row-2][1]
end=s[row-2][len-2]
fclose(fp)
}
int main()
{
GetMapFromFile()
int i,j
int x,y
x=end.x
y=end.y
s[x][y].v=0
stack_in(end)
fun()
c=start
prt()
go(start.x,start.y)
return 0
}