poj1077 Eight
IAmL
posted @ 2009年3月30日 06:49
in 解题报告
with tags
poj1077 Eight解题报告
, 4261 阅读
经典的搜索题,可以用BFS,双向BFS,A*算法来写。 用单向BFS写的话,和普通的BFS没什么两样。唯一要注意的就是要压缩状态,可以用康托展开(或者直接用逆序数)+hash来判重。这样一共有9!种状态,比10^9少得多。另外如果是多case的话,可以从目标状态(12345678x)开始,先预处理,这样会快点。
======华丽的分割线=========
#include <iostream>
#include <cstring>
using namespace std;
#define N 362881
//bool snew[N], sold[N], tnew[N], told[N];
bool state[N];
int v[9], step[N];
const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
const int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
//0.r; 1.d; 2.l; 3.u
struct node
{
long num;
long pre;
int dir;
}q[N];
long canto()
{
int j, i, tmp;
long ans;
for (ans = 1, i = 0; i < 9; i++)
{
for (tmp = v[i] - 1, j = 0; j < i; j++)
tmp -= (v[j] < v[i]);
ans = ans + tmp * fact[8 - i];
}
return ans;
}
void toArray(long num)
{
int i = 8;
while (num)
{
v[i--] = num % 10;
num /= 10;
}
}
long toNum()
{
int i;
long ans = 0;
for (i = 0; i < 9; i++)
ans = ans * 10 + v[i];
return ans;
}
long BFS()
{
memset(state, false, sizeof(state));
long head, tail, val;
int xx, xy, i, tx, ty, tmp, pos1, pos2;
node p;
head = tail = 0;
p.num = toNum();
p.pre = -1;
p.dir = 0;
q[tail++] = p;
val = canto();
state[val] = true;
while (head < tail)
{
p = q[head];
toArray(p.num);
val = canto();
if (val == 1) return head;
//find x
for (i = 0; i < 9; i++)
if (v[i] == 9) break;
xy = i / 3;
xx = i % 3;
//move
tx = xx;
ty = xy;
for (i = 0; i < 4; i++)
{
tx += move[i][0];
ty += move[i][1];
if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3)
{
pos1 = tx + ty * 3;
pos2 = xx + xy * 3;
tmp = v[pos1];
v[pos1] = v[pos2];
v[pos2] = tmp;
val = canto();
if (!state[val])
{
state[val] = true;
p.num = toNum();
p.pre = head;
p.dir = i;
q[tail++] = p;
}
tmp = v[pos2];
v[pos2] = v[pos1];
v[pos1] = tmp;
}
tx = xx;
ty = xy;
}
head++;
}
if (head >= tail) return -1;
return head;
}
void print(long i)
{
long pos = 0;
while (q[i].pre != -1)
{
step[pos++] = q[i].dir;
i = q[i].pre;
}
//0.r; 1.d; 2.l; 3.u
for (i = pos - 1; i >= 0; i--)
{
switch (step[i])
{
case 0:
cout << 'r';
break;
case 1:
cout << 'd';
break;
case 2:
cout << 'l';
break;
case 3:
cout << 'u';
break;
}
}
cout << endl;
}
int main()
{
int i;
long tmp;
char c;
for (i = 0; i < 9; i++)
{
cin >> c;
if (c == 'x') v[i] = 9;
else v[i] = c - '0';
}
tmp = BFS();
if (tmp == -1) cout << "unsolvable\n";
else print(tmp);
return 0;
}
#include <cstring>
using namespace std;
#define N 362881
//bool snew[N], sold[N], tnew[N], told[N];
bool state[N];
int v[9], step[N];
const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
const int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
//0.r; 1.d; 2.l; 3.u
struct node
{
long num;
long pre;
int dir;
}q[N];
long canto()
{
int j, i, tmp;
long ans;
for (ans = 1, i = 0; i < 9; i++)
{
for (tmp = v[i] - 1, j = 0; j < i; j++)
tmp -= (v[j] < v[i]);
ans = ans + tmp * fact[8 - i];
}
return ans;
}
void toArray(long num)
{
int i = 8;
while (num)
{
v[i--] = num % 10;
num /= 10;
}
}
long toNum()
{
int i;
long ans = 0;
for (i = 0; i < 9; i++)
ans = ans * 10 + v[i];
return ans;
}
long BFS()
{
memset(state, false, sizeof(state));
long head, tail, val;
int xx, xy, i, tx, ty, tmp, pos1, pos2;
node p;
head = tail = 0;
p.num = toNum();
p.pre = -1;
p.dir = 0;
q[tail++] = p;
val = canto();
state[val] = true;
while (head < tail)
{
p = q[head];
toArray(p.num);
val = canto();
if (val == 1) return head;
//find x
for (i = 0; i < 9; i++)
if (v[i] == 9) break;
xy = i / 3;
xx = i % 3;
//move
tx = xx;
ty = xy;
for (i = 0; i < 4; i++)
{
tx += move[i][0];
ty += move[i][1];
if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3)
{
pos1 = tx + ty * 3;
pos2 = xx + xy * 3;
tmp = v[pos1];
v[pos1] = v[pos2];
v[pos2] = tmp;
val = canto();
if (!state[val])
{
state[val] = true;
p.num = toNum();
p.pre = head;
p.dir = i;
q[tail++] = p;
}
tmp = v[pos2];
v[pos2] = v[pos1];
v[pos1] = tmp;
}
tx = xx;
ty = xy;
}
head++;
}
if (head >= tail) return -1;
return head;
}
void print(long i)
{
long pos = 0;
while (q[i].pre != -1)
{
step[pos++] = q[i].dir;
i = q[i].pre;
}
//0.r; 1.d; 2.l; 3.u
for (i = pos - 1; i >= 0; i--)
{
switch (step[i])
{
case 0:
cout << 'r';
break;
case 1:
cout << 'd';
break;
case 2:
cout << 'l';
break;
case 3:
cout << 'u';
break;
}
}
cout << endl;
}
int main()
{
int i;
long tmp;
char c;
for (i = 0; i < 9; i++)
{
cin >> c;
if (c == 'x') v[i] = 9;
else v[i] = c - '0';
}
tmp = BFS();
if (tmp == -1) cout << "unsolvable\n";
else print(tmp);
return 0;
}