maze.c

迷宫的又一解法。该算法简单、实用、可读性强

#include "stdafx.h"
#define  MAX_SIZE 8

int H[4] = {0, 1, 0, -1};						//水平方向下一位置相对当前位置的距离
int V[4] = {-1, 0, 1, 0};						//垂直方向下一位置相对当前位置的距离
char Maze[MAX_SIZE][MAX_SIZE] =					//迷宫（可以不是方阵）
{
	{'X','X','X','X','X','X','X','X'},
	{'O','O','O','O','O','X','X','X'},
	{'X','O','X','X','O','O','X','X'},
	{'X','O','X','X','O','X','O','O'},
	{'X','O','X','X','X','X','O','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','O','O','O','X','O','X'},
	{'X','X','X','X','X','X','X','X'}
};

void FindPath(int X, int Y)	
{
	if(X==MAX_SIZE-1 || Y==MAX_SIZE-1){			//到达出口，输出被标记通路的迷宫
		Maze[X][Y] = ' ';
		for(int i=0; i<MAX_SIZE; i++)
			for(int j=0; j<MAX_SIZE; j++)
				printf("%c%c", Maze[i][j], j<MAX_SIZE-1?' ':'\n');
	}else{
		for(int k=0; k<4; k++)					//未到出口时，分别从四个方向寻找
			if(Maze[X+V[k]][Y+H[k]] == 'O'){	//下一个通路，如果某个方向是通路，
				Maze[X][Y] = ' ';				//则标记当前位置为通，然后到下一
				FindPath(X+V[k], Y+H[k]);		//个位置继续寻找出路。(未严格检验
				Maze[X][Y] = 'O';				//边界)。找到出口或此路不通时回溯
			}
	}
}

int main(int argc, char* argv[])
{
	FindPath(1,0);
	return (int)getchar();
}