題目#
小蔥將買來的糖放進了冰箱冷藏，但是小蔥想吃糖了，小蔥希望把自己想吃的糖從冰箱裡面拿出來。具體來說，在一張 $N$ 行 $N$ 列的方格圖中，有若干顆糖，每顆糖都是橫向或者豎向擺放的。對於一個橫向擺放的糖，我們只能左右移動這顆糖（任意距離，但不能跨越其他糖），而對於一個豎向擺放的糖只能上下移動。我們的目標是把編號為 $1$ 的糖從冰箱移出去，而移出去的方法是讓該糖果能夠移動到方格圖的右邊界的位置（只有一號糖果能移出去，其他糖即使在邊界也不能出去）。我們保證任何一顆糖果長度至少為 $2$，並且 $1$ 號糖果一定橫向放置。在糖果移動過程中不能穿越其他糖果，問在上述限制條件下小蔥最少要移動多少次才能把 $1$ 號糖果移出冰箱。如果 $1$ 號糖果一開始就在右邊界上請輸出 $0$。
對於 $100%$ 的數據，$1\leq N\leq8$，最多有 $13$ 種不同的糖果，答案不超過 $10$ 步。
題解#
* 搜索！* 搜索！搜索！
每次移動任意糖任意步，把每一個狀態存下來（為了判斷是否重複），然後 bfs
如何存呢？其實一個糖只需要記錄它的一個坐標位置，另一個是不變的。
對於這些糖的坐標，可以用一個 $n$ 進制數來存，最多有 $13$ 種不同的糖果，所以 $n^{13} - 1$
就夠了，算一下，unsigned long long 夠了
注意#
每次放入一個新的狀態前先檢測要放入的這個狀態是不是答案，否則有可能會被卡超時（因為這個調了 2 個小時 QAQ）
代碼#
#include<bits/stdc++.h>
#define ull unsigned long long
#define DOWN 1
#define RIGHT 0
using namespace std;
const int N = 10;
int a[N][N], n, typenum;
const int M = 15;
// map壓ull
map<ull, int> step;
queue<ull> qwq;
int towards[M], pos[M], len[M], another_pos[M];
void trans(ull state)
{
int cnt = typenum;
while(cnt >= 1)
{
ull b = state % n;
pos[cnt] = b;
state /= n;
if(towards[cnt] == DOWN)
{
// cout << cnt << "點 DOWN" << endl;
for(int i = b;i <= b + len[cnt] - 1;i++)
{
a[i][another_pos[cnt]] = cnt;
}
}
else
{
// cout << cnt << "點 RIGHT" << endl;
for(int i = b;i <= b + len[cnt] - 1;i++)
{
a[another_pos[cnt]][i] = cnt;
}
}
cnt --;
}
}
ull pack()
{
ull start = 0;
for(int i = 1;i <= typenum;i++)
{
start = start * n + pos[i];
}
return start;
}
int main()
{
freopen("take.in", "r", stdin);
freopen("take.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
cin >> a[i][j];
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(a[i][j] == 0) continue;
int cl = a[i][j];
if(a[i + 1][j] == cl) towards[cl] = DOWN;
else towards[cl] = RIGHT;
if(towards[cl] == DOWN) pos[cl] = i, another_pos[cl] = j;
else pos[cl] = j, another_pos[cl] = i;
int x = i, y = j;
len[cl] = 0;
while(x <= n && y <= n && a[x][y] == cl)
{
a[x][y] = 0;
(towards[cl] == DOWN) ? (x ++) : (y++) ;
len[cl] ++;
}
typenum = max(typenum, cl);
}
}
ull start = 0;
for(int i = 1;i <= typenum;i++)
{
start = start * n + pos[i];
}
step[start] = 0;
qwq.push(start);
while(qwq.size())
{
ull t = qwq.front();
qwq.pop();
memset(a, 0, sizeof a);
trans(t);
if(pos[1] + len[1] - 1 >= n)
{
cout << step[t] << endl;
exit(0);
}
for(int i = 1;i <= typenum;i++)
{
if(towards[i] == DOWN)
{
for(int movement = 1;movement <= n;movement++)
{
if(a[pos[i] + len[i] - 1 + movement][another_pos[i]] != 0 || pos[i] + len[i] - 1 + movement > n) break;
pos[i] = pos[i] + movement;
ull now = pack();
pos[i] -= movement;
if(step[now] != 0)
continue;
qwq.push(now), step[now] = step[t] + 1;
/*就這裡*/if(i == 1 && pos[i] + len[i] - 1 + movement == n)
{
cout << step[now];
exit(0);
}
}
for(int movement = -1;movement >= -n;movement--)
{
if(a[pos[i] + movement][another_pos[i]] != 0 || pos[i] + movement < 1) break;
pos[i] = pos[i] + movement;
ull now = pack();
pos[i] -= movement;
if(step[now] != 0)
continue;
qwq.push(now), step[now] = step[t] + 1;
if(i == 1 && pos[i] + len[i] - 1 + movement == n)
{
cout << step[now];
exit(0);
}
}
}
else
{
for(int movement = 1;movement <= n;movement++)
{
if(a[another_pos[i]][pos[i] + len[i] - 1 + movement] != 0 || pos[i] + len[i] - 1 + movement > n) break;
pos[i] = pos[i] + movement;
ull now = pack();
pos[i] -= movement;
if(step[now] != 0)
continue;
qwq.push(now), step[now] = step[t] + 1;
if(i == 1 && pos[i] + len[i] - 1 + movement == n)
{
cout << step[now];
exit(0);
}
}
for(int movement = -1;movement >= -n;movement--)
{
if(a[another_pos[i]][pos[i] + movement] != 0 || pos[i] + movement < 1) break;
pos[i] = pos[i] + movement;
ull now = pack();
pos[i] -= movement;
if(step[now] != 0)
continue;
qwq.push(now), step[now] = step[t] + 1;
if(i == 1 && pos[i] + len[i] - 1 + movement == n)
{
cout << step[now];
exit(0);
}
}
}
}
//step等由這個點向外擴展的時候再更新
}
return 0;
}