C 미로찾기

| 메모/자료구조 2012. 3. 31. 19:23

Posted by GreatPark

미로 찾기 소스

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

#define M 9
#define N 8
#define STACK_SIZE M*N

int move[4][2] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};

typedef struct {
	int i;
	int j;
	int dir;
}element;

element stack[STACK_SIZE];
int top = -1;
element current = {1, 1};

void push(element *stack, element item) {
	if(top >= STACK_SIZE - 1) {
		printf("Stack is full\n");
		return;
	}
	stack[++top] = item;
}

element pop(element *stack) {
	if(top == -1) {
		printf("Stack is empty\n");
		exit(1);
	}
	else return stack[top--];
}

int isEmpty(element *stack) {
	if(top == -1) return 1;
	else return 0;
}

void printMaze(int m[M+2][N+2]);
void mazePath();
void printPath();
void printCurrent(int m[M+2][N+2]);

void main() {
	int end;
	mazePath();

	fflush(stdin);
	printf("Press any key to exit\n");
	scanf("%d", &end);

}

void printMaze(int m[M+2][N+2]) {
	int i, j;

	printf("\n\n");
	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(m[i][j] == 0) printf("  ");
			else if(m[i][j] == 2) printf("○");
			else if(m[i][j] == 3) printf("☆");
			else printf("▩");
		}
		printf("\n");
	}
	printf("\n\n");
}

void mazePath() {
	int maze[M+2][N+2] = {
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
	{1, 2, 1, 1, 0, 1, 0, 1, 1, 1},
	{1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
	{1, 1, 0, 0, 0, 1, 0, 0, 0, 1},
	{1, 1, 1, 0, 0, 0, 1, 0, 1, 1},
	{1, 0, 0, 0, 1, 0, 1, 0, 1, 1},
	{1, 1, 0, 1, 0, 0, 0, 1, 1, 1},
	{1, 0, 0, 0, 1, 1, 1, 1, 1, 1},
	{1, 0, 1, 0, 1, 1, 0, 0, 0, 1},
	{1, 0, 1, 0, 0, 0, 0, 1, 3, 1},
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
	int mark[M+2][N+2]={0};
	int next_i, next_j;
	int i, j, dir;
	int start;

	element item = {1, 1, 1};
	push(stack, item);

	printMaze(maze);

	printf("Press any key to start: ");
	scanf("%d", &start);

	while(!isEmpty(stack)) {
		item = pop(stack);
		i = item.i;
		j = item.j;
		dir = item.dir;
		while(dir <= 3) {
			next_i = i + move[dir][0];
			next_j = j + move[dir][1];
			if(next_i == M && next_j == N) {
printMaze(maze);
				printf("\nThe path in stack is as follows.\n\n");
				printPath();
				printf("i = %d, j = %d\n", next_i, next_j);
				printf("m = %d, n = %d\n", M, N);
				printf("\nThe mark is as follows.\n");
				printMaze(mark);
				return;
			}
			if (maze[next_i][next_j] == 0 && mark[next_i][next_j] == 0) {
				mark[next_i][next_j] = 1;
				item.i = next_i;
				item.j = next_j;
				item.dir = dir;
				push(stack, item);
				i = next_i;
				j = next_j;
				dir = 0;
			}
			else dir++;

			printCurrent(maze);
			Sleep(300);
			system("cls");
		}
	}
	printf("There is no path\n");
}

void printPath() {
	int path[M+2][N+2] = {0};
	int i, j;

	for(i=17; i>top; i--) printf("|       |\n");  //i = M*N (최대)
	for(i=top; i>=0; i--) {
		path[stack[i].i][stack[i].j] = 1;
		printf("|%d, %d, %d|\n", stack[i].i, stack[i].j, stack[i].dir);
	}
	printf("i, j, dir\n");
	printf("----------------\n");

	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(path[i][j] == 0) printf("  ");
			else printf("●");
		}
		printf("\n");
	}
	printf("\n\n");
}

void printCurrent(int m[M+2][N+2]) {
	int i, j;
	
	current.i = stack[top].i;
	current.j = stack[top].j;

	printf("\n\n");
for(i=17; i>top; i--) printf("|       |\n");  //i = M*N (최대)
	for(i=top; i>=0; i--) printf("|%d, %d, %d|\n", stack[i].i, stack[i].j, stack[i].dir);
	printf("i, j, dir\n");
	printf("----------------\n");
	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(i == current.i && j == current.j) printf("○");
			else if(m[i][j] == 3) printf("☆");
			else if(m[i][j] == 2) printf("  ");
			else if(m[i][j] == 1) printf("▩");
			else printf("  ");
		}
		printf("\n");
	}
	printf("\n\n");
}

