如何在二维矩阵中寻找满足多约束的必经指定单元格路径

给定一个二维矩阵，包含以下类型的单元格：

• S：起点
• E：终点
• M：必须访问的单元格
• X：不可访问的单元格
• 0：可访问的普通单元格

需要寻找一条满足以下全部条件的路径：

• 从起点S出发
• 最终到达终点E
• 经过所有标记为M的单元格
• 不经过任何X单元格
• 路径中无重复经过的单元格
• 仅允许上下左右四个方向的移动

矩阵最大尺寸为10×10，以下是一个示例：

示例矩阵 #

S 0 0 M 0
0 0 0 X 0
0 M 0 0 0
0 X 0 0 0
0 0 0 0 E

其中一个可行路径（*表示路径经过的单元格） #

* 0 * * *
* 0 * X *
* * * 0 *
0 X 0 0 *
0 0 0 0 *

路径不要求为最短路径，但优先选择较短路径且计算效率较高的方案。

内容的提问来源于stack exchange，提问作者Amy