递归版与非递归版

								#define DeBUG
#include <iostream>
using namespace std ;
#define zero {0}
int dir[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
int mp[100][100];
char road[100][100];
int visit[100][100];
int n,m;
bool dfs(int x,int y)
{
	int nowx;
	int nowy;
	int flag=0;
//	printf("*******************\n");
//	for(int l=0; l<n; l++)
//	{
//		for(int h=0; h<m; h++)
//		{
//			printf("%c ",road[l][h]);
//		}
//		printf("\n");
//	}
	for(int i=0; i<4; i++)
	{
		nowx=x+dir[i][0];
		nowy=y+dir[i][1];
		if(nowx<0||nowy<0||nowx>=n||nowy>=m)
			continue;
		if(visit[nowx][nowy]||mp[nowx][nowy]==1)
			{
					/*if(road[nowx][nowy]=='*')全面搜索
					{
						flag=1;
						road[x][y]='*';
					}
					*/
				continue;
			}
		if(nowx==n-1&&nowy==m-1)
		{
			flag=1;
			road[x][y]='*';
			
			dfs(nowx,nowy);//全面搜索 
			continue;
			//return true;//单路搜索 
		}
		visit[nowx][nowy]=1;
		road[nowx][nowy]='@';
		if(dfs(nowx,nowy)==true)
		{
			flag=1;
			road[x][y]='*';
		}
	}
	if(flag)
		return true;
	return false;
}
int main()
{
#ifdef DeBUG
	freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin);
//	freopen("C:\\Users\\Sky\\Desktop\\打表.txt","w",stdout);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!
#endif
	while(scanf("%d%d",&n,&m)+1)
	{
		int i,j,k;
		memset(mp,sizeof(mp));
		memset(visit,sizeof(visit));
		memset(road,sizeof(road));
		for(i=0; i<n; i++)
		{
			for(j=0; j<m; j++)
			{
				scanf("%d",&mp[i][j]);
				if(mp[i][j]==1)
					road[i][j]='#';
			}
		}
		visit[0][0]=1;
		road[0][0]='*';
		road[n-1][m-1]='*';
		dfs(0,0);
		for(int l=0; l<n; l++)
		{
			for(int h=0; h<m; h++)
			{
				printf("%c ",road[l][h]);
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}
/*
9 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
3 3
0 0 0
0 1 1
0 0 0
4 4
0 0 0 0
0 1 0 0
1 1 0 1
0 0 0 0
5 5
0 0 0 1 0
0 1 0 1 0
0 1 1 0 0
0 0 0 0 1
0 1 1 0 0
7 7
0 0 0 0 0 0 0
0 0 0 0 1 1 1
1 1 1 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 1 0
1 1 1 0 0 1 0
0 0 0 0 0 0 0

result
* * # @ @ @ #   
@ * # @ @ @ #   
* * @ @ # #   # 
* # # # @ @ # @ 
* * * # * * * @ 
@ # * * * # * # 
@ # # # # @ * # 
# # @ @ @ # * # 
# # @ @ @ @ * * 

* @ @ 
* # # 
* * * 

* * * * 
@ # * * 
# # * # 
@ @ * * 

* @ @ # @ 
* # @ # @ 
* # # @ @ 
* * * * # 
@ # # * * 

* * * * @ @ @ 
@ @ @ * # # # 
# # # * * @ @ 
@ @ @ @ * # # 
@ @ @ @ * # @ 
# # # @ * # * 
@ @ @ @ * * * 

*/

非递归

#define DeBUG
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std ;
struct Node
{
	int deep;
	int x;
	int y;
	int i;
	bool flag;
	Node() {}
	Node(int a,int b,int c,int d,bool e)
	{
		deep=a;
		x=b;
		y=c;
		i=d;
		flag=e;
	}
};
struct Stack
{
	Node data;
	Stack *next;
};
Node Front(Stack *S)
{
	Stack *p=S;
	while(p->next!=NULL)
	{
		p=p->next;
	}
	return p->data;
}
bool Empty(Stack *S)
{
	if(S->next==NULL)
	{
		return true;
	}
	return false;
}
bool Push(Stack *S,Node a)
{
	Stack *p=S;
	while(p->next!=NULL)
	{
		p=p->next;
	}
	p->next=(Stack *)malloc(sizeof(Stack));
	p->next->data=a;
	p->next->next=NULL;
	return true;
}
bool Pop(Stack *S)
{
	Stack *p=S;
	Stack *pre=p;
	while(p->next!=NULL)
	{
		pre=p;
		p=p->next;
	}
	if(p)
		free(p);
	pre->next=NULL;
	return true;
}


#define zero {0}
int dir[4][2]= {{0,int y)
{
	Stack *S; //建栈
	Stack head;//建栈
	S=&head;//建栈
	S->next=NULL;//建栈
	int nowx;
	int nowy;
	bool flag1=0;
	Node start(0,x,y,false);
	Push(S,start);
	while(!Empty(S))
	{
		Node now=Front(S);
		Pop(S);
		x=now.x;
		y=now.y;
		if(now.flag==true)
		{
			road[x][y]='*';
		}
		for(int i=0; i<4; i++)
		{
			nowx=x+dir[i][0];
			nowy=y+dir[i][1];
			if(nowx<0||nowy<0||nowx>=n||nowy>=m)
				continue;
			if(visit[nowx][nowy]||mp[nowx][nowy]==1)
				continue;
			if(i<4)
			{
				now.i=i;
				Push(S,now);
			}
			if(nowx==n-1&&nowy==m-1)
			{
				road[x][y]='*';
				/*
								visit[nowx][nowy]=1;
								Node it(now.deep+1,nowx,nowy,i,true);//全面搜索
								Push(S,it);
								break;*/
				while(!Empty(S))
				{
					Node itt=Front(S);
					Pop(S);
					road[itt.x][itt.y]='*';
				}
				return true;//单路搜索
			}
			visit[nowx][nowy]=1;
			road[nowx][nowy]='@';
			Node it(now.deep+1,false);
			Push(S,it);
			break;
		}
	}
	if(flag1)
		return true;
	return false;
}
int main()
{
#ifdef DeBUG
	freopen("C:\\Users\\Sky\\Desktop\\1.in",stdin);
#endif
	while(scanf("%d%d",j;
		memset(mp,road[l][h]);
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

								#define DeBUG
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
using namespace std ;
void SetColor(unsigned short ForeColor=3,unsigned short BackGroundColor=0)
{
    HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hCon,ForeColor|BackGroundColor);
}
int color[100][100][2];
struct Node
{
	int deep;
	int x;
	int y;
	int i;
	bool flag;
	Node() {}
	Node(int a,now);
			}
			if(nowx==n-1&&nowy==m-1)
			{
				road[x][y]='*';
				while(!Empty(S))
				{
					Node itt=Front(S);
					Pop(S);
					road[itt.x][itt.y]='*';
					color[itt.x][itt.y][0]=8;
					color[itt.x][itt.y][1]=2;
				}
				return true;//单路搜索成功
			}
			visit[nowx][nowy]=1;
			road[nowx][nowy]='@';
			color[nowx][nowy][0]=3;
			color[nowx][nowy][1]==8;
			Node it(now.deep+1,it);
			break;
		}
	}
	return false;
}
int main()
{
#ifdef DeBUG
	freopen("C:\\Users\\Sky\\Desktop\\1.in",sizeof(road));
		memset(color,sizeof(color));
		for(i=0; i<n; i++)
		{
			for(j=0; j<m; j++)
			{
				scanf("%d",&mp[i][j]);
				if(mp[i][j]==1)
					road[i][j]='#';
			}
		}
		visit[0][0]=1;
		road[0][0]='*';
		road[n-1][m-1]='*';
		color[n-1][m-1][0]=12;
		color[n-1][m-1][1]=0;
		if(dfs(0,0))
		{
			printf("成功找到出口！\n");
		}
		else
		{
			printf("未找到出口！\n");
		}
			for(int l=0; l<n; l++)
			{
				for(int h=0; h<m; h++)
				{
					if(color[l][h][0])
						SetColor(color[l][h][0],color[l][h][1]);
					printf("%c ",road[l][h]);
					if(color[l][h][0])
						SetColor(5,3);
				}
				printf("\n");
			}
			printf("\n");
	}
	return 0;
}