連接三難題解決

Question

我正在寫一個休閒連接三類型的遊戲，使用正方形網格。玩家沿着一行或一列滑動（基本上以1D旋轉），將至少三個相同類型的塊放在一起以便進行匹配。

因爲隨着比賽的推移難度會增加，隨之而來的一個點（我已經檢查，這是可能的）的存在是沒有動作，這將導致新的比賽。

除了使用蠻力的方法（其爲至少O（N^2）時間），是否有尋找可能的移動更快的方法？

Answer 1

你可以做到這一點在O（N日誌（M））其中ñ是在董事會和中號位置的數量是形狀可供數量：

1. Ø （N日誌（M））：對於每一個點（O（N）），更新地圖上爲它的行和列（O（日誌（M））的可用形狀
   
2. 。對於每個點（O（N）），檢查垂直，水平或對角相鄰或相隔一個空間的相似形狀（O（1）），並檢查行/列圖（S）（O（日誌（M））），將「連三」，看是否有有效的舉措是可用的。

您還可以改進上述方法，以免它不必要地重複檢查（第二行及以下的形狀不檢查，第二列和右側的形狀不檢查左側） ，但大的成本將是相同的。

此外，在每個移動你只需要更新已更改的行/列的地圖，你只需要檢查已經改變了形狀。最壞的情況是，整個板被清除，因此這種改進的大Ø成本將是一樣的好。