我有一个非常棘手的任务要解决：
给你一个 N * M 板（1 <= N，M <= 256）。您可以从每个字段移动到其相邻字段（不允许沿对角线移动）。一开始，有两种类型的字段：活动和阻塞。您可以通过活动场，但不能继续被阻止的场。您有 Q 个查询（1 <= Q <= 200）。有两种类型的查询：
1) 找到位于从字段 A 到 B 的最短路径上的下一个字段（与 A 相邻）
2) 将字段 A 从活动更改为阻塞或相反。
第一种查询可以用简单的 BFS 在 O(N * M) 时间内轻松解决。我们可以将活动字段和阻塞字段表示为 0 或 1，因此第二个查询可以在恒定时间内完成。
该算法的总时间为 O(Q (查询次数) * N * M)。
所以有什么问题？我有 1/60 秒的时间来解决所有的问题。如果我们将 1 秒视为 10^8 次计算，则剩下大约 1,5 * 10^6 次计算。一个 BFS 最多可能需要 N * M * 4 次，大约是 2,5 * 10^5。因此，如果 Q 为 200，则所需的计算可能高达 5 * 10^7，这太慢了。
据我所知，在这种情况下，没有比 BFS 更好的寻路算法（好吧，我可以选择 A*，但我不确定它是否比 BFS 快得多，它仍然是最坏情况 O(|E |) - 根据维基百科)。所以在这方面没有太多需要优化的地方。但是，我可以以某种方式更改我的图表以减少算法必须处理的边数（我不需要知道完整的最短路径，只知道我应该采取的下一步行动，所以剩下的最短路径可以非常简化）。我正在考虑一些预处理 - 将顶点分组并制作图形图，但我不确定如何以这种方式处理阻塞的字段。
我怎样才能更好地优化它？或者甚至有可能吗？
编辑：实际问题：我在板上有一些单元。我想开始将它们移动到选定的目的地。单位不能共享同一个领域，因此可以阻止其他人的路径或为他们开辟一条新的、更好的路径。可能有很多单位，这就是为什么我需要更好的优化。