题目大意:

题目分析:

因为前段时间做了一道转花盆刻骨铭心,所以一看到这题就开始bfs+hash,明知道过不了,但谁知道姿势正确得了85分,后来出题人告诉数据最大步数才14,我把搜索停止条件改成了18,瞬间ac。。。

正解有很多种:迭代加深,双向搜索,\(A^{*}\)……

考后写了一下迭代加深,不是一般的快,具体讲解请百度骑士.

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
namespace IO{
inline int read(){
int i = 0, f = 1; char ch = getchar();
for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-') f = -1, ch = getchar();
for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');
return i * f;
}
inline void wr(ll x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}using namespace IO; const int N = 10, M = 30;
int T, bin[N], ans;
char initMap[M];
struct node{char s[M]; int cnt;};
queue<node> que; bool flag;
typedef unsigned long long ull;
ull desVal;
const int Mod = 233333, H = 31;
vector<ull> G[Mod + 5];
vector<int> used; inline bool insert(ull x){
int key = x % Mod;
for(int i = 0; i < G[key].size(); i++)
if(G[key][i] == x) return false;
G[key].push_back(x); used.push_back(key); return true;
} inline ull toHash(char s[M]){
ull ret = 0;
for(int i = 1; i <= 21; i++) ret = ret * H + s[i] - '0';
return ret;
} inline void init(){
bin[0] = 0;for(int i = 1; i <= 6; i++) bin[i] = bin[i - 1] + i;
for(int i = 1; i <= 6; i++)
for(int j = 1; j <= i; j++)
desVal = desVal * H + i - 1;
} inline pair<int, int> get0Pos(char s[M]){
pair<int, int> ret;
for(int i = 1; i <= 6; i++)
for(int j = 1; j <= i; j++)
if(s[bin[i - 1] + j] == '0') {ret.first = i, ret.second = j; return ret;}
} inline void add(char s[M], int cnt){
node tmp;
for(int i = 1; i <= 21; i++) tmp.s[i] = s[i];
tmp.cnt = cnt;
que.push(tmp);
} int main(){
T = read(); init();
while(T--){
for(int i = 0; i < used.size(); i++) G[used[i]].clear();
flag = false; ans = 0;
for(int i = 1; i <= 6; i++)
for(int j = 1; j <= i; j++) initMap[bin[i - 1] + j] = read() + '0';
ull hashVal = toHash(initMap);
if(hashVal == desVal){
wr(0); putchar('\n');
continue;
}
insert(hashVal);
while(!que.empty()) que.pop();
add(initMap, 0);
while(!que.empty()){
char now[M];
node tmp = que.front();
int cnt = tmp.cnt;
for(int i = 1; i <= 21; i++) now[i] = tmp.s[i];
pair<int, int> pos = get0Pos(now);
//leftup
if(pos.second != 1){
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1])]);
ull hashVal = toHash(now);
if(hashVal == desVal){flag = true, ans = cnt + 1; break;}
else if(cnt + 1 == 18) break;
if(insert(hashVal)) add(now, cnt + 1);
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1])]);
}
//up
if(pos.second != bin[pos.first] - bin[pos.first - 1]){
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1]) + 1]);
ull hashVal = toHash(now);
if(hashVal == desVal){flag = true, ans = cnt + 1; break;}
else if(cnt + 1 == 18) break;
if(insert(hashVal)) add(now, cnt + 1);
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1]) + 1]);
}
//down
if(pos.first != 6){
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second]);
ull hashVal = toHash(now);
if(hashVal == desVal){flag = true, ans = cnt + 1; break;}
else if(cnt + 1 == 18) break;
if(insert(hashVal)) add(now, cnt + 1);
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second]);
}
//rightdown
if(pos.first != 6){
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second + 1]);
ull hashVal = toHash(now);
if(hashVal == desVal){flag = true, ans = cnt + 1; break;}
else if(cnt + 1 == 18) break;
if(insert(hashVal)) add(now, cnt + 1);
swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second + 1]);
}
que.pop();
}
if(flag) wr(ans), putchar('\n');
else printf("too difficult\n");
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
namespace IO{
inline int read(){
int i = 0, f = 1; char ch = getchar();
for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-') f = -1, ch = getchar();
for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');
return i * f;
}
inline void wr(ll x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}using namespace IO; const int N = 10, M = 30;
int T, ans;
int initMap[N][N];
bool flag;
typedef pair<int, int> P;
P pos;
const int des[N][N] = {{0}, {0, 0},{0,1,1},{0,2,2,2},{0,3,3,3,3},{0,4,4,4,4,4},{0,5,5,5,5,5,5}}; inline int H(){
int ret = -1;
for(int i = 1; i <= 6; i++)
for(int j = 1; j <= i; j++) if(initMap[i][j] ^ des[i][j]) ret++;
return ret;
} inline bool dfs(int now, int dep, int x, int y){
if(now > dep){
if(H() == -1) return true;
else return false;
}
if(H() + now - 1 > dep) return false;
//leftUp
if(y != 1){
swap(initMap[x][y], initMap[x - 1][y - 1]);
if(dfs(now + 1, dep, x - 1, y - 1)) return true;
swap(initMap[x][y], initMap[x - 1][y - 1]);
}
//up
if(y != x){
swap(initMap[x][y], initMap[x - 1][y]);
if(dfs(now + 1, dep, x - 1, y)) return true;
swap(initMap[x][y], initMap[x - 1][y]);
}
//down
if(x != 6){
swap(initMap[x][y], initMap[x + 1][y]);
if(dfs(now + 1, dep, x + 1, y)) return true;
swap(initMap[x][y], initMap[x + 1][y]);
}
//rightdown
int tmp = 0;
for(int i = 1; i < x; i++) tmp += i;
if(x != 6){
swap(initMap[x][y], initMap[x + 1][y + 1]);
if(dfs(now + 1, dep, x + 1, y + 1)) return true;
swap(initMap[x][y], initMap[x + 1][y + 1]);
}
return false;
} int main(){
T = read();
while(T--){
ans = 0, flag = false;
for(int i = 1; i <= 6; i++)
for(int j = 1; j <= i; j++) {
scanf("%d", &initMap[i][j]);
if(!initMap[i][j]) pos = P(i, j);
}
// cout<<pos.first<<" "<<pos.second<<endl;
for(int i = 0; i <= 20; i++)
if(dfs(1, i, pos.first, pos.second)){flag = true, ans = i;break;}
if(flag) wr(ans), putchar('\n');
else printf("too difficult\n");
}
return 0;
}
05-11 18:15