929 - Number Maze

[Jan]

I m using bfs with priority queue(STL). But I m getting TLE. Is there any better idea?

[little joey]

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.

[rio]

Djkstra + priority queue(not STL) could solve it with 4 ~ 6 sec.
STL is too slow.

----
sory for my poor english

[Jan]

Thank you both. I have got it Accepted.

[nut]

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

[rio]

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

[nut]

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

[nut]

I fixed some things, and now I get WA not MLE, now the code looks like this:
[code]
#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

[rio]

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

Your code outputs 5 (the answer is 4).

----
Sory for my poor English.

[sclo]

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.

[rio]

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

[Emilio]

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

[mogers]

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

[rio]

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.

[mogers]

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