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 :D

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! :D

Posted: Tue Sep 26, 2006 4:21 pm
by helloneo
Hello..~
I just followed the kp's idea.. but still getting TLE..
Any suggestions..?

Code: Select all

code removed

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

wa

Posted: Tue Nov 20, 2007 1:06 am
by baodog
Hi,

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

Code: Select all

Found a bug

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.