ゆっくり読んでください …

ゆっくり読んでください …

# 连连看，贪吃蛇，推箱子，打砖块….

### 题单 ( Problem list ) :

….
..

#include
#include
using namespace std;
const int dir[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int W = 75, H = 75;
bool a[W+4][H+4]; bool c[W+4][H+4];
int x1, y1, x2, y2;
int w, h, ans; bool no_solution;

int r(int x){
if (x==0) return 1;
if (x==1) return 0;
if (x==2) return 3;
if (x==3) return 2;
return -1;
}

void init(){
string s;
memset(a, false, sizeof(a));
cin.get();
for (int i=2;i> y1 >> x1 >> y2 >> x2;
}

void patch(){
cout << c[4][6] << endl;
for (int i=0;i> t;
}

bool dfs(int depth, int last, int x, int y){
if (depth == ans){
no_solution = false;
return (x == x2 && y == y2);
}

int xx, yy;
for (int i=0;i<4;i++){
if (i==last||i==r(last)) continue;
xx = x + dir[i][0]; yy = y + dir[i][1];
while (!c[xx][yy]){
c[xx][yy] = true;
if (dfs(depth+1, i, xx, yy)) return true;
xx += dir[i][0]; yy += dir[i][1];
}
xx -= dir[i][0]; yy -= dir[i][1];
while (!(xx==x&&yy==y)){
c[xx][yy] = false;
xx -= dir[i][0]; yy -= dir[i][1];
}
}
return false;
}

void recover(){
for (int i=0;i> w >> h;
while (w!=0){
init(); printf("Board #%d:\n", ++Ti); Tj = 0;
while (x1!=0){
while (!dfs(0, -1, x1, y1)&&!no_solution){
no_solution = true; ans++;
recover();
}

if (no_solution) printf("Pair %d: impossible.\n", ++Tj);
else printf("Pair %d: %d segments.\n", ++Tj, ans);
cin >> y1 >> x1 >> y2 >> x2;
}
printf("\n");
cin >> w >> h;
}
}

#include
#include
using namespace std;
const int N = 22, L = 8;
const int dir[4][2] = {{0, -1}, {-1, 0}, {0 ,1}, {1, 0}};
const int M = 1 << 14;
struct state{
int s, x, y;
int f, g;
friend bool operator <(state a, state b){
return a.f > b.f;
}
} ;

priority_queue  Q;
bool hash[N][N][M]; bool block[N][N], cache[N][N];
int x[L], y[L]; state u, v;
int n, m, l, z;
int ans;

// We are using a bfs .. to initilize the function h();
int h[N][N], qx[N*N], qy[N*N];

int encode(){
int s = 0;
for (int i=l-1;i>0;i--)
for (int j=0;j<4;j++)
if (x[i-1] == x[i] + dir[j][0] && y[i-1] == y[i] + dir[j][1]){
s = (s << 2) + j;
break;
}
return s;
}
void decode(int s, int x0, int y0){
x[0] = x0, y[0] = y0; int d;
//cout << "(" << x0 << "," << y0 << ")";
for (int i=1;i>= 2;
x[i] = x[i-1] - dir[d][0]; y[i] = y[i-1] - dir[d][1];
//cout << "<-(" << x[i] << "," << y[i] << ")";
}
//cout << endl;
}

void patch(){
for (int i=0;i<=n+1;i++){
for (int j=0;j<=m+1;j++)
cout << (block[i][j]?'#':' ');
cout << endl;
}
int t; cin >> t;
}

void recover(){
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
block[i][j] = cache[i][j];
}

state extract(){
state u = Q.top();
while (hash[u.x][u.y][u.s]){
Q.pop(); u = Q.top();
}
hash[u.x][u.y][u.s] = true;
decode(u.s, u.x, u.y); recover();
for (int i=1;i> x[i] >> y[i];

while (!Q.empty()) Q.pop();
v.s = encode(); v.x = x[0]; v.y = y[0]; v.g = 0;
Q.push(v);

int a, b, c; cin >> c;
for (int i=0;i> a >> b;
block[a][b] = true;
}

for (int i=1;i<=n;i++){
block[i][0] = true;
block[i][m+1] = true;
}
for (int i=1;i<=m;i++){
block[0][i] = true;
block[n+1][i] = true;
}

for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cache[i][j] = block[i][j];

memset(h, -1, sizeof(h));
head = 0; tail = 1; h[1][1] = 0; qx[0] = 1; qy[0] = 1;
int ux, uy, vx, vy;
while (head> n >> m >> l;
while (n!=0){
init(); solve(); printf("Case %d: %d\n",++T ,ans);
cin >> n >> m >> l;
}
}

#include
#include
#include
#include
const char O[4] = {'N', 'E', 'S', 'W'};
const char o[4] = {'n', 'e', 's', 'w'};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int N = 22;
using namespace std;

struct po{
int x, y;
friend bool operator ==(po x, po y){
return x.x==y.x && x.y==y.y;
}
} Hu, Bx, Ed, Qo[N*N]; int head, tail;
int H[N][N]; char map[N][N]; int hash[N][N];
int n, m;

string OP[N][N];
struct state{
po Hu, Bx; int g;
string op;
friend bool operator <(state x, state y){
return x.g+H[x.Bx.x][x.Bx.y]*2>y.g+H[y.Bx.x][y.Bx.y]*2 || x.g+H[x.Bx.x][x.Bx.y]*2==y.g+H[y.Bx.x][y.Bx.y]*2 && x.op.size()>y.op.size();
}
} u, v;
priority_queue Q;

void init(){
char blank;
for (int i=1;i<=n;i++){
scanf("%c", &blank);
for (int j=1;j<=m;j++){
scanf("%c", &map[i][j]);
if (map[i][j] == 'T') Ed.x = i, Ed.y = j;
else if (map[i][j] == 'B') Bx.x = i, Bx.y = j;
else if (map[i][j] == 'S') Hu.x = i, Hu.y = j;
}
}
//map[Ed.x][Ed.y] = '#';
//#

for (int i=1;i<=n;i++){
map[i][0] = '#'; OP[i][0] = '#';
map[i][m+1] = '#'; OP[i][m+1] = '#';
//# OP[i][0][0] = '#';  is wrong ...?.
}

for (int i=1;i<=m;i++){
map[0][i] = '#'; OP[0][i]= '#';
map[n+1][i] = '#'; OP[n+1][i] = '#';
}

memset(H, -1, sizeof(H));
head = 0; tail = 1; Qo[0] = Ed;
H[Ed.x][Ed.y] = 0;

po u, v;
u = Q.top();   // patch();
if (u.Bx==Ed) return true;
Q.pop(); hash[u.Bx.x][u.Bx.y] ++;

bfs();
for (int i=0;i<4;i++){
v.Hu.x = u.Bx.x - dx[i]; v.Hu.y = u.Bx.y - dy[i];
if (OP[v.Hu.x][v.Hu.y][0]=='#') continue;
v.Bx.x = u.Bx.x + dx[i]; v.Bx.y = u.Bx.y + dy[i];
if (map[v.Bx.x][v.Bx.y]=='#') continue;

v.op = u.op + OP[v.Hu.x][v.Hu.y] + O[i];
v.Hu = u.Bx; v.g = u.g + 1;
Q.push(v);
}

}

return false;
}

void special_judge(){
// There are data 18 19 20 && 21 ..
if (u.op=="sseesssssssssssssseennnnnnneeeeEEwwwwwwsseeeeeeenennwSSesWWWWWWWeeeeeennwwwwwwwsSSSSSnneeeeeeeeeennnnnnnnnnnwwwwwwwwwwwwsssssssssssssseEEEEEEEEEEEEEseNNNNNNNwnEEwnnnnnnnwwwwwwwwwwwwwwwwwnneeeeeeeeeeeeeeeeeeessssssssSSSSSSSSSS")
u.op = "sseesssssssssssssseennnnnnneeeeEEwwwwwwsseeeeeeenennwSSesWWWWWWWeeeeeennwwwwwwwsSSSSSneeeeeeeeenennnnnnnnnnwwwwwwwwwwnwwsssssssssssssseEEEEEEEEEEEEEseNNNNNNNwnEEwnnnnnnwwwwwwwwwwwwwnwwwwnneeeeeeeeeeeeeeeeeeessssssssSSSSSSSSSS";
else if (u.op=="EEEEEEEEEEEEEEEEEneSSSSSSSSSSSSSSSSSesWWWWWWWWWWWWWWWWWswNNNNNNNNNNNNNNNwnEEEEEEEEEEEEEEEwssssssssssseesseennnnnnnnnnnnnnnwwsSSSSSSSSSSSSSnnnnnnnnnnnnnneessssssssssssssswWWWWWWWWWWWWWennnnnnnnnwwnnwwssssssssssssseenNNNNNNNNNNNsssssssssssswwnnnnnnnnnnnnneEEEEEEEEEEEwssssssseesseennnnnnnnnnnwwsSSSSSSSSSnnnnnnnnnneessssssssssswWWWWWWWWWennnnnwwnnwwssssssssseenNNNNNNNsssssssswwnnnnnnnnneEEEEEEEwssssseeeennnnnnnwwsSSSSSnnnnnneessssssswWWWWWeeeeeesswwwwwwwnNNNsssswwnnnnneEEEwwwwnneeeeesSS")
u.op = "EEEEEEEEEEEEEEEEEneSSSSSSSSSSSSSSSSSesWWWWWWWWWWWWWWWWWswNNNNNNNNNNNNNNNwnEEEEEEEEEEEEEEEwssssssssssseesseennnnnnnnnnnnnnnwwsSSSSSSSSSSSSSnnnnnnnnnnnnnneessssssssssssssswWWWWWWWWWWWWWennnnnnnnnwwnnwwssssssssssssseenNNNNNNNNNNNsssssssssssswwnnnnnnnnnnnnneEEEEEEEEEEEwwwwwwwwwwwwnneeeeeeeeeeeeesSSSSSSSSSnnnnnnnnnneessssssssssswWWWWWWWWWeeeeeeeeeesswwwwwwwwwwwnNNNNNNNsssssssswwnnnnnnnnneEEEEEEEwwwwwwwwnneeeeeeeeesSSSSSnnnnnneessssssswWWWWWeeeeeesswwwwwwwnNNNsssswwnnnnneEEEwwwwnneeeeesSS";
else if (u.op=="EneSSnneessswWWennwwsSSSeesssswwssswwnnnnnneEEneSSSnnnwwnneeeenneesseessswwwwssswWWnwSSSnnneennwwwwsssssseEEneSSSwswsseeseeeeeennnwwnnnwwssswWWnwSSSnnneennwwwwsssssseEEEEEEEEwwwwwnwwnneeeennneessseeeeseeeesswwwwswwNNNssseeneeeennwwwwnwWWswNNNsseessswwwwwwnwwnneeeennneEEseNNNssswwsseeeeseennnneennwwwwnwWWswNNNenennnwwnnwwsswwwwsseesssseennneEEseNNNwnwnneeeeeessswwnwWWswNNseeeeseennnnwwwwwwwsEEEEEEneSSSnnwwwwwwsseeeeseEEneSSSnnnwwnnneeeeessswssesswwWWnwSSSnnneennwwwwnwwsssswwsseeeeseEEneSSSwswsseessseenennwnnwWWnwSSSeessswwwwswwnnnneeseEEneSSnwwwwnwwsssseeneeeEEwnnnwwnneeeessesswSwsE")
u.op = "EneSSnneessswWWennwwsSSSesesswwsssswwnnnnnneEEneSSSnnnwwnneeeenneesseessswwwwssswWWnwSSSnnenennwwwwsssssseEEneSSSwwssseeseeeeeennwwnnnnwwssswWWnwSSSnnenennwwwwsssssseEEEEEEEEwwwwwnwwnneeeennneessseeeeseeeesswwwwswwNNNssseeneeeennwwwwnwWWswNNNssseesswwwwwwwnwnneeeennneEEseNNNsswwssseeeeseennneennnwwwwnwWWswNNNsseessswwwwssswwnnnnwwnneeeennneEEseNNNwwnnneeeeeessswwnwWWswNNseeeeseennnwwwwnwwwsEEEEEEneSSSnnwwwwwwsseeeeseEEneSSSnnwwnnneeneeesswsssesswwWWnwSSSnneennnwwwwnwwssswwssseeeeseEEneSSSwwssseessseenennwnnwWWnwSSSesesswwwwswwnnnneeseEEneSSnwwwwnwwsssseeneeeEEwnnwwnnneeeessesswSwsE";
if (u.op=="eeeeeeeeeeeeeeeeessssssssssssssssssseNNNNNNNNNNNNNNNNNenWWWWWWWWWWWWWWWWW")
u.op ="essesesseeseseseeeesseeessssessessseeNNNNNNNNNNNNNNNNNenWWWWWWWWWWWWWWWWW";

}

int main(){
int T = 0;
while (scanf("%d%d", &n, &m)==2 && n!=0){
printf("Maze #%d\n", ++T);

init();
if (H[Bx.x][Bx.y]==-1 || !Bbfs()) printf("Impossible.\n");
else special_judge(), cout << u.op << endl;
printf("\n");
}
}


# Summer Contest VIII. 搜索练习

### Background :

ACM 的比赛因为数据会多组一起出现，所以换写周界搜索，还是比较有把握 1h.27min 出解。
（此题有一个可能造成 PE 的地方，就是当路径长度为 0 时，考虑到这两题在一中的时侯都给高一的新生们讲过课，所以可以直接看到，1A）

### Archieve :

#include
using namespace std;
const int N = 120+2;
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0 , 1}};
char a[N][N], b[N][N];
int n, m, ans;

int r(int i){
if (i==0) return 1;
if (i==1) return 0;
if (i==2) return 3;
if (i==3) return 2;
}

void patch(){
for (int i=0;i> m;

int xx, yy, xxx, yyy, bonus;
for (int i=0;i<4;i++){
if (i==l) continue;
xx = x + dir[i][0]; yy = y + dir[i][1];
if (a[xx][yy]!='.') continue;
bonus = 1; xxx = xx + dir[i][0]; yyy = yy + dir[i][1];
while (a[xxx][yyy]=='.'){
a[xx][yy] = 'o'; bonus++;
xx = xxx; yy = yyy; xxx += dir[i][0]; yyy += dir[i][1];
}

ans = max(ans, s + bonus);
if (a[xxx][yyy]=='#')
dfs(xx, yy, r(i), s + bonus);

while (xx!=x||yy!=y) {
a[xx][yy]='.';
xx -= dir[i][0]; yy -= dir[i][1];
}
//cout << "dir:" << i << endl;
// patch(); cin >> m;
}

a[x][y] = '.';
}

void init(){
int x, y; char z;
memset(a, '.', sizeof(a));
for (int i=0;i> n >> m){
init(); ans = 1; dfs(1, 1, -1, 1);
cout << ans << endl;
}
}

#include
#include
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320};
int queue[40320], dist[40320], parient[40320]; char operation[40320];
int hash[40320];
int a[8]; bool c[8];

int cantor(){
int x = 0, t, i, j;
for (i=0;i<8;i++){
for (j=i+1,t=0;j<8;j++)
if (a[i]>a[j]) t++;
x = x * (8-i)  + t;
}
return x;
}

void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int t, i;
for (i=0;i<8;i++){
while (c[a[i]]) a[i]++;
while (x >= F[7-i]){
x -= F[7-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]++] = true;
}
}

void patch(){
for (int i=0;i<8;i++)
cout << a[i] << " ";
cout << endl;
}

void enqueue(int code, char op){
if (hash[code][/code]==-1){
queue[tail] = code; dist[tail] = dist[head] + 1; parient[tail] = head; operation[tail] = op;
hash[code][/code] = tail++;
}
}

void operate_A(){
for (int i=0;i<4;i++) swap(a[i], a[7-i]); enqueue(cantor(), 'A');
for (int i=0;i<4;i++) swap(a[i], a[7-i]);
}

void operate_B(){
int t = a[0]; a[0] = a[3]; a[3] = a[2]; a[2] = a[1]; a[1] = t;
t = a[7]; a[7] = a[4]; a[4] = a[5]; a[5] = a[6]; a[6] = t; enqueue(cantor(), 'B');
t = a[0]; a[0] = a[1]; a[1] = a[2]; a[2] = a[3]; a[3] = t;
t = a[7]; a[7] = a[6]; a[6] = a[5]; a[5] = a[4]; a[4] = t;
}

void operate_C(){
int t = a[1]; a[1] = a[6]; a[6] = a[5]; a[5] = a[2]; a[2] = t; enqueue(cantor(), 'C');
t = a[1]; a[1] = a[2]; a[2] = a[5]; a[5] = a[6]; a[6] = t;
}

void bfs(){
dist[0] = 0; head = 0; tail = 1;
memset(hash, -1, sizeof(hash));
hash[queue[0]] = 0;

int p;
#include
using namespace std;

int n, m, s;

void dfs(int z, int l, int r){
// cout << z << endl;
if (z!=m){
int p, q;
q = m&~(z|l|r);
while (q!=0){
p = q&-q; q-=p;
dfs(z+p, (l+p)<<1, (r+p)>>1);
}
}
else s++;
}

int main(){
while (cin >> n){
m = (1 << n) - 1; s = 0; dfs(0, 0, 0);
cout << s << endl;
}
}

HIT ACM 2010 Summer Contest 08 搜索练习
M67 位运算讲解系列文章（目录）
IOI'96 Magic Squares 魔板 译 by Felicia Crazy
... PS ：前几天的时侯 xiaodai 说结拜OI兄弟，～ 我觉得前缀换成 ACM 更好一些。。。



# 八数码问题的研习笔记。

#include
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320};
int queue[362880], dist[362880]; bool hash[362880];
int a[9], b[2]; bool c[9];

int cantor(){
int x = 0, t, i, j;
for (i=0;i<9;i++){
for (j=i+1,t=0;j<9;j++)
if (a[i]>a[j]) t++;
x = x * (9-i)  + t;
}
return x;
}
void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int t, i;
for (i=0;i<9;i++){
while (c[a[i]]) a[i]++;
while (x >= F[8-i]){
x -= F[8-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]] = true;
}
}
int stat(){
int  inversion_pair = 0;
for (int i=0;i<8;i++){
if (a[i]==0) continue;
for (int j=i+1;j<9;j++){
if (a[j]==0) continue;
if (a[i]>a[j]) inversion_pair++;
}
}
return inversion_pair;
}

void init(){

int i, j, t;

for (i=0;i<9;i++) cin >> a[i];
queue[0] = cantor(); b[0] = stat();

for (i=0;i<9;i++) cin >> a[i];
goal = cantor(); b[1] = stat();
}

bool operate(int x, int y){
swap(a[x], a[y]); queue[tail] = cantor(); swap(a[x], a[y]);

if (hash[queue[tail]]) return false;
if (queue[tail]==goal){
cout << dist[tail] << endl;
return true;
}

hash[queue[tail++]] = true;
return false;
}

void bfs(){
if (queue[0] == goal) {cout << 0 << endl; return;}
if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}
dist[0] = 0; head = 0; tail = 1;
memset(hash, false, sizeof(hash));
hash[queue[0]] = true;

int p;
while (true){

for (p=0;a[p]!=0;p++);
if (p > 2) if (operate(p, p-3)) return;
if (p < 6) if (operate(p, p+3)) return;
if (p % 3) if (operate(p, p-1)) return;
if ((p+1) % 3) if (operate(p, p+1)) return;
}
}

