572 - Oil Deposits

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

Moderator: Board moderators

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

572 - Oil Deposits

Post by pavelph » Sat Jan 31, 2004 6:43 pm

I use algorithm that
1) read input to

Code: Select all

g: array [1 .. n, 1 .. n] of boolean
where g[i, j]=true if [i, j]='@'.
2) for this problem graph consists of nodes(=g) and two nodes [i1, j1] & [i2, j2] joined if |i1-12|<=1 and |j1-j2|<=1.
3) for this graph I start BFS.

I think that it is right algorithm. But I get WA again and again.
Here my code:
[pascal]program acm572; { Oil Deposits }
____DELETED________
[/pascal]
Last edited by pavelph on Sun Feb 01, 2004 4:27 pm, edited 1 time in total.

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k » Sat Jan 31, 2004 7:27 pm

Hi,

I'm not familiar with pascal but as far as I beleive it's a straight forward DFS/BFS problem. in DFS/BFS u should notice that u have eight position in next step. suppose, u called BFS/DFS at Oil[4][4] position .. then ur next eight queue position would be Oil[4][3],Oil[3][3],Oil[5][3],Oil[3][4],Oil[5][4], Oil[4][5], Oil[3][5] and Oil[5][5]. U have to consider vertical,horizontal and diagonal cases. If u care these i don't thik that there should be any more problem unless u made silly mistakes. there is no special input for this program I believe.

best of luck

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph » Sat Jan 31, 2004 11:06 pm

Thank you. As I understand you, my prog work like you say. Maybe I realy have some bug. But it is very hard to find it becouse program works well on all my inputs :oops:

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Feb 01, 2004 9:42 am

You use n as maximum for both dimensions in your procedures DFSwork() and DFS(). You should use m for the first and n for the second.

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph » Sun Feb 01, 2004 4:23 pm

Thank you, little joey. It was realy silly mistake.
Now I`ve got AC :)

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

512 - Time Limit Exceeded

Post by txandi » Sat Mar 06, 2004 1:35 am

I can't understand... in my pc my program works fast, it has no problem in solving a 100x100 matrix. Surprisingly it doen't seem be as fast for the judge-online.

What can I do? If checked all "while"'s and "for"'s... and I'm sure they are ok.

Any idea?

Thanks in advance

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Sat Mar 06, 2004 4:49 pm

Sorry... The problem that doesn't work is 572, not 512!

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

572 WA

Post by helmet » Sat Jun 26, 2004 10:55 am

Im using a useless version and union-find problem...can anyone find error?

Code: Select all

[cpp]
AC[/cpp]
thanks in advance
Last edited by helmet on Mon Jun 28, 2004 7:40 am, edited 1 time in total.
Just another brick in the wall...

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Sun Jun 27, 2004 10:19 am

consider this input it has only 1 oil well your program gives 2

5 10
**@****@**
***@**@***
****@@****
*****@****
*****@****

hope this helps :)
if u can think of it .. u can do it in software.

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

Thanks

Post by helmet » Mon Jun 28, 2004 7:39 am

Dude....


My mistake was I used j<m-1 instead of j<n-1....


Thanks Jagadish...
Just another brick in the wall...

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

572(oil deposit) TRICKY test case for you :-)

Post by Ali Arman Tamal » Tue Feb 15, 2005 11:58 am

INPUT:

12 25
*****************@*******
***************@@*@******
**************@****@*****
************@@******@@***
***********@**********@**
***********@***********@*
*********@@***@*@*****@**
*******@@****@*@*@**@@***
******@*****@*****@@*****
*******@**@@*************
*******@*@***************
********@****************

OUTPUT:

1


INPUT:

12 25
*****************@*******
***************@@*@******
**************@****@*****
************@@******@@***
***********@**********@**
***********@***********@*
*********@@***@*@*****@**
*******@@****@***@**@@***
******@*****@*****@@*****
*******@**@@*************
*******@*@***************
********@****************

OUTPUT:

1


INPUT:

12 25
*************************
***************@@*@******
**************@****@*****
************@@******@@***
***********@**********@**
***********@***********@*
*********@@***@*@*****@**
*******@@****@***@**@@***
******@*****@*****@@*****
*******@**@@*************
*******@*@***************
********@****************

OUTPUT:

2

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

572 WA :-(

Post by smilitude » Thu Jan 12, 2006 10:42 am

i thought this was an easy flood fill

Code: Select all

DELETED

fahim
#include <smile.h>

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Jan 12, 2006 11:08 am

Try this input:

Code: Select all

1 8
@*******
0 0

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Jan 12, 2006 11:24 am

err... whatta shame! :oops:
thanks mf, i got ac!
fahim
#include <smile.h>

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

WA!!!

Post by soddy » Sun Jun 10, 2007 2:58 am

I have tried every test case on forum...n getting right answer still my code is giving WA...cant find any bug....can some one help

Code: Select all

Code deleted
Last edited by soddy on Sun Jun 10, 2007 3:16 am, edited 2 times in total.

Post Reply

Return to “Volume 5 (500-599)”