Page **1** of **1**

### 10890 - Maze

Posted: **Wed Aug 31, 2005 3:19 pm**

by **polone**

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?

Posted: **Wed Aug 31, 2005 6:19 pm**

by **Cho**

(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.

Posted: **Thu Sep 01, 2005 7:05 am**

by **polone**

Thank you a lot!

I always forget the simplest things.

I'll try it again with your advice.

Thank you again!!

Posted: **Sun Sep 18, 2005 10:07 am**

by **Shoou-I Yu**

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!

Posted: **Sun Sep 18, 2005 1:58 pm**

by **Cho**

My output:

Code: Select all

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

Posted: **Sun Sep 18, 2005 11:30 pm**

by **kp**

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

Posted: **Mon Sep 19, 2005 5:26 am**

by **Shoou-I Yu**

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

thank you for your patience

Posted: **Mon Sep 19, 2005 7:49 am**

by **kp**

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.

About your example:

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

Posted: **Mon Sep 19, 2005 3:22 pm**

by **Shoou-I Yu**

cho: thanks for the answers to the test data

kp: thanks for the simple but excellent and efficient idea

got AC now

thanks again!

Posted: **Tue Sep 26, 2006 4:21 pm**

by **helloneo**

Hello..~

I just followed the kp's idea.. but still getting TLE..

Any suggestions..?

Posted: **Tue Sep 26, 2006 7:25 pm**

by **sclo**

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.

Posted: **Wed Sep 27, 2006 10:35 am**

by **helloneo**

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

### wa

Posted: **Tue Nov 20, 2007 1:06 am**

by **baodog**

Hi,

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

Thanks

### Re: 10890 - Maze

Posted: **Tue Dec 29, 2009 10:31 pm**

by **Articuno**

Can anyone explain why this idea is not working?

My idea was very simple. I used bfs.

1. I use a three dimensional array such as cost[number of treasures collected yet][row][column];

2. Visit every position and if there is a treasure in that position yet to be collected... collect it and if possible update the cost array.

3. Finally cost[s][n-1][n-1] is the answer.

Can anyone say why this approach is not working....... well I am not good in graph.