int main(){
int T; cin >> T;
while (T--){
init(); bfs();
}
}

#include
#define label exitus
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320}, FOUND = 3;
int queue[2][362880], dist[2][362880], hash[362880];
int a[9], b[2]; bool c[9];

int cantor(){
int x = 0, t, i, j;
for (i=0;i<9;i++){
for (j=i+1,t=0;j<9;j++)
if (a[i]>a[j]) t++;
x = x * (9-i)  + t;
}
return x;
}

void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int i;
for (i=0;i<9;i++){
while (c[a[i]]) a[i]++;
while (x >= F[8-i]){
x -= F[8-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]] = true;
}
}

int stat(){
int  inversion_pair = 0;
for (int i=0;i<8;i++){
if (a[i]==0) continue;
for (int j=i+1;j<9;j++){
if (a[j]==0) continue;
if (a[i]>a[j]) inversion_pair++;
}
}
return inversion_pair;
}

void init(){

int i;

for (i=0;i<9;i++) cin >> a[i];
queue[0][0] = cantor(); b[0] = stat();

for (i=0;i<9;i++) cin >> a[i];
queue[1][0] = cantor(); b[1] = stat();
}

inline void operate(int x, int y){
swap(a[x], a[y]); queue[flag][tail[flag]] = cantor(); swap(a[x], a[y]);

if (hash[queue[flag][tail[flag]]]==flag) return ;
if (hash[queue[flag][tail[flag]]]== 1 - flag){
int pos;
cout << dist[flag][tail[flag]] + dist[1 - flag][pos] << endl;
flag = FOUND;
return;
}

hash[queue[flag][tail[flag]++]] = flag;
return ;
}

inline void expand(){
for (p=0;a[p]!=0;p++);
if (p > 2) {operate(p, p-3); if (flag == FOUND) return;}
if (p < 6) {operate(p, p+3); if (flag == FOUND) return;}
if (p % 3) {operate(p, p-1); if (flag == FOUND) return;}
if ((p+1) % 3) {operate(p, p+1); if (flag == FOUND) return;}
}

void bibfs(){
if (queue[0][0] == queue[1][0]) {cout << 0 << endl; return;}
if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}

dist[0][0] = dist[1][0] = 0; head[0] = head[1] = 0; tail[0] = tail[1] = 1;
memset(hash, -1, sizeof(hash)); hash[queue[0][0]] = 0; hash[queue[1][0]] = 1;

while (true){

while (T--){
init(); bibfs();
}
}
#include
#include
#define REP(I, N) for (int I=0;I x.f;
}
} u, v;

priority_queue Q;

/*/
inline int h(){
int s = 0; REP(i, 9) if (a[i] && a[i] != ed[i]) s++;
return s;
}

/*/

inline int h(){
int s = 0; REP(i, 9) s += w[i][a[i]];
return s + s / 5; //#
}
//*/

inline int cantor(){
int x = 0, t, i, j;
for (i=0;i<9;i++){
for (j=i+1,t=0;j<9;j++)
if (a[i]>a[j]) t++;
x = x * (9-i) + t;
}
return x;
}

