Page 1 of 7

### 929 - Number Maze

Posted: Sun Oct 29, 2006 10:45 am
I m using bfs with priority queue(STL). But I m getting TLE. Is there any better idea?

Posted: Sun Oct 29, 2006 11:07 am
That's the right approach for general graphs, but Ruben did a good job by exploiting the properties of this specific graph and letting the standard solutions get TLE. Think about it.

Posted: Sun Oct 29, 2006 8:07 pm
Djkstra + priority queue(not STL) could solve it with 4 ~ 6 sec.
STL is too slow.

----
sory for my poor english

Posted: Mon Oct 30, 2006 3:26 pm
Thank you both. I have got it Accepted.

### ok, let's discuss it here

Posted: Sat Nov 11, 2006 7:38 pm
Actually, thanks for your help. I just didn't cheked up and left (oops), but it didn't affect to MLE.

Now it looks lile:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define N 1000
#define LONG_MAX 2147483647
#define MAX 10

class Queue
{
public:
int x,y;
Queue *next;
Queue *prev;
Queue *last;
Queue *first;
int numel;
public:
Queue()
{
numel = 0;
first = this;
next = this;
prev = this;
last = this;
};

void Push(int x, int y) // a``````

Posted: Sat Nov 11, 2006 8:21 pm
Even though you got a way out of MLE, i think you'll get TLE.
I tried your code with STL Queue, and got TLE. This is the code.

Code: Select all

``````#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;

#define N 1000

char maze[N][N];
long v[N][N];
int cases, m, n;
long count;

typedef pair<int, int> Point;

int main()
{
scanf("%d", &cases);
for (int i=0; i<cases; i++)
{
queue<Point> q;
scanf("%d%d",&n,&m);
count = 0;
for (int j=0;j<n;j++)
for (int k=0;k<m;k++)
{
scanf("%d", &maze[j][k]);
v[j][k] = LONG_MAX ;
}
v[0][0] = maze[0][0];
q.push(Point(0,0));

while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
count--;
// a``````

Posted: Sun Nov 12, 2006 12:07 pm
rio wrote:Even though you got a way out of MLE, i think you'll get TLE.
I tried your code with STL Queue, and got TLE. This is the code.

In your code, same places could be expanded (queued) several times.
And it is determing min-distance for all the places.
Actually, a used 10 queues in order to not waste time searching for min distance. So a could examine these 10 queues and extract the min distance in constant time.
But you're right about queuing the same element many times. I'll fix it. Thanks

### now WA

Posted: Sun Nov 12, 2006 12:34 pm
I fixed some things, and now I get WA not MLE, now the code looks like this:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define N 1000
#define LONG_MAX 2147483647
#define MAX 10

class Queue
{
public:
int x,y;
Queue *next;
Queue *prev;
Queue *last;
Queue *first;
int numel;
public:
Queue()
{
numel = 0;
first = this;
next = this;
prev = this;
last = this;
};

void Push(int x, int y) // a``````

Posted: Sun Nov 12, 2006 1:50 pm
The algorithm seems to be wrong. Your approuch (v[x][y] = -1) is not right.
To see where your algorithm is wrong, consider this case.

Code: Select all

``````1
4
5
0 2 1 9 9
1 9 1 0 0
1 1 1 9 0
9 9 9 9 0``````

----
Sory for my poor English.

Posted: Sun Nov 26, 2006 12:43 pm
I got AC using 10 STL queues to simulate dijkstra, but my time of 8.842 secs is quite bad. I think if you implement dijkstra using your own binary heap instead of STL priority_queue, it will run even faster.

Posted: Sun Nov 26, 2006 2:23 pm
Implementing priority_queue with 10 queues(not STL) is what I did to get 0.936 secs.
It is much faster than using the heap (using heap(not STL) took 3 ~ 4 secs).
It enables queueing/taking out element with O(1).

Posted: Mon Nov 27, 2006 11:10 pm
You can get AC with only one priority_queue(STL). Although I have got AC in 9.641 secs.
You must optimize your code to get AC with only one priority_queue(STL)
Ah, on the other hand, I like the idea of 10 priority queues. Maybe I'll try it later

Posted: Fri Dec 01, 2006 2:17 am
I didnt solve this problem yet (I'm not familiar with priority_queue's non STL yet), but I was thinking in dijkstra with a heap...

Could you explain how you implement a priority queue with 10 queues ?
Or just give me a link to somewhere that explains it ?

thanks

Posted: Fri Dec 01, 2006 3:02 am
Little hint for implementing a priority queue with 10 queues :

If you queued out a element from the i th queue, and expand it, and its adjacent element had value '6', you just need to queue it in (i + 6)%10 th queue.
In this way, you don't need to queue distance information.
(It's like a ring, so I used "ring_queue" for the queues variable name)

----
Sory for my poor English.

Posted: Fri Dec 01, 2006 2:16 pm
rio wrote:Little hint for implementing a priority queue with 10 queues :

If you queued out a element from the i th queue, and expand it, and its adjacent element had value '6', you just need to queue it in (i + 6)%10 th queue.
In this way, you don't need to queue distance information.
(It's like a ring, so I used "ring_queue" for the queues variable name)
Thank you Rio, i got it Very nice ideia indeed. I'll try it out