Description

---

Input

---

Output

---

Solution

一看到這題的我是懵逼的，好像有好多狀態(tài)，媽媽怎么辦？

然而仔細(xì)讀題目，轉(zhuǎn)動我們的腦子可以發(fā)現(xiàn)，由于每個棋子可以向各個方向移3格，且只會改變自身的位置，整個網(wǎng)格就被劃成了9個區(qū)域：

0 1 2
3 4 5
6 7 8

其中每個區(qū)域代表的是處于某個位置的格子能走遍的所有格子的集合。舉個栗子：第一行第一列的格子就跟第一行第四列的格子就在同一個集合里，而不跟第一行第二列的格子在一個集合。
而在這個集合里的任何格子間棋子可以相互到達(dá)。換句話說，處于這片區(qū)域的任何一個格子的棋子，都可以看作處于同一個格子。這樣，我們就用左上角的格子作為區(qū)域的代表格，我們只用記這樣3×3的一個狀態(tài)。

然后跨過棋子使其消失相當(dāng)于合并兩個棋子到第三個格子，這在“縮略圖”中，就是相鄰的格子間的操作，只需要將相應(yīng)區(qū)域的格子的棋子數(shù)量對應(yīng)加減就行了。然后我們搜索，用hash記憶化(我用的是map)，每次執(zhí)行合并操作棋子數(shù)必然減少，狀態(tài)不會太多。

由于方向的對稱性，我們可以只記4個方向，對應(yīng)要處理好邊界問題，不要出界。

---

Code

#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> #include <iostream> #include <map>using namespace std;const int dx[] = {0, 1, 1, 1}; const int dy[] = {1, -1, 0, 1};map <long long, int> M; int n, m, K; int tx, ty;int lim[3][3], val[3][3];long long Get(){long long ans = 0, t = 1;for(int i = 0; i < 3; i++)for(int j = 0; j < 3; j++){ans += val[i][j] * t;t *= 11;}return ans; }int Find(int now){if(now == 1) return val[tx][ty] ? 1 : 2;long long res = Get();if(M[res]) return M[res];for(int x = 0; x < 3; x++)for(int y = 0; y < 3; y++){if(!val[x][y]) continue;for(int i = 0; i < 4; i++){if(x + dx[i] >= n || y + dy[i] >= m) continue;int nx = (x + dx[i] + 3) % 3, ny = (y + dy[i] + 3) % 3;if(!val[nx][ny]) continue;int nnx = (nx + dx[i] + 3) % 3, nny = (ny + dy[i] + 3) % 3;if(lim[nnx][nny] == val[nnx][nny]) continue;val[nnx][nny] ++; val[nx][ny] --; val[x][y] --;int ans = Find(now-1);val[nnx][nny] --; val[nx][ny] ++; val[x][y] ++;if(ans == 1) return M[res] = 1;}}return M[res] = 2; }int main(){freopen("bzoj2719.in", "r", stdin);freopen("bzoj2719.out", "w", stdout);while(~ scanf("%d%d%d%d%d", &K, &n, &m, &tx, &ty)){M.clear();memset(lim, 0, sizeof(lim));memset(val, 0, sizeof(val));tx = (tx - 1) % 3; ty = (ty - 1) % 3;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++) lim[i%3][j%3] ++;int x, y;for(int i = 0; i < K; i++){scanf("%d%d", &x, &y);val[(x-1)%3][(y-1)%3] ++; }if(Find(K) == 1) puts("Yes");else puts("No");}return 0; }

---

總結(jié)

以上是生活随笔為你收集整理的BZOJ2719 - [Violet 4]银河之星 (记忆化搜索+hash)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。