10890 - Maze

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10890 - Maze

Post by polone » Wed Aug 31, 2005 3:19 pm

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?

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

Post by Cho » Wed Aug 31, 2005 6:19 pm

(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

Post by polone » Thu Sep 01, 2005 7:05 am

Thank you a lot!

I always forget the simplest things.

I'll try it again with your advice.

Thank you again!!

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

Post by Shoou-I Yu » Sun Sep 18, 2005 10:07 am

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!

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

Post by Cho » Sun Sep 18, 2005 1:58 pm

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

Post by kp » Sun Sep 18, 2005 11:30 pm

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

Post by Shoou-I Yu » Mon Sep 19, 2005 5:26 am

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

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Mon Sep 19, 2005 7:49 am

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

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

Post by Shoou-I Yu » Mon Sep 19, 2005 3:22 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! :D

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Sep 26, 2006 4:21 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Sep 26, 2006 7:25 pm

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

Post by helloneo » Wed Sep 27, 2006 10:35 am

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

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

wa

Post by baodog » Tue Nov 20, 2007 1:06 am

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
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10890 - Maze

Post by Articuno » Tue Dec 29, 2009 10:31 pm

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.
May be tomorrow is a better day............ :)

Post Reply

Return to “Volume 108 (10800-10899)”