Question

用C语言和栈求解迷宫路径

求解路径的代码不会写

Answer 1

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	int x;
	int y;
	int type;
	int v;
}POINT;

POINT s[10][10],stack[50],start,end,c;
int pos=0;

void prt()
{
	int i,j;
	system("cls");
	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
		{
			if(end.x==i && end.y==j)
			{
				printf("ex");
			}
			else if(s[i][j].type==1)
			{
				printf("■");
			}
			else if(i==c.x && j==c.y)
			{
				printf("●");
			}
			else
			{
				printf("  ");
			}
		}
		printf("\n");
	}
	system("pause");
}

void stack_in(POINT a)
{
	stack[pos++]=a;
}

POINT stack_out()
{
	int i;
	POINT t;
	t=stack[0];
	for(i=0;i<pos-1;i++)
	{
		stack[i]=stack[i+1];
	}
	pos--;
	return t;
}

void fun()
{
	POINT 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<=9 && 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<=9 && 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]);
		}
	//	prt();
	}
}

void go(int x, int y)
{
	int v;
	while(1)
	{
		if(x==end.x && y==end.y)
		{
			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];
			x=x-1;
			prt();
			continue;
		}
		else if(x+1<=9 && s[x+1][y].v==v-1)
		{
			c=s[x+1][y];
			x++;
			prt();
			continue;
		}
		else if(y-1>=0 && s[x][y-1].v==v-1)
		{
			c=s[x][y-1];
			y--;
			prt();
			continue;
		}
		else if(y+1<=9 && s[x][y+1].v==v-1)
		{
			c=s[x][y+1];
			y++;
			prt();
			continue;
		}
	}
}

int main()
{
	int i,j;
	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
		{
			s[i][j].x=i;
			s[i][j].y=j;
			s[i][j].type=0;
			s[i][j].v=-1;
		}
	}
	int x,y;
	end=s[9][5];
	
	start=s[0][0];
	x=end.x;
	y=end.y;
	s[x][y].v=0;
	stack_in(end);
	s[0][4].type=1;
	s[0][8].type=1;
	s[1][2].type=1;
	s[1][6].type=1;
	s[1][8].type=1;
	s[2][0].type=1;
	s[2][2].type=1;
	s[2][4].type=1;
	s[2][5].type=1;
	s[2][6].type=1;
	s[2][6].type=1;
	s[3][2].type=1;
	s[3][4].type=1;
	s[3][8].type=1;
	s[4][0].type=1;
	s[4][2].type=1;
	s[4][4].type=1;
	s[4][6].type=1;
	s[4][7].type=1;
	s[4][8].type=1;
	s[5][2].type=1;
	s[6][0].type=1;
	s[6][2].type=1;
	s[6][4].type=1;
	s[6][5].type=1;
	s[6][6].type=1;
	s[6][7].type=1;
	s[6][8].type=1;
	s[7][2].type=1;
	s[7][4].type=1;
	s[7][8].type=1;
	s[8][1].type=1;
	s[8][2].type=1;
	s[8][4].type=1;
	s[8][6].type=1;
	s[8][8].type=1;
	s[9][4].type=1;
	s[9][6].type=1;
	fun();
	c=start;
	prt();
	go(start.x,start.y);
	return 0;
}