## 10653 - Bombs! NO they are Mines!!

Moderator: Board moderators

### 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[i][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][i] + movfil[j];
int ct = ay[mov][i] + 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
neno_uci
Experienced poster

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

[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.

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

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.
neno_uci
Experienced poster

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

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...
technobug
Learning poster

Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien

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
Eduard
Experienced poster

Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 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..

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

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.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 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.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

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.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
technobug
Learning poster

Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien

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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
technobug
Learning poster

Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien

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).
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

i lost one point (tle) at south americans contest last year due to a problem like this....

i got what you mean...
technobug
Learning poster

Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien

### 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.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

Next