데이터 구조: 미로 (알 기 쉬 움)

3088 단어 데이터 구조
설명:
하나.지 도 를 설치 하면 0 으로 통할 수 있 음 을 표시 하고, 1 로 장애물 (통할 수 없 음) 을 표시 합 니 다.
둘.사상: 바로 사람 으로 하여 금 미로 안에서 위로, 아래로, 왼쪽으로, 오른쪽으로 (이 네 가지 순서, 너 도 마음대로 위로, 아래로, 왼쪽으로, 오른쪽으로) 움 직 이게 하 는 것 이다. 매번 걸 을 때마다 사람 이 가지 않 은 곳 을 가게 해 야 하기 때문에 우 리 는 여기 서 사람 이 걸 어 가 는 곳 을 1 로 설정한다. 여기 서 우 리 는 사람 이 위로 올 라 가 고 계속 걸 으 며 1 (장애물) 에 부 딪 히 는 것 을 알 면 사람 이 먼저 아래로 내 려 가 고 아래 에 있 는 곳 이 숫자 1 (즉 장애물) 이라는 것 을 발견 한다 고 가정 한다. 그래서 선택 한 사람 은 왼쪽으로, 왼쪽 에 있 는 곳 은 0 이 고 그 다음 에 사람 은 왼쪽으로, 그리고 지나 간 곳 의 숫자 를 1 로 바 꾼 다음 에 이렇게 계속 판단 한다.사람 이 다음 에 가 는 곳 의 숫자 가 0 인지, 0 이면 계속 전진 하고, 1 이면 다른 방향 을 시도 한다.만약 에 우리 가 위로, 아래로, 왼쪽으로, 오른쪽으로 의 숫자 가 모두 1 이라는 것 을 발견 한다 면 우 리 는 돌 이 켜 보면 사람 은 자신의 이전 위치 로 물 러 날 것 이다. 만약 에 위로, 아래로, 왼쪽으로, 오른쪽으로 의 이 숫자 들 이 모두 1 이 라면 당신 이 설정 한 출구 를 찾 을 때 까지 계속 거 슬러 올 라 갈 것 이다.
셋.도구:  스 택 (선진 후 출) 과 2 차원 배열.
#include
#include
#define M 10
int map[M][M]={
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1},	
};
int map1[M][M]={
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1},	
};
int top =0;
typedef struct{
	int i;
	int j;
} Route;

void up(Route route[])
{
	map[route[top].i][route[top].j]=1;
	top++;
	route[top].i=route[top-1].i-1;
	route[top].j=route[top-1].j;
}
void down(Route route[])
{
	map[route[top].i][route[top].j]=1;
	top++;
	route[top].i=route[top-1].i+1;
	route[top].j=route[top-1].j;	
}
void left(Route route[])
{
	map[route[top].i][route[top].j]=1;
	top++;
	route[top].i=route[top-1].i;
	route[top].j=route[top-1].j-1;
}
void right(Route route[])
{
	map[route[top].i][route[top].j]=1;
	top++;
	route[top].i=route[top-1].i;
	route[top].j=route[top-1].j+1;
}
void back(Route route[])
{
	map[route[top].i][route[top].j]=1;
	top--;
}
int map_route(Route route[],int x,int y)
{
	do
	{
		if(map[route[top].i-1][route[top].j]==0)
		up(route);
		else
		{
			if(map[route[top].i+1][route[top].j]==0)
			down(route);
			else
			{
				if(map[route[top].i][route[top].j-1]==0)
				left(route);
				else
				{
					if(map[route[top].i][route[top].j+1]==0)
					right(route);
					else
					back(route);					
				}				
			}
		}
		if(route[top].i==x&&route[top].j==y)
		break;
	}while(top>=0);
	return 0;
}
int match(Route route[],int i,int j)
{
	for(int val=0;val<=top;val++)
	{
		if(i==route[val].i&&j==route[val].j)
		{
			return 1;
			break;
		}
	}
	return 0;
}
int main()
{
	Route route[M*M];
	route[top].i=8;
	route[top].j=8;//       
	int x=1,y=1;//       
	if(map[x][y]==1||map[route[top].i][route[top].j]==1)
	{
		printf("             ");
		exit(0);
	}
	map_route(route,x,y);
	printf("     
"); for(int i =0;i

 

좋은 웹페이지 즐겨찾기