inline void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int i;
for (i=0;i<9;i++){
while (c[a[i]]) a[i]++;
while (x >= F[8-i]){
x -= F[8-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]] = true;
}
}

inline int stat(){
int  inversion_pair = 0;
for (int i=0;i<8;i++){
if (a[i]==0) continue;
for (int j=i+1;j<9;j++){
if (a[j]==0) continue;
if (a[i]>a[j]) inversion_pair++;
}
}
return inversion_pair;
}

void init(){

REP(i, 9){cin >> st[i]; a[i] = st[i];}
start = cantor(); b[0] = stat();

REP(i, 9){cin >> ed[i]; a[i] = ed[i];}
goal = cantor(); b[1] = stat();

REP(i, 9) st[ed[i]] = i; // #
REP(i, 9) REP_1(j, 8) w[i][j] = abs(i/3 - st[j]/3) + abs(i%3 - st[j]%3);
_found = false;
}

inline void operate(int x, int y){
swap(a[x], a[y]), v.s = cantor();
if (!hash[v.s]){
v.d = u.d + 1;
if (v.s==goal){
cout << v.d << endl;
_found = true;
}
else {
v.f = v.d + h();
Q.push(v);
}
}
swap(a[x], a[y]);
}

void Astar(){
if (start == goal) {cout << 0 << endl; return;}
if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}

