929 - Number Maze

[Darko]

He is correct, I am not sure why you don't believe him. What does flag[j-1]==0 evaluate to if j==0?

[lazyboy]

sorry , I bilieved him and i used

Code: Select all

if(j>0 && flag[i][j-1]==0)

and also,

if(j>0)
    if(flag[i][j-1]==0)

but for both the time i got RE.
so i think problem is in another portion.

Is my heapify correct and array size enough?

thanks for urs reply.

[newkid]

@lazyboy
well after some time debugging i found out what was the reason behind RE. The reason was obviously array limit was not sufficient. but as you already suspected the maximum size can be only 1000 x 1000 = 1000000, which you have already allocated. So I suspected you might be entering the same node more than once in the queue thus crossing the limit. And i was right.

Here is the summary of what i did:
instead of

Code: Select all

while(i!=n && j!=m)(

i used

Code: Select all

while (true) {
  temp = a[1].data;
  i = a[1].x;
  j = a[1].y;
  if (i == n - 1 && j == m - 1)
    break;
......

and removed the other break statements.

Please remove your code after you get ACC.

[lazyboy]

Thanks newkid for your debugging.
i removed my code.

[MRH]

plz give me some test case, all the board input my program give same but i can not remove WA.

[RC's]

I got TLE for this problem.... I tried implementing queue as in the previous posts said, but I still got TLE. I think there is something wrong with my code. Can anybody help me ?

Code: Select all

#include <stdio.h>
#include <memory.h>
#include <limits.h>

struct CNum
{
	int number;
	int x, y;
};

struct move
{
	int x, y;
};

class CQueue
{
public :
	CNum data[1000000];	
	int front, rear;

	inline void push(int dat, int x, int y)
	{
		data[rear].number = dat;
		data[rear].x = x;
		data[rear].y = y;
		rear++;
	}

	inline CNum pop()
	{
		if(front <= rear)
			return data[front++];
	}

	CQueue()
	{
		clear();
	}

	inline void clear()
	{
		front = rear = 0;
	}
};

int maze[1000][1000], distance[1000][1000];
CQueue Q[10];
char buffer [50000];

int main()
{
	move moves[4], t;
	int cases, row, col, i, j, idxmin, row1, col1, metu;
	char *ctr;

	CNum MNow;

	freopen("f.in", "r", stdin);
	freopen("f.out", "w", stdout);

	moves[0].x = -1;
	moves[0].y =  0;
	moves[1].x =  1;
	moves[1].y =  0;
	moves[2].x =  0;
	moves[2].y = -1;
	moves[3].x =  0;
	moves[3].y =  1;

	scanf("%i\n", &cases);

	while(cases--)
	{
		for(i = 0 ; i < 10; i++)
		{
			Q[i].clear();
		}
		scanf("%i\n%i\n", &row, &col);

		for(i = 0; i < row; i++)
		{
			gets(buffer);
			ctr = buffer;
			for(j = 0; j < col; j++)
			{
				while(*ctr == ' ') ctr++;
				maze[i][j] = *ctr - '0';
				distance[i][j] = INT_MAX;
				ctr++;
			}
		}


		row1 = row - 1;
		col1 = col - 1;

		// BFS
		distance[0][0] = maze[0][0];
		Q[0].push(maze[0][0],0,0);
		idxmin = 0;
		metu = 0;
		while(!metu)
		{
			MNow = Q[idxmin].pop();
			//printf("%i %i %i\n", MNow.x, MNow.y, MNow.number);
			for(i = 0; i < 4; i++)
			{
				t.x = MNow.x + moves[i].x;
				t.y = MNow.y + moves[i].y;
				if(t.x >= 0 && t.x < col &&
					t.y >= 0 && t.y < row)
				{
					if(distance[t.y][t.x] > MNow.number + maze[t.y][t.x])
					{
						if(t.y == row1 && t.x == col1)
						{
							printf("%i\n", MNow.number + maze[t.y][t.x]);
							metu = 1;
							break;
						}
						else
						{
							distance[t.y][t.x] = MNow.number + maze[t.y][t.x];
							Q[distance[t.y][t.x] % 10].push(distance[t.y][t.x], t.x, t.y);
						}
					}
				}
			}

			if(!metu)
			{
				// Get Highest Priority
				for(i = 0; i < 10; i++)
				{
					if(Q[i].front != Q[i].rear) 
					{
						idxmin = i;
						break;
					}
				}

				for(i = i + 1; i < 10; i++)
				{
					if( (Q[i].front != Q[i].rear) && 
						Q[i].data[Q[i].front].number < Q[idxmin].data[Q[idxmin].front].number)
					{
						idxmin = i;
					}
				}
			}
		}
	}
	
	return 0;
}

[sapnil]

WR Help.....
i use simple bfs with 10 queue, bur getting WR....pl help me.

Code: Select all

// find bugs,code remove

[Jehad Uddin]

Could not find any error ,pls help

Code: Select all

code removed got acc.... :D 

[Shafaet_du]

Pass this cases and you should get ac:

Code: Select all

4
1 1
9
2 2
0 0
0 0
20 20
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 3 1 4 6 7 8 9 6 5
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 3 1 4 6 7 8 9 6 5
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
9 9 9 0 0 0 0 0 1 2 3 4 6 7 8 9 0 5 4 3
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
1 3 5 7 8 9 2 2 2 2 3 4 4 4 4 5 6 7 8 9
0 9 9 8 7 6 9 9 9 9 9 9 9 0 0 0 0 0 9 9
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
1 2 3 4 5 6 7 8 9 5 3 2 4 5 6 7 8 9 9 6
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
0 0 0 0 0 0 1 1 1 1 2 3 3 3 3 3 4 4 4 4
3 3 3 1 1 1 1 1 3 4 5 6 7 8 9 0 5 4 3 1
22 20
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 3 1 4 6 7 8 9 6 5
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 2 2 2 2 2 8 9 6 5
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 0 6 7 8
1 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
9 9 9 0 0 0 0 0 1 2 3 4 6 7 8 9 0 5 4 3
1 2 3 4 5 6 7 8 9 9 0 6 4 0 0 0 5 6 7 8
1 4 5 7 8 9 7 5 3 4 6 7 4 0 0 0 4 3 5 9
1 3 5 7 8 9 2 2 0 2 3 4 4 0 0 0 6 4 8 9
0 9 9 8 7 6 9 9 9 9 9 9 9 0 0 0 2 0 9 9
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
1 2 3 4 6 6 8 9 0 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
1 2 3 4 5 6 7 8 9 5 3 2 4 5 6 7 8 9 9 6
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
0 0 0 0 0 0 1 1 1 1 2 3 3 3 3 3 4 4 4 4
3 3 3 1 1 1 1 1 3 4 5 6 7 8 9 0 5 4 3 1
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1

output:

Code: Select all

9
0
75
67

good luck

[Imti]

My code finds the result by applying Dijkstra+Min-priority queue.I think mine's just a straightforward implementation of Dijkstra.I hope,You guy could get this coe easily.This one passed all the input found here,but don't know where is my silly mistake???

Code: Select all

//cut after getting accepted

[back_tracker]

hey Guys, my code gives wrong output for some test cases. I hope you guys help me finding the bug.
I am using dijkstra algorithm

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int main ()
{

int test;
cin>>test;

for(int t =0; t <test; t++)
{
int row, col;

cin>>row>>col;

int **cost_maze = new int *[row];
for(int i =0; i <row; i++)
cost_maze= new int[col];



int **maze = new int *[row];
for(int i=0; i<row; i++)
maze= new int [col];


int max =0;

int c =0;
for(int i =0; i <row; i++)
{
for(int j =0; j<col; j++)
{
cin>>cost_maze[j];
max = max + cost_maze[j];
maze[j]= c;
c++;
}
}


if(row==1 && col==1)
{
cout<<cost_maze[0][0]<<endl;
continue;
}



c=0;
vector<vector<int> > edge;

for(int i =0; i<row; i++)
{
for(int j=0; j<col; j++)
{

if(i>0 )
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[j]);
edge[c-1].push_back(maze[i-1][j]);
edge[c-1].push_back(cost_maze[i-1][j]);
}


if(i<row-1)
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[j]);
edge[c-1].push_back(maze[i+1][j]);
edge[c-1].push_back(cost_maze[i+1][j]);
}

if(j<col-1)
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[j]);
edge[c-1].push_back(maze[j+1]);
edge[c-1].push_back(cost_maze[j+1]);
}

if(j>0)
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[i][j]);
edge[c-1].push_back(maze[i][j-1]);
edge[c-1].push_back(cost_maze[i][j-1]);
}

}
}





