929 - Number Maze

[SRX]

oops ........
if you read input with "scanf" , then it use 3 secs to read ,
so those who got tle shoud find a fast input way ...

[mogers]

oops ........
if you read input with "scanf" , then it use 3 secs to read ,
so those who got tle shoud find a fast input way ...

by the way, you could tell us how

[SRX]

oops ........
if you read input with "scanf" , then it use 3 secs to read ,
so those who got tle shoud find a fast input way ...

by the way, you could tell us how

ok , if your language is C or C++ , then "gets" will help you

[mogers]

I didnt try gets because the compiler used in Portugal's constests, doesn't allow gets, we may use fgets ...
I've changed scanf to getchar and saw the diference very nice

I'm having TLE... unfortunatly i dont have time to debug right now...
I use 10 non STL queues but I'm not sure about their MAX Size (i guess that my problem is the size of the array - defined as 999)

How do you implement Queues ? I use an array. I think that a linked list saves memory but is slower.

[rio]

Using getchar() (and scanf()) can't reduce the overhead of function call (maximaly it is called 999x999 times).
I think SRX wanted to say like this code (It doesn't matter weither you use gets() or fgets())

Code: Select all

char buf[BUF_SIZE];
char *c;
for (i = 0; i < row; ++i) {
   fgets(buf, sizeof(buf), stdin);
   c = buf;
   for (j = 0; j < col; ++j) {
      while (*c == ' ') ++c;
      maze[i][j] = *c++ - '0';
   }
}

I use 10 non STL queues but I'm not sure about their MAX Size (i guess that my problem is the size of the array - defined as 999)

I think size 999 is too small.

How do you implement Queues ? I use an array. I think that a linked list saves memory but is slower.

I used an array.

(I hope this wouldn't be a spoiler. If it is, tell me. I'll edit my post)
----
Sory for my poor English.

[mogers]

I had

Code: Select all

for (i=0;i<rows;i++) {
     for (j=0;j<cols;j++)
     {
          maze[i][j] = getchar();
          maze[i][j] -= '0';               
          getchar();           /* read   ' ' or '\n'   */
     }
}

Assuming that the input doesn't have more spaces... I forgot about the overhead

I changed the size and still got tle... i have a bug somewhere. Now I must study for exam

thank you all

[mogers]

Finaly I had some time to problem solving

I was geting TLE because i forgot the smallest case (maze 1x1).
Meanwhile, my Dijkstra with a heap not STL was accepted in 8.645 secs
With 10 queue's I got accepted in 1.213 secs ... amazing

In this way, you don't need to queue distance information.

I couldn't avoid queueing the current distance. I think thats why I have ~twice your memory

It is much faster than using the heap (using heap(not STL) took 3 ~ 4 secs).

Someday, I'll be able to achieve your runtimes Rio... my dijkstra or queue's version take (+/-) twice your time. you're the man

thanks again

[FAQ]

I still got a lot of WAs, please help me some tests thanks

[abhiramn]

Why is this approach wrong.

Code: Select all

#include<stdio.h>
int maze[1000][1000],cum[1000][1000];
int main()
{
	int i,j,test,m,n;
	scanf("%d",&test);
	++test;
	while(--test)
	{
		scanf("%d%d",&m,&n);
		for(i=0;i<m;++i)
			for(j=0;j<n;scanf("%d",&maze[i][j]),++j);
		cum[0][0]=maze[0][0];
		for(i=1;i<n;cum[0][i]=cum[0][i-1]+maze[0][i],++i);
		for(i=1;i<m;cum[i][0]=cum[i-1][0]+maze[i][0],++i);
		for(i=1;i<m;++i)
			for(j=1;j<n;++j)
				cum[i][j]=(cum[i-1][j]<cum[i][j-1]?cum[i-1][j]:cum[i][j-1])+maze[i][j];
		printf("%d\n",cum[m-1][n-1]);
	}
	return 0;
}

[rio]

Consider this case:

Code: Select all

1
4
5
0 9 9 9 9
0 9 0 0 0
0 0 0 9 0
9 9 9 9 0

The answer should be 0, but your codes output 9.
----
Rio

[abhiramn]

Thanks a ton. Terribly stupid mistake. That code is nonsense.
Abhiram.

[mmonish]

I used bfs with heap but i am getting WA.
Please anyone give me some test case.

[ayeshapakhi]

are u sure that ur heap is working properly?

[mmonish]

>>ayeshapakhi
Thanks for ur reply. I think my heap is working properly.

anyone please give me some test case.

[ayeshapakhi]

to monish