851 - Maze

[DJWS]

I got Accpeted just before.
In this problem, using IDA* can save us a lot of memory and improve the speed.

--
DJWS, a newbie in programming

[artem]

This output for tests above

Code: Select all

west
west
south
south
east
east
south

west
west
north
north
east
east
east

west
west
west
east
east
east

east
east
west
south
south
east
east

south
south
west
west
south

west
south
west
west
south

south
west
south

east
west
west
west

north
south

north
west
west
north

east
south
south

south
west
east
east

south
east
west
north

north
south

east
south
east
south
south

south
south
east
east
west
south

south
south
south

east
east
west
south


north
north
north

And this another intersting input:

Code: Select all

1
8
########
#......#
#......#
#......#
#....#.#
#..#..##
#...#..#
######.#

and output

west
north
west
west
west
north
west
east
east
south
south
south
east
south
east
south
east
south

[Hackson]

I am struggling in this problem using IDA*.
I tried different ways to estimate the cost and heuristics functions but I didnot success.
My way to make estimation is:
g(x)
should be an addition of the parent node's g(x) with number of possible moves at this stage. for example, at certain stage, 3 'people' can move in one direction, then the g(x) = previous g(x) + 3

h(x)
Summation of all the 'people' that makes the shortest distance with any goal.

I am not sure what the admissible function is, but mine seems (and I tested) not the admissible one......
Is there any better estimation of f(x)? I am not eligible enough to obtain one for myself.

[DJWS]

My way to make estimation is:
h(x)
Summation of all the 'people' that makes the shortest distance with any goal.

In heuristic searching, the estimate function h(x) must be an under-estimate.

According to this problem, more than 1 people may be able to escape at each step. So we can not estimate the steps with summation from all people. It's maybe an over-estimate.

I have send a message to you.
Good luck.
--
DJWS, a newbie in programming

[serur]

I was thinking to myself it's a very hard problem, for only 85 of us all solved it and mostly with heaps of time... Hm...

[serur]

Hi fellows!

What do you think of 851-"Maze"?
I tried to solve it with IDA*.

My approach:
1) for every free position (i,j) I find (with bfs) distance[j] to the nearest escape-cell.
Thus I obtain admissible estimate - the solution is in the depth >= max(dist[j]).
2)if there is no solution in the depth D, then I increase D...

Now let the code speak for itself:

/

Code: Select all

 bad code is cut :) 

The above gives TLE...
Please, give us your opinion.

[mf]

Your code implements just iterative-deepening DFS, not IDA*.
In a proper IDA* you should calculate heuristic function at each visited state.
If g is the distance to the current state ("depth" of it), h is the value of (non-overestimating!) heuristic for this state, then the distance from source to goal through this state is at least g+h. You stop recursion when this value exceeds current limit. The limit for the next iteration of IDA* is the minimum of these g+h's.

You can represent states more efficiently, if you just keep 64 bits (fits in a 'long long' type); 1 bit for each unblocked location, which indicate whether there may be a person there, for some starting position. Initially all bits are 1's for unblocked locations. For each move just shift the 1's left, up, down or right, except near the walls. This can be very efficiently implemented with binary operators and shifts.

[serur]

Hi mf!

I beg you pardon for inaccuracy.
When deciding which move to make next -

north,east,south or west - we must analyze

all these possibilities by means of function

f=(steps made so far ) + (bfs-distance from

current position of the prisoner to

escape-cell) for each prisoner.
If for some prisoner this f()-evalutaion

gets beyond the depth that's contemplated in

the current iteration of IDA*, we prune the

branch..

Now I see all the advantages of your idea

about long long, though implementation is

not clear to me as yet... (also, Visual C++

doesn't support long long, but this makes

no matter after all)

Thank you, due to you I've grasped the

situation better now.

[serur]

Hi mf!

I need one more hint about states and long long.

Thank you

[mf]

You can use the following code, it should work both for MSVC and gcc:

Code: Select all

/* Declares 64-bit unsigned integer type 'uint64' */
#ifdef _MSC_VER
typedef unsigned __int64 uint64;
#else
typedef unsigned long long uint64;
#endif

[serur]

Hi mf!

Thank you so much for your help.

This is my next attempt, which gives TLE.
It looks very awkward, and it's enormous, I know, but I'll appreciate your opinion.



Well, I think I'm on the right direction, so I'll try to improve my IDA*, and tweak something...

Thank you.

[mf]

Hi. A few points:

1)
In an expression like 1 << k, the result is a 32-bit integer by default (when both operands are of type 'int', C standard demands 'int' as the result type).
You have to tell the compiler explicitely that you want a 64-bit shift.

For gcc it's sufficient to append suffix ULL to 1: 1ULL << k.
In MSVC, probably this will work: ((uint64)1) << k.

2)
I didn't at all mean to use 64-bit ints just instead of arrays.
Use all the power of bitwise operators, THAT is what makes them perfect for this problem.

In my solution I have these bitmaps:
all_inner: indicates which of the cells are strictly inside the map (not on the boundary or outside)
walls: which cells of the map are blocked by walls,
inner: inner = (~walls) & all_inner;
Each number represent 8x8 map; a cell (row, col) corresponds to bit 1<<(8*row+col).

Performing a move from a state s can be then done in this simple way:

Code: Select all

north: s' = ((s >> 8) | (s & (walls << 8))) & inner)
south: s' = ((s << 8) | (s & (walls >> 8))) & inner)
west:  s' = ((s >> 1) | (s & (walls << 1))) & inner)
east:  s' = ((s << 1) | (s & (walls >> 1))) & inner)

3)
I don't think it makes much sense to use everywhere short's instead of int's.
Judge runs on a modern processor (not on some prehistoric 8086), you have lots of memory (100Mb+), and time (90 seconds).
That should be more than enough for IDA*. My own solution used BFS, much slower than IDA*, and it manages to finish in just 50 seconds.

Also, you have a bug: short's should be parsed with scanf("%hd", ...).

[serur]

Hi mf!

Congratulations - you hold now your proper place in the ranklist
I also got AC (of course one is hardly surprised )
Thank you so much for your help - I don't know how I'd have done without your ingenius ideas.

Also,

Code: Select all

south: s' = (((s<< 8) | (s & (walls>> 8))) & inner) 
north: s' = (((s >> 8) | (s & (walls << 8))) & inner) 
east:  s' = (((s << 1) | (s & (walls >>1))) & inner) 
west:  s' = (((s >>1) | (s & (walls << 1))) & inner) 

Now that you set better standard for this problem I dare say time limit (90 sec) will be adjusted also.

Thank you again.

Keep posting!

[mf]

Oh, I've just "upgraded" my older solution from BFS to IDA*.
Literally it became 500 times faster (50sec -> 0.1s), I'm surprised myself...

[serur]

Hi!

you are quite prolific today
I see you have AC 358 - "Cow". With bisection I got WA so many times