c++ - 为回文遍历网格

Question

我一直在努力解决这个问题，但除了一个天真的解决方案之外，我什么都想不出。基本上，我得到了一个大小为 N 的字符网格，其中我必须找到从左上角到右上角的不同路径的数量，当只向下和向右移动时给出一个回文。

这是一个网格的例子:

ABCD

BXZX

CDXB

中国职业篮球联赛

这个格子里有“ABXZXBA”等12个回文。我的解决方案是遍历网格中的所有路径，并通过为前 N 个字符保留一个字符堆栈并为接下来的 N 个字符弹出每个字符并检查它们是否相同来检查该字符串是否为回文。当 N 变得太大并且我不确定如何继续时，此解决方案会超时。任何伪代码或建议将不胜感激。

Answer 1

只是一个理论 - 我还没有尝试编写代码:

您可以从左上角和右下角开始，并保持路径同步。由于它是一个回文，因此从底部到顶部的路径中需要有相同的字母。

每次寻找路径中的下一步时，检查反向步骤中是否有匹配的字母。

可以进一步限制反向步骤的可用路径，因为它不能到达向前步骤的左侧或上方。

当路径相遇时停止，这很复杂，因为它们可能最终位于相同的网格位置(奇数行)，或者它们可能刚好相遇(偶数行)。

反向跟踪和堆栈保持可能有点复杂，因为您必须(可能)考虑反向步骤的多种选择，但它应该减少可能性的数量。最好将其视为正向和反向路径中的每一步都会为您提供一个新的(更小的)网格来检查回文。