小葱拿糖
题目
小葱将买来的糖放进了冰箱冷藏，但是小葱想吃糖了，小葱希望把自己想吃的糖从冰箱里面拿出来。具体来说，在一张行列的方格图中，有若干颗糖，每颗糖都是横向或者竖向摆放的。对于一个横向摆放的糖，我们只能左右移动这颗糖（任意距离，但不能跨越其他糖），而对于一个竖向摆放的糖只能上下移动。我们的目标是把编号为的糖从冰箱移出去，而移出去的方法是让该糖果能够移动到方格图的右边界的位置（只有一号糖果能移出去，其他糖即使在边界也不能出去）。我们保证任何一颗糖果长度至少为，并且号糖果一定横向放置。在糖果移动过程中不能穿越其他糖果，问在上述限制条件下小葱最少要移动多少次才能把号糖果移出冰箱。如果号糖果一开始就在右边界上请输出。
对于的数据，，最多有种不同的糖果，答案不超过步。
题解
*搜索！*搜索！搜索！
每次移动任意糖任意步，把每一个状态存下来（为了判断是否重复），然后bfs
如何存呢？其实一个糖只需要记录它的一个坐标位置，另一个是不变的。
对于这些糖的坐标，可以用一个进制数来存，最多有 种不同的糖果，所以 就够了，算一下，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;
}