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

### 572 - Oil Deposits

Posted: **Sat Jan 31, 2004 6:43 pm**

by **pavelph**

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]

Posted: **Sat Jan 31, 2004 7:27 pm**

by **prince56k**

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

Posted: **Sat Jan 31, 2004 11:06 pm**

by **pavelph**

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

Posted: **Sun Feb 01, 2004 9:42 am**

by **little joey**

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.

Posted: **Sun Feb 01, 2004 4:23 pm**

by **pavelph**

Thank you, little joey. It was realy silly mistake.

Now I`ve got AC

### 512 - Time Limit Exceeded

Posted: **Sat Mar 06, 2004 1:35 am**

by **txandi**

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

Posted: **Sat Mar 06, 2004 4:49 pm**

by **txandi**

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

### 572 WA

Posted: **Sat Jun 26, 2004 10:55 am**

by **helmet**

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

thanks in advance

Posted: **Sun Jun 27, 2004 10:19 am**

by **jagadish**

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

5 10

**@****@**

***@**@***

****@@****

*****@****

*****@****

hope this helps

### Thanks

Posted: **Mon Jun 28, 2004 7:39 am**

by **helmet**

Dude....

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

Thanks Jagadish...

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

Posted: **Tue Feb 15, 2005 11:58 am**

by **Ali Arman Tamal**

INPUT:

12 25

*****************@*******

***************@@*@******

**************@****@*****

************@@******@@***

***********@**********@**

***********@***********@*

*********@@***@*@*****@**

*******@@****@*@*@**@@***

******@*****@*****@@*****

*******@**@@*************

*******@*@***************

********@****************

OUTPUT:

1

INPUT:

12 25

*****************@*******

***************@@*@******

**************@****@*****

************@@******@@***

***********@**********@**

***********@***********@*

*********@@***@*@*****@**

*******@@****@***@**@@***

******@*****@*****@@*****

*******@**@@*************

*******@*@***************

********@****************

OUTPUT:

1

INPUT:

12 25

*************************

***************@@*@******

**************@****@*****

************@@******@@***

***********@**********@**

***********@***********@*

*********@@***@*@*****@**

*******@@****@***@**@@***

******@*****@*****@@*****

*******@**@@*************

*******@*@***************

********@****************

OUTPUT:

2

### 572 WA :-(

Posted: **Thu Jan 12, 2006 10:42 am**

by **smilitude**

i thought this was an easy flood fill

Posted: **Thu Jan 12, 2006 11:08 am**

by **mf**

Posted: **Thu Jan 12, 2006 11:24 am**

by **smilitude**

err... whatta shame!

thanks mf, i got ac!

### WA!!!

Posted: **Sun Jun 10, 2007 2:58 am**

by **soddy**

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