929 - Number Maze
Moderator: Board moderators
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
HomePage
- little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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:
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
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.
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
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.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.
But you're right about queuing the same element many times. I'll fix it. Thanks
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
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.
Your code outputs 5 (the answer is 4).
----
Sory for my poor English.
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.
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.
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.
Thank you Rio, i got itrio 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)

