10422 - Knights in FEN

[Whinii F.]

Came back with an AC with 0.023 sec
Assume you could declare 25!/(12! 12!) array without MLE. But the resulting array only will have VERY few elements, most of them filled with null.

So you can replace them into a hashed set or something. Of course it will cost some time to check if a state has been visited, but it will not matter much since the number of the nodes are so small.

My program uses DFS, but searches not more than 1000 states per input case. (checked with an assert())

[Observer]

I know the DFS approach, but I still want to know the BFS implementation...

[turuthok]

Observer, I lost my code for this one ... but I used BFS approach. As far as I can recall, I started from target state, find possible moves that are one-step away ... I repeated that it until at most 10 steps. I stored each possible move into a hash-list. After this, I just dealt with the inputs, if it's within 10 moves, it must be in my hash list.

-turuthok-

[Larry]

Ya, me too, though I guess it wasn't clear by my last post..

[helpless]

generate all node from final state to deph 10 ensuring that the last state will not generate again use long(32 bit) data type to store 25 position

[Observer]

Thanks all. I finally rewrote my code and got Accepted in 0.008 sec. Not as good as 0.000 sec. of course

[jackie]

I search the forum but the topic is the time limit. I really don't know why WA?
Can anyone help PLZ? Some test data will work . THKS!

A binary number and the blank position ------- one state

[cpp]#pragma warning(disable:4786)
#include <cstdio>
#include <memory>
#include <cassert>
#include <set>
using namespace std;
set< pair<int,int> >used;
bool finish;
pair<int,int> final;
int best;
const int digit[25] = {16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1};
const int xtran[8] = {-2,-2,-1,-1,1,1,2,2};
const int ytran[8] = {-1,1,-2,2,-2,2,-1,1};

inline bool suit(int a)
{
return a >= 0 && a < 5;
}
void traceBack(int depth,pair<int,int>c)//depth--setps searched
{
assert(c.first > 33554432);
used.insert(c);
if (depth > 9)
return;
int x = c.second / 5, y = c.second % 5, pattern = c.first;
pair<int,int> next;
for (int i = 0; i < 8; ++i)
{
if (suit(x + xtran) && suit(y + ytran))
{
next.second = (x + xtran) * 5 + y + ytran;
if (digit[next.second] & pattern)
next.first = pattern ^ digit[next.second] ^ digit[x * 5 + y];
else
next.first = pattern;
if (next == final)
{
finish = true;
best = best > depth+1 ? depth + 1 : best;
return;
}
if (used.find(next) == used.end())
traceBack(depth+1,next);
}
}
}

int main()
{
// freopen("10422.in","r",stdin);
int cnt,i,j;
pair<int,int> current;
final.first = 66554912;//11111; 01111; 00011 00001 00000
final.second = 12;
char input[6];
scanf("%d",&cnt);
getchar();
for (NULL; cnt--; NULL)
{
best = 12;
used.clear();
finish = false;
current.first = 1;
for (i = 0; i < 5; ++i)
{
gets(input);
assert(strlen(input) == 5);
for (j = 0; j < 5; ++j)
{
if (input[j] == ' ')
current.second = 5 * i + j;
if (input[j] == '1')
current.first = (current.first << 1) | 1;
else
current.first <<= 1;
}
}
traceBack(0,current);
assert(used.size() < 100000);
if (!finish)
printf("Unsolvable in less than 11 move(s).\n");
else
printf("Solvable in %d move(s).\n",best);
}
return 0;
}[/cpp]

[jackie]

Seems no one is interested !

Now i find the used <set> is wrong ,but it too slow .

May be two way BFS will work.

It's some task tomorrow.

[jackie]

Now make it one word.

[cpp]Method Time (second) Memory States checked
TraceBack >7 >5M nearly 1000000
BFS(from begin to end) >4 >4M >100000
BFS(from end to begin) >2 >2M >10000
BFS(both way) 0.031 64K <2000[/cpp]

Not very precise but we know the efficiency.

[JackDaniels]

I'm stuck . I don't know what's wrong. I've solved this problem with DFS first, then with BFS. WA for both...

PLEASE give me some inputs & outputs.

These are inputs & outputs obtained with my code:

Code: Select all

input
4
01011
110 1
01110
01010
00100
10110
01 11
10111
01001
00000
11111
01111
00 11
00001
00000
11111
01111
00110
00001
000 0

output:
Unsolvable in less than 11 move(s).
Solvable in 7 move(s).
Solvable in 0 move(s).
Solvable in 3 move(s).

[JackDaniels]

Should I post my code? Would that help you helping me? Anyway my code is quite huge, say 250 lines!

[Emilio]

Hello,

my AC program gives the next output:

Code: Select all

Unsolvable in less than 11 move(s).
Unsolvable in less than 11 move(s).
Unsolvable in less than 11 move(s).
Unsolvable in less than 11 move(s).

I solved with simple DFS.

Good luck!

[JackDaniels]

Finally I've got AC.
I've solved the problem using BFS and an optimising function wich counts how many knights aren't on their final place. The runtime was 0.035 seconds... pretty good.
Emilio, are you sure you've got those outputs for my inputs, with your AC program? cause my AC program does not give that answer.

[Emilio]

Emilio, are you sure you've got those outputs for my inputs, with your AC program?

Yes, even I sent my code yesterday another time for confirming that was correct and I obtained AC (You can see my statistics http://acm.uva.es/cgi-bin/OnlineJudge?A ... 45242:Back), I sent it because I tought that was strange the output for my code. My code works fine, I think, it not prune its method is brute force. Maybe your code or mine is incorrect, but are AC

[Sedefcho]

Solvable in 0 move(s).
Solvable in 3 move(s).

These last two answers from JackDaniels are obviously OK
( I mean OK from logical point of view and not from Judge's
points of view ).

Emilio's answers for these two cases are logically wrong.

It's pretty interesting what the Judge Test Inputs are.