CSP-J/S第一轮认证必考知识点：回溯算法
01
回溯算法
例题：已知一个迷宫以及迷宫的入口和出口，现在从迷宫的入口出发，看是否存在一条路径？如果存在，则输出YES，不存在，输出NO。
解析：计算机走迷宫时，利用“试探和回溯”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。
下图为例，介绍一下迷宫的具体走法。下图中灰色部分墙体部分：
1）从入口进入迷宫之后，理论上有前后上下四个方向可以走，这里以前、下、后、上四个方向为顺序进行迷宫的道路搜索。如果有路，则向前，无路则按顺序向下一个方向进行搜索。图a是顺着向前方向一直搜索，当向前方向不通时，则向下如图b搜索，还不通，则向后搜索，后面已经搜索过了（需要一个标志位，搜索过的标志为不通），则继续向上搜索如图d所示，发现仍然不通（这里需要对边界进行判断，对于超过边界的区域认为不通）。
总结：迷宫中一共有三种类型的路不通
  • 前方道路是墙体
  • 已经访问过的路径
  • 超出迷宫边界
（2）此时，搜索位置的四个方向都走不通，就需要退回到前一个位置，这叫回溯。当回到上一个位置后，由于原来是向前搜索的，结果不通，则此时需要换一个方向搜索，现在向下搜索,此时是通路。在下一个位置上，继续按照前、下、后、上顺序继续搜索，如图e所示。
（3）在图e的搜索位置上，向前不通，转向向下搜索，有路可通，则下移一格，如图f所示。
（4）继续向前搜索，有通路，如图g所示。
（5）发现向前搜索，无路，转向向下搜索，下移一格，到达出口。如图h所示。
对于迷宫的数据表示方法，一般都是采用二维数组表示。至于数据类型，可以采用整型或者字符型表示，本题为了方便，采用了字符型。
stringmap
[
5
]={
"0000#"
,

"0#0##"
,

"#00##"
,

"#0#00"
,

"#0000"
};
二维数组中，字符'0'表示通路，'#'表示墙体。
在迷宫中，相对中心点，向四个方向搜索的数据表示可以用图8-3表示。
这里利用两个数组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
;

intdfs(int x, int y)
{

if
(x==x1 && y==y1)
//到达
  {

cout
<<
"YES"
<<
endl
;

    flag=
true
;

return1
;

  }

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
;
//重新标记未走过
    }

  }

return0
;

}
02
参考书籍
《CCF CSP第一轮认证一本通》
ISBN：978-7-302-58146-8
作者：丁向民
定价：79元
03
精彩推荐
继续阅读
阅读原文