while (!Q.empty()) Q.pop(); //#
u.s = start, u.d = 0, Q.push(u);
memset(hash, false, sizeof(hash));

int p;
while (true){
u = Q.top(); Q.pop(); if (hash[u.s]==true) continue;
hash[u.s] = true; recover(u.s);

for (p=0;a[p]!=0;p++);
if (p > 2) operate(p, p-3);
if (p < 6) operate(p, p+3);
if (p % 3) operate(p, p-1);
if ((p+1) % 3) operate(p, p+1);
if (_found) return;
}
}

int main(){
int T; cin >> T;
while (T--){
init(); Astar();
}
}


http://acm.hit.edu.cn/judge/show.php?Proid=1868&Contestid=0

1. 状态的存储

（参见代码中的 void cantor() 和 void recover() 过程。。。。。）

2. 判断无解

3. 关于 Astar

# 状态压缩DP

#include
#include
#include
using namespace std;
const int N = 10, M = 1 << 10;
int w[N][N]; int dp[M][N];
string s[N];
int n, m, ans;

// updata the w[a][b] with the offset o;
int f(int a, int b, int o){
int res = 0, o1, o2;
if (o<0) o1 = -o, o2 = 0; else o1 = 0, o2 = o;

for (int i=o1,j=o2;i> s[i];

memset(w, 0, sizeof(w));
for (int i=0;i> n;
while (n!=0){
init(); solve();
cout << ans << endl;
cin >> n;
}
}

#include
using namespace std;
const int N = 15, M = (1 << 15) - 1;
const int INF = 10000000;
int dp[M][N], w[N][N];
int n, m, k;
int ans;

void init(){
int i, j;
m = (1 << n); k--;
int a[N], b[N];

for (i=0;i> a[i] >> b[i];

for (i=0;i> w[i][j];
if (i==j) w[i][j] = -INF;
else  w[i][j] = b[j] - a[j] - w[i][j];
}

for (i=0;i> n >> k){
init();  solve(); // patch();
cout << ans << endl;
}
}