## 929 - Number Maze

Moderator: Board moderators

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### Why TLE???

i use priority queue and BFS. but i can not understand why getting TLE everytime????please anyone check my code ..........
My code below:

Code: Select all

``````
#include<iostream>
#include<cstring>
#define M 1000000
#define INF 999999

using namespace std;
int dx[4]={-1,+1,0,0};
int dy[4]={0,0,-1,+1};
int A[999][999];
int row,col;

struct node {
node* next;
//node* pre;
int index;
int weight;
};
class PQueue {
public:
PQueue(){
}

node* newNode=new node;

newNode->next=NULL;
newNode->index=key;
newNode->weight=value;

}

bool flag=false;

prev=newNode;
newNode->next=cur;
}

else {
while(cur!=NULL) {
//cout<<cur->weight<<endl;
if(cur->index==newNode->index) {
cur->weight=newNode->weight;
flag=true;
break;
}
if(cur->weight>newNode->weight) {

prev->next=newNode;
newNode->next=cur;
flag=true;
break;
}
prev=cur;
cur=cur->next;
}
if(flag==false) {
prev->next=newNode;
}
}
}
}

int pop() {
node* temp=new node;
int key=temp->index;
delete temp;
return key;
}
int IsEmpty(){
return 0;
}
void print() {
while(cur!=NULL) {
cout<<cur->index<<" ";
cout<<cur->weight<<endl;
cur=cur->next;
}
}

};

int BFS() {

int visited[M];
int dis[M];
PQueue q;
for(int i=0;i<row*col;i++)
{
dis[i]=INF;
visited[i]=0;
}

dis[0]=0;

int x,y,w,c,p;

while(!q.IsEmpty()) {

p=q.pop();
if(p==((row*col)-1)) break;
if(visited[p]==0) {
x=p/col;
y=p%col;
for(int i=0;i<4;i++) {
int tx=x+dx[i];
int ty=y+dy[i];
if(tx>=0 && tx<row && ty>=0 && ty<col) {
w=A[tx][ty];
c=(tx*col)+ty;

if(dis[c]>dis[p]+w) {
dis[c]=dis[p]+w;
//cout<<"dis["<<c<<"]="<<dis[c]<<endl;
}
}
}
visited[p]=1;
}
}
return dis[(row*col)-1];
}

int main()
{
int test,node;
cin>>test;
while(test--) {
cin>>row>>col;
for(int i=0;i<row;i++) {
for(int j=0;j<col;j++) {
cin>>A[i][j];
}
}
cout<<BFS()<<endl;;
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 929 - Number Maze

Don't triple post.