929 - Number Maze
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 929 - Number Maze
read "Information on Submission Errors" at uva.onlinejudge.org
Check input and AC output for thousands of problems on uDebug!
Re: 929 - Number Maze
I guess nobody else will pass this problem again due to the Submission Error
Re: 929 - Number Maze
Hello ,
I got TLE, I have used 10 queues and getchar() but still got TLE. Is there something wrong with my code?
Thank You.
I got TLE, I have used 10 queues and getchar() but still got TLE. Is there something wrong with my code?
Code: Select all
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <math.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef pair<int,ii> iii;
typedef vector<iii> viii;
int grid[1002][1002];
int dist[1002][1002];
void Initdist(int N,int M)
{
for (int i=0;i<=N;i++)
{
for (int j=0;j<=M;j++)
{
dist[i][j]=100000010;
}
}
}
int main()
{
int TC;
scanf("%d",&TC);
getchar();
int x,y;
int N,M;
char input;
for (int i=1;i<=TC;i++)
{
scanf("%d %d",&N,&M);
getchar();
Initdist(N,M);
for (int j=1;j<=N;j++)
{
for (int k=1;k<=M;k++)
{
input=getchar();
getchar();
grid[j][k]=(int)input-48;
}
}
//Djikstra's Algortihm
queue<iii> rpq[11];
int iterate=grid[1][1];
rpq[grid[1][1]%10].push(make_pair(grid[1][1],make_pair(1,1)));
dist[1][1]=grid[1][1];
int str=0;
while(str!=10)
{
if (rpq[iterate%10].empty())
{
iterate++;
if (iterate==10)
{
iterate=0;
}
str++;
continue;
}
str=0;
iii front=rpq[iterate%10].front();
ii frontd=front.second;
rpq[iterate%10].pop();
if (dist[frontd.first][frontd.second]<front.first)
{
continue;
}
//relaxation
//north
x=frontd.second;
y=frontd.first-1;
if ((dist[y][x]>dist[frontd.first][frontd.second]+grid[y][x]) && (frontd.first-1>0))
{
dist[y][x]=dist[frontd.first][frontd.second]+grid[y][x];
rpq[(iterate+grid[y][x])%10].push(make_pair(dist[y][x],make_pair(y,x)));
}
//east
x=frontd.second+1;
y=frontd.first;
//printf("H %d %d %d %d %d\n",x,y,dist[y][x],dist[frontd.first][frontd.second],grid[y][x]);
if ((dist[y][x]>dist[frontd.first][frontd.second]+grid[y][x]) && (x<=M))
{
dist[y][x]=dist[frontd.first][frontd.second]+grid[y][x];
rpq[(iterate+grid[y][x])%10].push(make_pair(dist[y][x],make_pair(y,x)));
}
//south
x=frontd.second;
y=frontd.first+1;
if ((dist[y][x]>dist[frontd.first][frontd.second]+grid[y][x]) && (y<=N))
{
dist[y][x]=dist[frontd.first][frontd.second]+grid[y][x];
rpq[(iterate+grid[y][x])%10].push(make_pair(dist[y][x],make_pair(y,x)));
}
//west
x=frontd.second-1;
y=frontd.first;
if ((dist[y][x]>dist[frontd.second][frontd.first]+grid[y][x]) && (x>0))
{
dist[y][x]=dist[frontd.first][frontd.second]+grid[y][x];
rpq[(iterate+grid[y][x])%10].push(make_pair(dist[y][x],make_pair(y,x)));
}
}
/*for (int i=1;i<=N;i++)
{
for (int j=1;j<=M;j++)
{
printf("%d ",dist[i][j]);
}
printf("\n");
}*/
printf("%d\n",dist[N][M]);
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 929 - Number Maze
Try stopping once you've reached the destination, not once all the queues are empty.
Check input and AC output for thousands of problems on uDebug!
Re: 929 - Number Maze
WA ![:(](./images/smilies/icon_frown.gif)
I tried all the i/o found in this thread. For all the input my program gives the correct output. please help...
Thanks in advance.
Here is my code. Sorry for my big code.
![:(](./images/smilies/icon_frown.gif)
I tried all the i/o found in this thread. For all the input my program gives the correct output. please help...
Thanks in advance.
Here is my code. Sorry for my big code.
Code: Select all
removed after acc.
Last edited by t.tahasin on Thu Sep 25, 2014 5:29 am, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 929 - Number Maze
Try changing line 150 to:
for(int T = 1; T<=test; T++) {
for(int T = 1; T<=test; T++) {
Check input and AC output for thousands of problems on uDebug!
Re: 929 - Number Maze
thank you brianfry713
sorry for my stupid mistake..
sorry for my stupid mistake..
Re: 929 - Number Maze
Hi. This is my first implementation of dijkstra's algorithm and it keeps telling me that I am getting TLE.
Can anyone help and tell me why?
Can anyone help and tell me why?
Code: Select all
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <numeric>
#include <queue>
#include <limits>
using namespace std;
struct point{
int x;
int y;
int total;
bool operator<(const point &a)const
{
if(a.total>total){
return false;
}
else{
return true;
}
}
};
int main()
{
int maze[1000][1000];
bool isVisited[1000][1000];
int runs;
cin>> runs;
for(int i=0; i<runs; ++i)
{
int rows, cols;
cin >> rows >> cols;
int final=1000000;
for(int j=0; j<rows; ++j) // For every row
{
for(int k=0; k<cols; ++k)
{
isVisited[j][k]=0;
cin >> maze[j][k];
}
}
priority_queue <point> Q;
point cur, temp;
cur.x=0; cur.y=0; cur.total=maze[0][0];
Q.push(cur);
int px, py; // Present x, y
while(!Q.empty())
{
cur=Q.top(); // Get current node
Q.pop();
px=cur.x; py=cur.y;
isVisited[px][py]=true; // Set the isVisited to true
if(cur.x==rows-1 && cur.y== cols-1)
{
final=min(final, cur.total);
}
// Push all the possible places from here
// Check left
if(py>0 && !isVisited[px][py-1])
{
temp.x=px;
temp.y=py-1;
temp.total=cur.total+maze[px][py-1];
Q.push(temp);
}
// Check right
if(py<cols-1 && !isVisited[px][py+1])
{
temp.x=px;
temp.y=py+1;
temp.total=cur.total+maze[px][py+1];
Q.push(temp);
}
// Check top
if(px>0 && !isVisited[px-1][py])
{
temp.x=px-1;
temp.y=py;
temp.total=cur.total+maze[px-1][py];
Q.push(temp);
}
// Check bot
if(px<rows-1 && !isVisited[px+1][py])
{
temp.x=px+1;
temp.y=py;
temp.total=cur.total+maze[px+1][py];
Q.push(temp);
}
}
cout << final << endl;
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 929 - Number Maze
Read this thread.
Check input and AC output for thousands of problems on uDebug!
Re: 929 - Number Maze
Can this problem be solve using DP?
I haven't learned djkstra yet but learned a little dp. So I'm trying to solve it with a dp algo I've came up with...
Here's my code but its causing infinite recursion... I don't know what's wrong here... Help plz...
I haven't learned djkstra yet but learned a little dp. So I'm trying to solve it with a dp algo I've came up with...
Here's my code but its causing infinite recursion... I don't know what's wrong here... Help plz...
Code: Select all
#include<iostream>
#include<climits>
#include<cstdio>
#define R 1000
#define C 1000
#define NIL -1
int cost[R][C],ans[R][C],r,c;
using namespace std;
int min(int,int,int,int);
int MinCost(int m,int n)
{
//cout<<r<<" "<<c<<endl;
if(m<0 || n<0 || m==r || n==c) return INT_MAX;
else if(m==0 && n==0) ans[m][n]=cost[m][n];
else if(ans[m][n]==NIL)
ans[m][n]=cost[m][n]+min(MinCost(m-1,n),MinCost(m+1,n),MinCost(m,n+1),MinCost(m,n-1));
return ans[m][n];
}
int min(int a,int b,int c,int d)
{
int ar[]={a,b,c,d},min=INT_MAX;
for(int i=0;i<4;i++)
if(min>ar[i])
min=ar[i];
return min;
}
int main()
{
freopen("in.txt","r",stdin);
int t,i,j;
cin>>t;
while(t--)
{
cin>>r>>c;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
cin>>cost[i][j];
ans[i][j]=NIL;
}
cout<<MinCost(r-1,c-1);
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 929 - Number Maze
brianfry713 wrote:Read this thread.
Check input and AC output for thousands of problems on uDebug!
Re: 929 - Number Maze
I didn't get it...
There is no link to thread...
There is no link to thread...
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 929 - Number Maze
Read all of the posts in this thread, the one that this post is in.
http://acm.uva.es/board/viewtopic.php?t=12583
http://acm.uva.es/board/viewtopic.php?t=12583
Check input and AC output for thousands of problems on uDebug!
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:
thanks in Advanced.
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 {
node* head;
public:
PQueue(){
head=NULL;
}
void add_with_priority(int key,int value) {
node* newNode=new node;
newNode->next=NULL;
newNode->index=key;
newNode->weight=value;
if(head==NULL) {
head=newNode;
}
if(head!=NULL) {
node* prev=head;
bool flag=false;
node* cur=head;
if(head->weight>newNode->weight) {
head=newNode;
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;
temp=head;
int key=temp->index;
head=head->next;
delete temp;
return key;
}
int IsEmpty(){
if(head==NULL) return 1;
return 0;
}
void print() {
node* cur=head;
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;
q.add_with_priority(i,INF);
visited[i]=0;
}
dis[0]=0;
q.add_with_priority(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;
q.add_with_priority(c,dis[c]);
}
//q.add_with_priority(c,dis[c]);
}
}
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;
}
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:
thanks in Advanced.
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 {
node* head;
public:
PQueue(){
head=NULL;
}
void add_with_priority(int key,int value) {
node* newNode=new node;
newNode->next=NULL;
newNode->index=key;
newNode->weight=value;
if(head==NULL) {
head=newNode;
}
if(head!=NULL) {
node* prev=head;
bool flag=false;
node* cur=head;
if(head->weight>newNode->weight) {
head=newNode;
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;
temp=head;
int key=temp->index;
head=head->next;
delete temp;
return key;
}
int IsEmpty(){
if(head==NULL) return 1;
return 0;
}
void print() {
node* cur=head;
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;
q.add_with_priority(i,INF);
visited[i]=0;
}
dis[0]=0;
q.add_with_priority(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;
q.add_with_priority(c,dis[c]);
}
//q.add_with_priority(c,dis[c]);
}
}
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;
}