미로 7x6

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

#define M 7
#define N 6
#define STACK_SIZE M*N

int move[4][2] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};

typedef struct {
	int i;
	int j;
	int dir;
}element;

element stack[STACK_SIZE];
int top = -1;
element current = {1, 1};

void push(element *stack, element item) {
	if(top >= STACK_SIZE - 1) {
		printf("Stack is full\n");
		return;
	}
	stack[++top] = item;
}

element pop(element *stack) {
	if(top == -1) {
		printf("Stack is empty\n");
		exit(1);
	}
	else return stack[top--];
}

int isEmpty(element *stack) {
	if(top == -1) return 1;
	else return 0;
}

void printMaze(int m[M+2][N+2]);
void mazePath();
void printPath();
void printCurrent(int m[M+2][N+2]);

void main() {
	int end;
	mazePath();

	fflush(stdin);
	printf("Press any key to exit\n");
	scanf("%d", &end);

}

void printMaze(int m[M+2][N+2]) {
	int i, j;

	printf("\n\n");
	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(m[i][j] == 0) printf("  ");
			else if(m[i][j] == 2) printf("○");
			else if(m[i][j] == 3) printf("☆");
			else printf("▩");
		}
		printf("\n");
	}
	printf("\n\n");
}

void mazePath() {
	int maze[M+2][N+2] = {
	{1, 1, 1, 1, 1, 1, 1, 1},
	{1, 2, 1, 1, 0, 1, 0, 1},
	{1, 0, 0, 1, 0, 0, 0, 1},
	{1, 1, 0, 0, 0, 1, 1, 1},
	{1, 1, 1, 0, 0, 0, 1, 1},
	{1, 0, 0, 0, 1, 1, 1, 1},
	{1, 1, 0, 1, 0, 0, 0, 1},
	{1, 0, 0, 0, 0, 1, 3, 1},
	{1, 1, 1, 1, 1, 1, 1, 1}
};
	int mark[M+2][N+2]={0};
	int next_i, next_j;
	int i, j, dir;
	int start;

	element item = {1, 1, 1};
	push(stack, item);

	printMaze(maze);

	printf("Press any key to start: ");
	scanf("%d", &start);

	while(!isEmpty(stack)) {
		item = pop(stack);
		i = item.i;
		j = item.j;
		dir = item.dir;
		while(dir <= 3) {
			next_i = i + move[dir][0];
			next_j = j + move[dir][1];
			if(next_i == M && next_j == N) {
printMaze(maze);
				printf("\nThe path in stack is as follows.\n\n");
				printPath();
				printf("i = %d, j = %d\n", next_i, next_j);
				printf("m = %d, n = %d\n", M, N);
				printf("\nThe mark is as follows.\n");
				printMaze(mark);
				return;
			}
			if (maze[next_i][next_j] == 0 && mark[next_i][next_j] == 0) {
				mark[next_i][next_j] = 1;
				item.i = next_i;
				item.j = next_j;
				item.dir = dir;
				push(stack, item);
				i = next_i;
				j = next_j;
				dir = 0;
			}
			else dir++;

			printCurrent(maze);
			Sleep(300);
			system("cls");
		}
	}
	printf("There is no path\n");
}

void printPath() {
	int path[M+2][N+2] = {0};
	int i, j;

	for(i=14; i>top; i--) printf("|       |\n");  //i = M*N
	for(i=top; i>=0; i--) {
		path[stack[i].i][stack[i].j] = 1;
		printf("|%d, %d, %d|\n", stack[i].i, stack[i].j, stack[i].dir);
	}
	printf("i, j, dir\n");
	printf("----------------\n");

	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(path[i][j] == 0) printf("  ");
			else printf("●");
		}
		printf("\n");
	}
	printf("\n\n");
}

void printCurrent(int m[M+2][N+2]) {
	int i, j;
	
	current.i = stack[top].i;
	current.j = stack[top].j;

	printf("\n\n");
for(i=14; i>top; i--) printf("|       |\n");  //i = M*N
	for(i=top; i>=0; i--) printf("|%d, %d, %d|\n", stack[i].i, stack[i].j, stack[i].dir);
	printf("i, j, dir\n");
	printf("----------------\n");
	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(i == current.i && j == current.j) printf("○");
			else if(m[i][j] == 3) printf("☆");
			else if(m[i][j] == 2) printf("  ");
			else if(m[i][j] == 1) printf("▩");
			else printf("  ");
		}
		printf("\n");
	}
	printf("\n\n");
}

