929 - Number Maze

brianfry713 · Post by **brianfry713** » Fri Aug 02, 2013 12:42 am

read "Information on Submission Errors" at uva.onlinejudge.org

alexiago · Post by **alexiago** » Wed Aug 14, 2013 5:43 pm

I guess nobody else will pass this problem again due to the Submission Error

kev_yu · Post by **kev_yu** » Sun Dec 29, 2013 8:51 am

Hello ,

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;
}

Thank You.

brianfry713 · Post by **brianfry713** » Thu Jan 16, 2014 2:08 am

Try stopping once you've reached the destination, not once all the queues are empty.

t.tahasin · Post by **t.tahasin** » Wed Sep 24, 2014 11:12 am

WA

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.

brianfry713 · Post by **brianfry713** » Thu Sep 25, 2014 4:04 am

Try changing line 150 to:
for(int T = 1; T<=test; T++) {

t.tahasin · Post by **t.tahasin** » Thu Sep 25, 2014 5:30 am

thank you brianfry713
sorry for my stupid mistake..

mratan16 · Post by **mratan16** » Fri Oct 17, 2014 11:03 am

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?

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;
		
	}
}

brianfry713 · Post by **brianfry713** » Fri Oct 17, 2014 10:27 pm

Read this thread.

axelblaze · Post by **axelblaze** » Sun Oct 26, 2014 9:46 pm

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

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;
}

brianfry713 · Post by **brianfry713** » Tue Oct 28, 2014 11:10 pm

brianfry713 wrote:Read this thread.

axelblaze · Post by **axelblaze** » Wed Oct 29, 2014 6:07 pm

I didn't get it...
There is no link to thread...

brianfry713 · Post by **brianfry713** » Wed Oct 29, 2014 9:04 pm

Read all of the posts in this thread, the one that this post is in.
http://acm.uva.es/board/viewtopic.php?t=12583

LazyTym · Post by **LazyTym** » Wed Feb 04, 2015 11:27 am

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 {
    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;
}

thanks in Advanced.

LazyTym · Post by **LazyTym** » Wed Feb 04, 2015 11:27 am

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 {
    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;
}

thanks in Advanced.

OJ Board

929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Re: 929 - Number Maze

Why TLE???

Why TLE???