10653 - Bombs! NO they are Mines!!

Moderator: Board moderators

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

10653 - Bombs! NO they are Mines!!

I had 15+ RTE during the contest and I still don't get it, please try to find my error, or just try to give me a hint. This is my code:

[cpp]
#include <stdio.h>

int f1, c1, f2, c2, fil, col, mat[1000][1000];

{
int n1, n2, f, c;

for (int i = 0; i <= fil - 1; i++)
for (int j = 0; j <= col - 1; j++)
mat[j] = 0;

scanf("%d", &n1);

for (int i = 1; i <= n1; i++) {

scanf("%d %d", &f, &n2);

for (int j = 1; j <= n2; j++) {

scanf("%d", &c);
mat[f][c] = -1;
}
}

scanf("%d %d", &f1, &c1);
scanf("%d %d", &f2, &c2);
}

void MakeSolu()
{
const int movfil[4] = {-1, 0, 1, 0};
const int movcol[4] = {0, 1, 0, -1};
int ax[2][1000000], ay[2][1000000], canta = 1, cantv, mov = 0, p = 0;
bool fin = false;

ax[0][0] = f1;
ay[0][0] = c1;
mat[f1][c1] = 1;

do {

p++;
cantv = 0;

for (int i = 0; i <= canta - 1; i++)
for (int j = 0; j <= 3; j++) {

int ft = ax[mov] + movfil[j];
int ct = ay[mov] + movcol[j];

if (ft >= 0 && ft < fil && ct >= 0 && ct < col)
if (mat[ft][ct] == 0) {

mat[ft][ct] = p;
ax[mov ^ 1][cantv] = ft;
ay[mov ^ 1][cantv] = ct;
cantv++;

if (ft == f2 && ct == c2)
fin = true;
}
}

mov ^= 1;
canta = cantv;

}
while (canta != 0 && !fin);

printf("%d\n", mat[f2][c2]);
}

int main()
{
scanf("%d %d", &fil, &col);

while (fil || col) {

MakeSolu();
scanf("%d %d", &fil, &col);
}

return 0;
}
[/cpp]

Any help would be appreciated

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
[c]int ax[2][1000000], ay[2][1000000], canta = 1, cantv, mov = 0, p = 0;[/c]
The judge cannot allocate 16 MB of memory onto the stack, which is probably the reason for your RTE.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Thanks a lot UFP2161, that was really my mistake, I did not know that

I feel bad since I did not solve the task during the contest because of this stupid error.

Yandry.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
I used the following structure for my Point:

typedef struct P {
int x,y;
int z;
};

(where z means its deepness in the search).... then i do a simple BFS...

altough i did get AC, it ran during 3.4 secs.... only cause i use a recycling macro as follows:

#define n() (recC!=0 ? rec[--recC] : new P() );

otherwise it gives MLE.... how did you guys solve it in less time? u usually dont use a struct? just a int[3]?

thanks...

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
I just do a simple BFS but the points from where i go left,rigth,up or down i remember in 2 arrays(one for column,and the second for row).And update my arrays on every steps. I got AC during 1.5..sc .
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

don't get it

I used BFS and get it AC in 4.74 seconds...

Shouldn't straight forward BFS pass the time limit or is there any tricks and trade in this problem..

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
No, I also use straight forward bfs and get AC in 1.4 seconds. So I guess it's all in the implementation details. Does your program terminate the bfs as soon as it knows the answer? That can be a time saver.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

i think so

yeah,

I terminated the BFS function when the destination is reached..

btw I used STL queue to implement BFS... could that be a reason for the slower time.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Well, that can easily be the case. I don't know how STLs queue is implemented, but if it does memory (de)allocation on every enqueue and dequeue, it will spend a lot of time on that. I use a static array with 1Meg elements to implement the queue, with enqueue/dequeue functions inline.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
I am also using stls queue.... took it out and now AC in 01.773 hehuehuahuea..... incredible... their queue sucks without optimization

from 3.4 -> 1.773

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Since the judge doesn't use any optimisation flags, using STL containers is noticably slower than "doing it yourself". Otherwise, there shouldn't be that much of a difference.

Terminating when destination is reached rarely gives that kind of speed increase. For this problem, my solution (a straightforward impl using STL queues) was about 5% faster (3.775 s instead of 4.012 s) when I terminated upon reaching destination instead of doing the full bfs.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
Hello Per Austrin,

1000 1000
0
0 0
0 1

(I forgot the problem description, so forgive me if there is something wrong)....

This is a 1000x1000 map without any mines...... if you do a bfs without stoping it shall go through each and every vertex. While if you skip it when you reach the end (deep=1) you get it done

It could have been worse if the map would have been bigger..... altough I am sure that bfs is fast cause it only visits once each vertex (1000x1000 visits)

Guilherme Silveira

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Yeah, sure, but that's not what typical judge input looks like, which is what I was talking about (though perhaps I was a bit unclear).

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
i lost one point (tle) at south americans contest last year due to a problem like this....

i got what you mean...

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

AC

Removed STL - and got it AC in 3.36 seconds...
the significant part is that this problem had a time limit of 4 seconds in the real time contest.. it seems that the usage of STL is quite risky.

around 1.5 seconds was reduced by the omission of it - a significant time, I guess.

But, how did some people get AC under 1 second. Is there any different way other than BFS.