미로 9x8

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

#define M 9
#define N 8
#define STACK_SIZE M*N

int move[4][2] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};

typedef struct {
	int i;
	int j;
	int dir;
}element;

element stack[STACK_SIZE];
int top = -1;
element current = {1, 1};

void push(element *stack, element item) {
	if(top >= STACK_SIZE - 1) {
		printf("Stack is full\n");
		return;
	}
	stack[++top] = item;
}

element pop(element *stack) {
	if(top == -1) {
		printf("Stack is empty\n");
		exit(1);
	}
	else return stack[top--];
}

int isEmpty(element *stack) {
	if(top == -1) return 1;
	else return 0;
}

void printMaze(int m[M+2][N+2]);
void mazePath();
void printPath();
void printCurrent(int m[M+2][N+2]);

void main() {
	int end;
	mazePath();

	fflush(stdin);
	printf("Press any key to exit\n");
	scanf("%d", &end);
}

void printMaze(int m[M+2][N+2]) {
	int i, j;

	printf("\n\n");
	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(m[i][j] == 0) printf("  ");
			else if(m[i][j] == 2) printf("○");
			else if(m[i][j] == 3) printf("☆");
			else printf("▩");
		}
		printf("\n");
	}
	printf("\n\n");
}

void mazePath() {
	int maze[M+2][N+2] = {
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
	{1, 2, 1, 1, 0, 1, 0, 1, 1, 1},
	{1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
	{1, 1, 0, 0, 0, 1, 0, 0, 0, 1},
	{1, 1, 1, 0, 0, 0, 1, 0, 1, 1},
	{1, 0, 0, 0, 1, 0, 1, 0, 1, 1},
	{1, 1, 0, 1, 0, 0, 0, 1, 1, 1},
	{1, 0, 0, 0, 1, 1, 1, 1, 1, 1},
	{1, 0, 1, 0, 1, 1, 0, 0, 0, 1},
	{1, 0, 1, 0, 0, 0, 0, 1, 3, 1},
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
	int mark[M+2][N+2]={0};
	int next_i, next_j;
	int i, j, dir;
	int start;

	element item = {1, 1, 1};
	push(stack, item);

	printMaze(maze);

	printf("Press any key to start: ");
	scanf("%d", &start);

	while(!isEmpty(stack)) {
		item = pop(stack);
		i = item.i;
		j = item.j;
		dir = item.dir;
		while(dir <= 3) {
			next_i = i + move[dir][0];
			next_j = j + move[dir][1];
			if(next_i == M && next_j == N) {
				printMaze(maze);
				printf("\nThe path in stack is as follows.\n\n");
				printPath();
				printf("i = %d, j = %d\n", next_i, next_j);
				printf("m = %d, n = %d\n", M, N);
				printf("\nThe mark is as follows.\n");
				printMaze(mark);
				return;
			}
			if (maze[next_i][next_j] == 0 && mark[next_i][next_j] == 0) {
				mark[next_i][next_j] = 1;
				item.i = next_i;
				item.j = next_j;
				item.dir = dir;
				push(stack, item);
				i = next_i;
				j = next_j;
				dir = 0;
			}
			else dir++;

			printCurrent(maze);
			Sleep(300);
			system("cls");
		}
	}
	printf("There is no path\n");
}

void printPath() {
	int path[M+2][N+2] = {0};
	int i, j;

	for(i=17; i>top; i--) printf("|       |\n");  //i = M*N (최대)
	for(i=top; i>=0; i--) {
		path[stack[i].i][stack[i].j] = 1;
		printf("|%d, %d, %d|\n", stack[i].i, stack[i].j, stack[i].dir);
	}
	printf("i, j, dir\n");
	printf("----------------\n");

	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(path[i][j] == 0) printf("  ");
			else printf("●");
		}
		printf("\n");
	}
	printf("\n\n");
}

