迷宫及数独问题

迷宫及数独问题

迷宫问题

迷宫类题目，出题人会在程序中构造一个迷宫。该迷宫一般由各种符号构成，一些符号表示墙壁，一些

符号表示可以行走的路，并标定入口和出口。

程序依据解题者输入的字符串来走迷宫（如有的题目以 w/s/a/d 字符分别表示 向上/向下/向左/向右 行

走一格），如果该字符串满足以最短路径从入口走到出口，并且中间没有任何碰壁行为，则获得 flag。

迷宫问题有以下特点:

在内存中布置一张 “地图”（通常是一个字符串）

将用户输入限制在少数几个字符范围内

一般只有一个迷宫入口和一个迷宫出口

布置的地图可以由可显字符 (比如 # 和 * ) 组合而成 (这非常明显, 查看字符串基本就知道这是个迷宫题

了)，也可以单纯用不可显的十六进制值进行表示。可以将地图直接组成一条非常长的字符串，或是一行

一行分开布置。如果是一行一行分开布置的话，因为迷宫一般都会比较大，所以用于按行(注意, 布置并

非按顺序布置, 每行都对应一个具体的行号, 你需要确定行号才能还原迷宫地图) 布置迷宫的函数会明显

重复多次。

而被限制的字符通常会是一些方便记忆的组合， 比如 w/s/a/d , h/j/k/l , l/r/u/d 这样的类似组合.

当然各个键具体的操作需要经过分析判断。对于二维的地图， 一般作者都会设置一个 X坐标 和一个 Y

坐标 用于保存当前位置. 我们也可以根据这个特点来入手分析。

一般情况下， 迷宫是只有 1 个入口和 1 个出口 ，像入口在最左上角 (0, 0) 位置, 而出口在最右下角

(max_X, max_Y) 处。但也有可能是出口在迷宫的正中心，用一个 Y 字符表示等等。解答迷宫题的条

件也是需要根据具体情况判断的。

当然迷宫的走法可能不止 1 条 ，也有情况是有多条走法， 但是要求某一个走法比如说代价最小。那么

这就可以变相为一个算法问题（搜索算法）。