## 929 - Number Maze

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### 929 - Number Maze

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Djkstra + priority queue(not STL) could solve it with 4 ~ 6 sec.
STL is too slow.

----
sory for my poor english

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Thank you both. I have got it Accepted.
Ami ekhono shopno dekhi...
HomePage

nut
New poster
Posts: 4
Joined: Sat Nov 11, 2006 3:43 pm

### ok, let's discuss it here

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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

nut
New poster
Posts: 4
Joined: Sat Nov 11, 2006 3:43 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

nut
New poster
Posts: 4
Joined: Sat Nov 11, 2006 3:43 pm

### now WA

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal
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