秒懂算法 | 回溯算法

例题：已知一个迷宫以及迷宫的入口和出口，现在从迷宫的入口出发，看是否存在一条路径？如果存在，则输出YES，不存在，输出NO。

解析：计算机走迷宫时，利用“试探和回溯”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。

下图为例，介绍一下迷宫的具体走法。下图中灰色部分墙体部分：

1）从入口进入迷宫之后，理论上有前后上下四个方向可以走，这里以前、下、后、上四个方向为顺序进行迷宫的道路搜索。如果有路，则向前，无路则按顺序向下一个方向进行搜索。图a是顺着向前方向一直搜索，当向前方向不通时，则向下如图b搜索，还不通，则向后搜索，后面已经搜索过了（需要一个标志位，搜索过的标志为不通），则继续向上搜索如图d所示，发现仍然不通（这里需要对边界进行判断，对于超过边界的区域认为不通）。

总结：迷宫中一共有三种类型的路不通

• 前方道路是墙体

已经访问过的路径
超出迷宫边界
（2）此时，搜索位置的四个方向都走不通，就需要退回到前一个位置，这叫回溯。当回到上一个位置后，由于原来是向前搜索的，结果不通，则此时需要换一个方向搜索，现在向下搜索,此时是通路。在下一个位置上，继续按照前、下、后、上顺序继续搜索，如图e所示。

（3）在图e的搜索位置上，向前不通，转向向下搜索，有路可通，则下移一格，如图f所示。

（4）继续向前搜索，有通路，如图g所示。

（5）发现向前搜索，无路，转向向下搜索，下移一格，到达出口。如图h所示。

对于迷宫的数据表示方法，一般都是采用二维数组表示。至于数据类型，可以采用整型或者字符型表示，本题为了方便，采用了字符型。

string map[5]={"0000#",
             "0#0##",
         "#00##",
         "#0#00",
         "#0000"};

二维数组中，字符'0'表示通路，'#'表示墙体。

在迷宫中，相对中心点，向四个方向搜索的数据表示可以用图1表示。

这里利用两个数组dx和dy分别表示数据偏移量。

int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};

对这两个数组的顺序访问，就相当于分别向前、下、后、上进行搜索。

int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
对这两个数组的顺序访问，就相当于分别向前、下、后、上进行搜索。
int x,y,x1,y1,nx,ny,n;
bool visited[100][100],flag=false;
int dfs(int x, int y)
{
  if(x==x1 && y==y1)//到达
  {
    cout<<"YES"<<endl;
    flag=true;
    return 1;
  }
  for(int i=0;i<4;++i)
  {
    nx=x+dx[i];//搜索四个方向
    ny=y+dy[i];
    if(nx<0 || nx>=n || ny<0 || ny>=n)//判断是否越界以及是否走过
      continue;
    if(!visited[nx][ny])
    {
      visited[nx][ny]=true;//走过
      dfs(nx,ny);//否则从现在的点开始继续往下搜索
      visited[nx][ny]=false;//重新标记未走过
    }
  }
  return 0;
}