void printCurrent(int m[M+2][N+2]) {
	int i, j;
	
	current.i = stack[top].i;
	current.j = stack[top].j;

	printf("\n\n");
	for(i=17; i>top; i--) printf("|       |\n");  //i = M*N (최대)
	for(i=top; i>=0; i--) printf("|%d, %d, %d|\n", stack[i].i, stack[i].j, stack[i].dir);
	printf("i, j, dir\n");
	printf("----------------\n");
	for(i=0; i<M+2; i++) {
		for(j=0; j<N+2; j++) {
			if(i == current.i && j == current.j) printf("○");
			else if(m[i][j] == 3) printf("☆");
			else if(m[i][j] == 2) printf("  ");
			else if(m[i][j] == 1) printf("▩");
			else printf("  ");
		}
		printf("\n");
	}
	printf("\n\n");
}

#include <iostream>
#include <string.h>
#include <windows.h>

using namespace std;

#define MAX_STACK_SIZE 100
#define MAZE_SIZE 9

typedef struct  StackObjectRec { 
 short r;
 short c;
} StackObject;

StackObject  stack[MAX_STACK_SIZE]; 
int  top = -1; 
StackObject here={0,0}, entry={0,0};

char maze[MAZE_SIZE][MAZE_SIZE] = {
 { '1', '1', '1', '1', '1', '1', '1', '1', '1' }, 
 { 'e', '0', '1', '1', '0', '1', '1', '1', '1' },
 { '1', '0', '0', '1', '0', '1', '1', '1', '1' },
 { '1', '1', '0', '0', '0', '1', '1', '1', '1' },
 { '1', '1', '1', '0', '0', '0', '1', '1', '1' },
 { '1', '0', '0', '0', '1', '1', '1', '1', '1' },
 { '1', '1', '0', '1', '0', '0', '0', '1', '1' },
 { '1', '0', '0', '0', '0', '1', '0', '0', 'x' },
 { '1', '1', '1', '1', '1', '1', '1', '1', '1' },
 };


void initialize()
{
 top = -1;
}

int isEmpty()
{
 return (top == -1);
}

int isFull()
{
 return (top == (MAX_STACK_SIZE-1));
}

void push(StackObject item)
{ 
     if( isFull() ) { 
    cout<<"stack is full\n";
   } 
   else stack[++top] = item; 
}

StackObject pop() 
{ 
    if( isEmpty() ) {
  cout<<"stack is empty\n";
  exit(1);
 }
 else return stack[top--]; 
} 

void printStack()
{
 int i;
 for(i=5;i>top;i--)
  cout<<"|     |\n";
 for(i=top;i>=0;i--)
  cout<< "|(" <<stack[i].r<< ","<<stack[i].c<<")|\n";
 cout<<"-------\n";
}

void pushLoc(int r, int c)
{
 if( r < 0 || c < 0 ) return;
 if( maze[r][c] != '1' && maze[r][c] != '.' ){
  StackObject tmp;
  tmp.r = r;
  tmp.c = c;
  push(tmp);
 }
}

void printMaze(char m[MAZE_SIZE][MAZE_SIZE])
{
 int r,c;
 cout<<"\n\n";
 for(r=0;r<MAZE_SIZE;r++){
  for(c=0;c<MAZE_SIZE;c++){
   if( c == here.c && r == here.r )
    cout<<"●";
   else {
    if( m[r][c] == '.' ) cout<<"  ";
    else {
     if( m[r][c] == '1' ) cout<<"▧";
     else cout<<"  ";
    }

   }
  }
  cout<<endl;;
 }
 cout<<"\n\n";
}

void main()
{
 int r,c;
 here = entry;
 printMaze(maze);
 printStack();

 cout<<"Press any key !! ";
 fflush(stdin);
 getchar();
 system("cls");

 while ( maze[here.r][here.c]!='x' ){
  printMaze(maze);
  r = here.r;
  c = here.c;
  maze[r][c] = '.';
  pushLoc(r-1,c);
  pushLoc(r+1,c);
  pushLoc(r,c-1);
  pushLoc(r,c+1);
  printStack();

  Sleep(300);
  system("cls");

  if( isEmpty() ){
   cout<<"실패\n";
   return;
  }
  else 
   here = pop();
//  printMaze(maze);
//  printStack();
 }
 printMaze(maze);
 cout<<"성공\n";
}

저작자표시

'메모 > 자료구조' 카테고리의 다른 글

C 연결리스트 연산 (0)	2012.03.31
다항식의 자료구조 (0)	2012.03.31
Big-oh(O) 빅오 표기법, 시간 복잡도 (0)	2012.03.31

And

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

그레이트박

Article Category

Notice

Recent Article

C 미로찾기

'메모 > 자료구조' 카테고리의 다른 글

Tag Cloud

Calendar

Archive

My Link

티스토리툴바