## 851 - Maze

**Moderator:** Board moderators

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
```

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
```

### 851 Maze II - IDA*?

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.

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.

Solving problem is a no easy task...

### Re: 851 Maze II - IDA*?

In heuristic searching, the estimate function h(x) must be an under-estimate.Hackson wrote:My way to make estimation is:

h(x)

Summation of all the 'people' that makes the shortest distance with any goal.

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

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
The above gives TLE...

Please, give us your opinion.

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(distThus 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:

/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 :) `

Please, give us your opinion.

Last edited by serur on Sat Apr 14, 2012 3:23 pm, edited 2 times in total.

*If there is ever a war between men and machines, it is easy to guess who will start it*(c) Arthur Clarke

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.

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.

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.

*If there is ever a war between men and machines, it is easy to guess who will start it*(c) Arthur Clarke

Code: Select all

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

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.

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.

Last edited by serur on Tue May 30, 2006 3:30 pm, edited 1 time in total.

*If there is ever a war between men and machines, it is easy to guess who will start it*(c) Arthur Clarke

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)
```

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", ...).

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,

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!

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)
```

Thank you again.

Keep posting!

*If there is ever a war between men and machines, it is easy to guess who will start it*(c) Arthur Clarke