## 10890 - Maze

Moderator: Board moderators

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

### 10890 - Maze

I've seen someone's post that say the problem could be solved by BFS && Backtracking within pruning.

In my code I used Backtracking treasure by treasure to find the minimun cost.

But I can't find a way to prune it! That leaded to TLE.
BFS in the same method will get TLE too...

Are there anyone know the method of pruning?
Or another way to deal with this problem?

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
(I assume you want to say DFS instead of BFS.)

The simplest pruning heuristic is to compare the currect cost and the min cost you can get so far. If the current cost is not less than the min cost, you don't need to search any further. I think this heuristic alone is fast enough. But I prune further by estimating the minimum addition cost to reach the goal.
I code, therefore I am.

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan
Thank you a lot!

I always forget the simplest things.

Thank you again!!

Shoou-I Yu
New poster
Posts: 4
Joined: Thu Sep 15, 2005 3:51 pm
I am getting WA on this problem
Could anyone who ACed check the answer for these test cases or provide some critical input?
Thank you

Code: Select all

``````30 30 10
26 28
6 14
26 29
20 21
12 21
13 8
28 12
16 7
18 2
21 14
24 20
26 28
6 24
21 6
2 13
14 8
0 25
24 10
10 20
18 19
7 9
2 25
3 5
29 18
0 13
5 25
27 18
6 14
5 20
13 22
30 30 10
25 16
3 24
11 13
13 18
22 27
12 0
28 16
9 11
4 14
11 28
17 14
19 3
2 7
9 5
10 25
4 14
17 20
28 20
19 4
10 5
6 3
7 3
9 9
27 18
7 18
17 22
10 19
11 25
5 11
28 28
30 30 10
11 1
4 12
26 19
19 20
17 13
0 5
29 8
24 12
4 8
28 9
26 29
18 5
11 22
18 22
12 21
10 29
0 25
13 6
14 20
26 1
10 11
22 15
10 26
16 27
3 19
18 5
25 19
17 11
25 0
11 24
30 30 10
15 28
24 5
9 2
17 26
11 14
6 14
16 2
23 14
11 7
21 25
13 12
19 19
8 25
1 1
26 19
27 8
2 18
9 21
5 28
19 23
22 25
18 19
29 10
20 12
29 18
12 11
26 10
4 10
12 23
4 29
0 0 0
``````
output:

Code: Select all

``````Case 1: 62
Case 2: 128
Case 3: 60
Case 4: 78
``````
I used DFS and BFS to solve this problem, but my DFS version is still too slow, and my BFS version is getting WA.
For the DFS, I used the heuristic mentioned above but still my program is too slow. Any other pruning I should add?
thanks again!

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
My output:

Code: Select all

``````Case 1: 58
Case 2: 58
Case 3: 60
Case 4: 58``````

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
I used backtracking + simple idea.

simple idea:
I want to know is it neccesary to go from
cell (x1,y1) to cell (x2,y2)? The answer is NO in a
following case: if rectangle with corners (x1,y1) and (x2,y2)
contain at least one unvisited cell. And of cource I only care
about cells with treasures, and cut off branches when current
path became equal or longer then minimal found so far.

it works very fast

Shoou-I Yu
New poster
Posts: 4
Joined: Thu Sep 15, 2005 3:51 pm
To kp:

I am sorry I don't really understand what you mean here.
The answer is NO in a
following case: if rectangle with corners (x1,y1) and (x2,y2)
contain at least one unvisited cell.
For this test case, how would your program run?
6 2 2
1 1
4 4

x x x x x E S=start, T=treasure, E=end
x x x x T x
x x x x x x
x x x x x x
x T x x x x
S x x x x x

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Ok, I'll explane it a bit

First I start my backtracking from the cell (0,0).

Each step do the following:

Code: Select all

``````
if curpath+dist(curcell,END)>= minpath then exit;

v[curcell] = 1; // mark current cell as visited

for (all U = unvisited cells with treasures) do begin
// if we just move here to the next reccurcive step
// then we get Time Limit Exceeded that's why we
// will do additional check, and it may turn out that
// we don't actually need to do this step

flag = true; // by default assume we need to go to U
for (all V = unvisited cells with treasures) do // (*)
if (U<>V) and (V situated inside rectangle with corners U, curcell) then
begin
flag = false; // Good, we don't need to go to U
break;
end;
if flag then begin
curpath = curpath + dist(curcell,U)
treasures = treasures + (number of treasures in a cell U)
(make reccurssive call of the same proc);
end;
end;

v[curcell] = 1; // unmark it (full search)
``````
The idea is simple: why should we go to the cell U if
there is an intermediate cell thru which we better go first.

(*): I used preprocessing to store the list of "intermediate"
cells to each pair (U,V) so during the check I actually
scan this list until the unvisited cell is found.

6 2 2
1 1
4 4

x x x x x E S=start, T=treasure, E=end
x x x x T x
x x x x x x
x x x x x x
x T x x x x
S x x x x x

My program will do the following:

Code: Select all

``````go to (1,1); treasures=1; path=2;
go to (4,4); treasures=2; path=8;
go to E; path=10;

NOT go to (4,4); treasures=1; path=8;
// We dont need to go from (0,0) to (4,4) because
// we better go to the (1,1) first! (then we can go to (4,4))
END
``````

Shoou-I Yu
New poster
Posts: 4
Joined: Thu Sep 15, 2005 3:51 pm
cho: thanks for the answers to the test data

kp: thanks for the simple but excellent and efficient idea
got AC now

thanks again!

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Hello..~
I just followed the kp's idea.. but still getting TLE..
Any suggestions..?

Code: Select all

``````code removed
``````
Last edited by helloneo on Wed Sep 27, 2006 10:32 am, edited 1 time in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
helloneo wrote:Hello..~
I just followed the kp's idea.. but still getting TLE..
Any suggestions..?
I think that map is too slow. Very simple pruning will get AC for this problem. We have found a solution when the number of visited trasures==s and compute the remaining cost of the path. Prune if the remaining cost + visited cost >= currently best solution. I used the same kind of technique for solving TSP.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
sclo wrote: I think that map is too slow. Very simple pruning will get AC for this problem. We have found a solution when the number of visited trasures==s and compute the remaining cost of the path. Prune if the remaining cost + visited cost >= currently best solution. I used the same kind of technique for solving TSP.
Thanks a lot ..
I'm so supprised.. The simple pruning strategy saved a lot of running time..

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### wa

Hi,

I get wa. Anything wrong with a simple BFS approach?
Thanks

Code: Select all

``````Found a bug
``````

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm