http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
For anyone that has got accepted in this problem, please help me! I got WAs so many... what else I might miss? I just used A* with priority_queue. It works for all TC I created myself....
Moderator: Board moderators
fushar wrote:DId you mean that I should do BFS from final state to ALL reachable states?
Oh one more, how did you mark a state as visited?
int fact[10]; // a table of factorials
int encode(int a[9]) {
int c[10], i, k, r;
for (i = 0; i < 9; i++) c[i] = i;
for (r = 0, k = 0; k < 9; k++) {
r += c[a[k]] * fact[8 - k];
for (i = a[k]; i < 9; i++) c[i]--;
}
return r + 1;
}
void decode(int a[9], int r) {
int c[10], i, k;
for (i = 0; i < 9; i++) c[i] = i;
for (r--, k = 0; k < 9; k++) {
i = r / fact[8 - k];
r %= fact[8 - k];
a[k] = c[i];
for (; i < 9; i++) c[i] = c[i + 1];
}
}
Deleted AC code
user@localhost:/tmp$ g++ -o p p.cc && ./p >output
2 3 4 1 5 x 7 6 8
user@localhost:/tmp$ hexdump -C output
00000000 00 75 6c 6c 64 64 72 75 72 64 6c 6c 75 72 64 72 |.ullddrurdllurdr|
00000010 75 6c 64 72 0a |uldr.|
00000015
user@localhost:/tmp$
if (x != -2)
{
trace(P[x]);
printf("%c", M[x]);
}
if (P[x] != -2)
{
trace(P[x]);
printf("%c", M[x]);
}
mf wrote:Like this:
- Code: Select all
int fact[10]; // a table of factorials
int encode(int a[9]) {
int c[10], i, k, r;
for (i = 0; i < 9; i++) c[i] = i;
for (r = 0, k = 0; k < 9; k++) {
r += c[a[k]] * fact[8 - k];
for (i = a[k]; i < 9; i++) c[i]--;
}
return r + 1;
}
void decode(int a[9], int r) {
int c[10], i, k;
for (i = 0; i < 9; i++) c[i] = i;
for (r--, k = 0; k < 9; k++) {
i = r / fact[8 - k];
r %= fact[8 - k];
a[k] = c[i];
for (; i < 9; i++) c[i] = c[i + 1];
}
}
Users browsing this forum: No registered users and 0 guests