max = max*max;

int *value = new int [row*col];
for(int i=1; i<row*col; i++)
value[i]= max;

value[0]= 0;



vector<int> Q(row*col);

for(int i=0; i<row*col; i++)
Q[i]= i;



while(Q.size()!= 0)
{

int min = max+1;
int index=0 ;

int it=0;

for(int i=0; i<Q.size(); i++)
{
if(min> value[Q[i]])
{
min = value[Q[i]];
it = Q[i];
index = i;
}
}


for(int i=0; i<edge.size(); i++)
{
if(edge[i][0]== it && value[edge[i][1]]> value[edge[i][0]] + edge[i][2])
{
value[edge[i][1]] = value[edge[i][0]] + edge[i][2];

}

}

Q.erase(Q.begin()+ index);
}






cout<<value[(row*col)-1 ]<<endl;
}
}

[sadia_atique]

I'm getting tle for this problem..I used dijkstra,and tried to implement it with just array,without using STL priority queue,just to get it within time limit,bt unsuccessful..can anyone please help me?What can I do to get it within time??

Code: Select all

#include<cstdio>
#include<cstring>
using namespace std;
int check[1005][1005];
int inp[1005][1005];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int dis[1005][1005];
typedef struct{
        int x,y,w;
        }N;
N queue[1000000];
int main()
{
    int r,c,i,j,k,t,xx,yy,start,end,min,pos;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&r,&c);
        memset(check,false,sizeof(check));
        for(i=0; i<r; i++)
        {
           for(j=0; j<c; j++) scanf("%d",&inp[i][j]);
           }
        for(i=0; i<r; i++)
        {
           for(j=0; j<c; j++)
           {
               dis[i][j]=2474836;
               }
           }
        N s,p,s1,temp;
        queue[0].x=0;queue[0].y=0;queue[0].w=inp[0][0];
        dis[0][0]=inp[0][0];
        start=end=0;
        end++;
        while(start<end)
        {
            min=queue[start].w;
            pos=start;
            for(j=start+1; j<end; j++)/*find the smallest element,and swap it with start pos element*/
            {
                if(min>queue[j].w)
                {
                    min=queue[j].w;
                    pos=j;
                    }
                }
            temp=queue[pos];
            queue[pos]=queue[start];
            queue[start]=temp;
            s=queue[start];
            check[s.y][s.x]=true;
            if(s.y==r-1 && s.x==c-1) break;
            for(i=0; i<4; i++)
            {
                xx=s.x+dx[i];
                yy=s.y+dy[i];
                if(xx<0||yy<0||xx>c-1||yy>r-1) continue;
                if(check[yy][xx]==true) continue;
                if(dis[yy][xx]>dis[s.y][s.x]+inp[yy][xx])
                {
                     dis[yy][xx]=dis[s.y][s.x]+inp[yy][xx];
                     }
                queue[end].x=xx;queue[end].y=yy;queue[end].w=dis[yy][xx];
                end++;
                }
              start++;
            }
        printf("%d\n",dis[r-1][c-1]);
        }
     return 0;
     }          

[sadia_atique]

Can anyone please help me to get in runtime for this problem?What can I do to get it in runtime?

[brianfry713]

Searching through the entire queue to find the minimum value is much slower than just using a priority_queue.

[sadia_atique]

but here STL priority queue gives tle,what to do?