学步园

因为周六举行月赛，写几个经典的BFS DFS
供大家参考，代码是以前写的不是很简洁，有不懂的可留言。

注：写搜索时一定要记得访问标记，以免访问过的点再次访问，出现死循环等情况。

1、走不出的迷宫：http://acm.nuc.edu.cn/OJ/problem.php?pid=1010

数据范围比较小，可以用递归，代码简洁些；

#include "stdio.h"
#define M 82
int dx[] = {0,1,0,-1}; //方向数组
int dy[] = {1,0,-1,0};
int DFS (int x,int y);
int n;
char map[M][M];
int DFS (int x,int y)
{
    int
i,X,Y,flag;
    if (x ==
n&& y== n)//找到出口，返回1
    {
       
map[x][y] = '#'; //标记路径
       
return 1;
    }
    if
(map[x][y] == '1')
       
return 0;
    map[x][y] =
'*';//访问标记 以免重复访问
    flag =
0;
    for (i = 0;
i < 4; i ++)
    {
       
X = x + dx[i];//查找四个方向
       
Y = y + dy[i];
       
if (map[X][Y] == '1'||map[X][Y] == '*') //该点不可走，或已访问过
           
continue;
       
else if (DFS(X,Y) == 1) flag = 1;
    }
    if (flag ==
0)  //回退输出路径
       
map[x][y] = '0';
    else
       
map[x][y] = '#';
    return
flag;
}

int main ()
{
    int
i,j,x,y;
    scanf ("%d
%d %d",&n,&y,&x);
    for (i = 1;
i <= n; i ++)
       
for (j = 1; j <= n; j ++)
       
{
           
getchar ();
           
scanf ("%c",&map[i][j]);
       
}

    for (i = 0;
i <=n+1; i ++) //给图加个框，就不必再判断点是否出界
       
for (j = 0; j<=n+1; j ++)
           
if (j == 0||i==0||j==n+1||i==n+1)
               
map[i][j] = '1';
    if (DFS(x,y)
== 1)
    {
       
printf ("Found\n");
       
for (i = 1; i <= n; i ++)
       
{
           
for (j =1; j <= n; j++)