c - 有约束条件的迷宫求解

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。




已关闭8年。




我知道解决迷宫问题是Stack Overflow上经常讨论的话题。这是一个大家可能都感兴趣的问题。

将给出n * n矩阵形式的迷宫作为输入。每个元素位于0-9之间。也将给出一个数字序列，每个数字都在0-9之间。矩阵和序列数组的维数也是已知的。问题是要找到矩阵中从(0,0)到(n-1，n-1)满足给定序列的所有可能路径。路径只能向下，向右或向下+向右移动。必须使用线程来完成。

输入和输出格式在以下示例中进行了说明-

例子:
Example1 http://gowthams.in/etc/1.PNG
Example2 http://gowthams.in/etc/2.PNG
Example3 http://gowthams.in/etc/3.PNG

每个线程可以打印其位置(i，j)或更新某种数据结构以供以后处理。

解决此问题的最佳方法是什么？

这是一个作业问题，我可以寻求帮助。我不是在寻找任何形式的代码。我只希望一些正确方向的指针。

谢谢!

最佳答案

感谢您的确切声明。

1)这句话似乎很令人不安:



因为这意味着对于矩阵NxN，您肯定需要创建N2线程，这对我来说太多了。

但是，您的解决方案甚至更危险:您要开始检查路由，并为每次检查创建一个新线程。这将创建新的指数数量的新线程，以解决该任务。您肯定需要某种优化:这称为动态优化:您是否在共享内存中存储是否可以使用(i,j)单元来完成从idx索引到目标单元格的顺序。这样，您将永远不必一次解决同一子任务。我建议您为每个此类任务[i,j,idx]创建条件锁，并使用它以便在子线程完成时告诉依赖它的线程。

2)多个路径对您来说不是问题:如果我正确地阅读了作业，您只是对这样的路径是否存在感兴趣，而不是寻找所有解决方案。

我没有提供确切的解决方案，只是根据要求提供了指示。这也正是我倾向于帮助家庭作业者的方式。