maze.c

迷宫算法,找出较优的路径,找到出口.算法效率比较高

/*
*  Name:    $RCSfile$
*
*  Version: $Revision$
*
*  Created by: chensd
*
*  Purpose: This is a C language practice program
*
*  UNICATION CO. LTD. PROPRIETARY INFORMATION
*
*  SECURITY LEVEL - HIGHLY CONFIDENTIAL
*
*  DO NOT COPY
*
*  This document and the information contained in it is confidential and
*  proprietary to Unication Co., Ltd. The reproduction or disclosure in
*  whole or in part, to anyone outside of Unication Co., Ltd. without the
*  written approval of the President of Unication Co., Ltd., under a
*  Non-Disclosure Agreement, or to any employee of Unication Co. Ltd. who
*  has not previously obtained written authorization for access from the
*  individual responsible for the document, will have a significant
*  detrimental effect on Unication Co., Ltd. and is expressly prohibited.
*
*  Copyright (c) $Date$ Unication Co., Ltd.
*
*  All rights reserved
*/

#include <stdio.h>
#include <memory.h>

typedef struct{
	int x;
	int y;
}Position;

Position pos[1000];

char mazeProcess[12][12];
char maze[12][12] = {
	'1','1','1','1','1','1','1','1','1','1','1','1',
	'1','0','0','0','1','0','0','0','0','0','0','1',
	'0','0','1','0','1','0','1','1','1','1','0','1',
	'1','1','1','0','1','0','0','0','0','1','0','1',
	'1','0','0','0','0','1','1','1','0','1','0','0',
	'1','1','1','1','0','1','0','1','0','1','0','1',
	'1','0','0','1','0','1','0','1','0','1','0','1',
	'1','1','0','1','0','1','0','1','0','1','0','1',
	'1','0','0','0','0','0','0','0','0','1','0','1',
	'1','1','1','1','1','1','0','1','1','1','0','1',
	'1','0','0','0','0','0','0','1','0','0','0','1',
	'1','1','1','1','1','1','1','1','1','1','1','1'};


/*
*  Name:       mazeTraverse
*
*  Purpose:    find the maze solution
*
*  Params:     "current" is the position of current
*              "step" is the number of current path
*
*  Return:     1 - have solution
*              0 - can not find
*
*  Note:       none
*
*/
int mazeTraverse(Position current, int step)
{
	int i,j,k;
	Position p;
    pos[step] = current;

	/*can find the solution*/
    if(current.x == 4 && current.y == 11){
		for(k=0;k<=step;k++){
			printf("the step %d position is:\n", k);

			/*print the process of maze*/
			mazeProcess[pos[k].x][pos[k].y] = 'X';
			for(i=0; i<12; i++) {
				for(j=0; j<12; j++) {
					printf("%c  ", mazeProcess[i][j]);
				}
				printf("\n");
			}
		}
		printf("we find the path!\n");
		
		return 1;
    } 

	/*the position has been found*/
	maze[current.x][current.y] = '1';

	/*recursive process*/
	if(maze[current.x+1][current.y] == '0'){
		p.x = current.x+1;
		p.y = current.y;
		if(mazeTraverse(p, step+1)) {
			return 1;
		}
	}
	
	if(maze[current.x][current.y+1] == '0') {
		p.x = current.x;
		p.y = current.y+1;
		if(mazeTraverse(p, step+1)){
			return 1;
		}
	}

	if(maze[current.x][current.y-1] == '0') {
		p.x = current.x;
		p.y = current.y-1;
		if(mazeTraverse(p, step+1)){
			return 1;
		}
	}

	if(maze[current.x-1][current.y] == '0') {
		p.x = current.x-1;
		p.y = current.y;
		if(mazeTraverse(p, step+1)){
			return 1;
		}
	}
	
	return 0;
}

/*
*  Name:       main
*
*  Purpose:    program entry
*
*  Params:     refer to the usage
*
*  Return:     >0 - succeed
*              -1 - met error
*
*  Note:       none
*
*/
int main(int argc, char **argv)
{ 
	Position first;
	first.x = 2;
	first.y = 0;
	memcpy(mazeProcess, maze, 12*12);
	if(!mazeTraverse(first, 0)){
		printf("can not find the path!\n");
	}
}