問題#
小葱は買ったキャンディを冷蔵庫に入れましたが、キャンディが食べたいと思っています。小葱は冷蔵庫から食べたいキャンディを取り出したいと考えています。具体的には、$N$ 行 $N$ 列のグリッドにいくつかのキャンディがあり、各キャンディは横向きまたは縦向きに配置されています。横向きに配置されたキャンディは左右に移動できます（任意の距離で、他のキャンディを越えてはいけません）、縦向きに配置されたキャンディは上下に移動できます。私たちの目標は、番号 $1$ のキャンディを冷蔵庫から移動させることであり、その方法はそのキャンディがグリッドの右端に移動できるようにすることです（番号 1 のキャンディだけが移動できます。他のキャンディは境界にいても移動できません）。すべてのキャンディの長さは少なくとも $2$ であり、$1$ 号キャンディは必ず横向きに配置されています。キャンディの移動中に他のキャンディを越えてはいけません。上記の制限条件の下で、小葱が $1$ 号キャンディを冷蔵庫から移動させるために最小限に移動する回数は何回ですか。もし $1$ 号キャンディが最初から右端にいる場合は $0$ を出力してください。
$100%$ のデータに対して、$1\leq N\leq8$、最大で $13$ 種類の異なるキャンディがあり、答えは $10$ ステップを超えません。
解答#
* 探索！* 探索！探索！
任意のキャンディを任意のステップで移動させ、各状態を保存します（重複を判断するために）、その後 bfs を行います。
どうやって保存するかというと、実際にはキャンディの 1 つの座標位置だけを記録し、もう 1 つは不変です。
これらのキャンディの座標は、$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;
}