929 - Number Maze

[Jan]

To mmonish, check your code with a table of all zeroes. Post your code if it passes.

[mmonish]

I check my code with a table of all zero's. it gives correct output.
Here is my code

Code: Select all

removed after AC.


[Jan]

Try the cases.

Input:

Code: Select all

3
8
17
1 4 2 3 2 2 1 6 8 5 7 6 1 8 9 2 7
9 5 4 3 1 2 3 3 4 1 1 3 8 7 4 2 7
7 9 3 1 9 8 6 5 0 2 8 6 0 2 4 8 6
5 0 9 0 0 6 1 3 8 9 3 4 4 6 0 6 6
1 8 4 9 6 3 7 8 8 2 9 1 3 5 9 8 4
0 7 6 3 6 1 5 4 2 0 9 7 3 7 2 6 0
1 6 5 7 5 4 1 2 0 0 1 4 6 0 7 1 7
7 7 7 3 3 5 9 9 8 1 8 2 6 6 0 3 8
12
17
4 0 6 1 8 9 8 4 1 4 3 9 8 8 0 8 7
7 8 3 8 3 7 1 0 7 3 4 9 6 5 1 0 9
9 6 8 3 4 8 4 9 9 2 5 5 3 3 3 7 4
3 8 0 8 8 0 6 8 1 9 8 9 7 2 2 8 2
8 9 0 7 8 1 5 8 6 1 2 4 2 5 8 6 2
6 5 3 9 2 4 6 1 8 2 1 1 9 7 6 2 9
5 2 0 0 3 9 1 8 1 9 5 3 2 5 2 5 8
6 7 7 2 2 9 4 1 9 6 9 8 2 5 5 4 9
1 2 5 0 8 3 9 3 9 6 7 9 9 7 6 9 3
5 7 6 6 5 8 2 5 4 4 1 6 1 6 3 3 5
5 3 2 8 2 5 3 6 1 8 6 2 1 4 6 2 9
1 5 0 3 6 4 9 2 9 3 4 4 0 5 9 6 3
14
16
2 8 0 7 2 2 5 9 1 0 8 5 0 7 9 0
5 3 4 1 0 4 8 5 9 2 5 4 1 3 9 5
8 2 7 9 6 1 7 7 1 9 0 3 4 1 7 5
3 3 2 4 1 2 9 0 8 7 4 5 6 8 0 7
7 4 3 1 3 6 3 0 1 9 0 4 2 9 3 1
4 8 2 0 5 5 9 3 2 8 7 4 8 1 4 3
5 5 2 6 8 9 2 9 5 9 4 5 0 5 8 8
0 1 3 2 2 2 7 0 3 1 3 3 7 0 9 5
5 8 3 7 8 3 7 9 3 9 1 8 2 8 0 1
8 4 8 6 0 9 3 0 0 8 7 6 3 5 6 5
8 3 9 4 8 3 9 7 6 4 5 8 6 1 5 5
1 9 6 4 5 4 2 5 3 2 6 8 2 6 6 3
9 4 5 6 2 5 3 5 6 6 1 4 4 6 2 6
8 2 5 5 1 0 1 5 1 7 6 0 0 2 4 3


Output:

Code: Select all

59
88
76

Hope these help.

[mmonish]

>> jan
I think the maze numbers from 0 to 9. so is ur testcase is ok or not?

[Jan]

Sorry, I haven't read the description again. However, the cases are correct ( hopefully ) now.

[mmonish]

Now i get AC. problem on my heap implementation.
Thank u all for help.

[ayeshapakhi]

[shakil]

I got TLE. How i can reduce time. Thanks in advance........

Code: Select all

#include<stdio.h>
const long max = 1000;
long value[max][max],si[max][max],sa[max][max],in,n,m;
long x[max*max],y[max*max];

void que(long h1)  //modify que
{
long h2,t1,t2;
while(h1!=0)
{
h2=(h1-1)/2;

if(value[x[h2]][y[h2]]>value[x[h1]][y[h1]])
{
t1=x[h2];t2=y[h2];
x[h2]=x[h1];y[h2]=y[h1];
x[h1]=t1;y[h1]=t2;
si[x[h1]][y[h1]]=h1;
si[x[h2]][y[h2]]=h2;
h1=h2;
}
else
break;
}

}
void coque()   //delete que
{
   long root,k,va,t1,t2;
in--;
x[0]=x[in];y[0]=y[in];
si[x[0]][y[0]]=0;
root=0;
while(root<in)
{
k=-1;
va=value[x[root]][y[root]];
if(2*root+1<in)
{
if(value[x[2*root+1]][y[2*root+1]]<va)
{va=value[x[2*root+1]][y[2*root+1]];k=2*root+1;}
}

if(2*root+2<in)
{
if(value[x[2*root+2]][y[2*root+2]]<va)
{va=value[x[2*root+2]][y[2*root+2]];k=2*root+2;}
}

if(k!=-1)
{
t1=x[root];t2=y[root];
x[root]=x[k];y[root]=y[k];
x[k]=t1;y[k]=t2;
si[x[root]][y[root]]=root;
si[x[k]][y[k]]=k;
root=k;
}
else
break;
}

}



void main()
{
long i,j,X,Y,cas,cas1;

scanf("%ld",&cas);

for(cas1=1;cas1<=cas;cas1++)
{
scanf("%ld %ld",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%ld",&sa[i][j]);
value[i][j]=2000000000;
si[i][j]=-1;
}
value[0][0]=sa[0][0];
in=0;
if(m>1)
{
value[0][1]=sa[0][0]+sa[0][1];
x[0]=0;y[0]=1;
sa[0][1]=0;
in=1;
}
if(n>1)
{
value[1][0]=sa[0][0]+sa[1][0];
x[in]=1;y[in]=0;
sa[1][0]=in;
in++;
que(in-1);
}
while(in!=0)
{
if(x[0]==n-1&&y[0]==m-1)
break;
X=x[0];Y=y[0];
coque();
if(Y+1<m)
if(value[X][Y+1]>value[X][Y]+sa[X][Y+1])
{
value[X][Y+1]=value[X][Y]+sa[X][Y+1];
if(si[X][Y+1]==-1)
{x[in]=X;y[in]=Y+1;
 si[X][Y+1]=in;
 in++;
que(in-1);
}
else
que(si[X][Y+1]);
}


if(Y-1>=0)
if(value[X][Y-1]>value[X][Y]+sa[X][Y-1])
{
value[X][Y-1]=value[X][Y]+sa[X][Y-1];
if(si[X][Y-1]==-1)
{x[in]=X;y[in]=Y-1;
 si[X][Y-1]=in;
 in++;
que(in-1);
}
else
que(si[X][Y-1]);
}


if(X+1<n)
if(value[X+1][Y]>value[X][Y]+sa[X+1][Y])
{
value[X+1][Y]=value[X][Y]+sa[X+1][Y];
if(si[X+1][Y]==-1)
{x[in]=X+1;y[in]=Y;
 si[X+1][Y]=in;
 in++;
que(in-1);
}
else
que(si[X+1][Y]);
}

if(X-1>=0)
if(value[X-1][Y]>value[X][Y]+sa[X-1][Y])
{
value[X-1][Y]=value[X][Y]+sa[X-1][Y];
if(si[X-1][Y]==-1)
{x[in]=X-1;y[in]=Y;
 si[X-1][Y]=in;
 in++;
que(in-1);
}
else
que(si[X-1][Y]);
}

}

printf("%ld\n",value[n-1][m-1]);

}
} 

[Darko]

I am going nuts with this one. At this moment, my Java code doesn't look much like Java...

Anyway - can someone tell me how big the input file is?

I assumed that it was 16MB. Being that the only way I can get some fast I/O is to read the whole thing in, I really see no room for improvement with my current approach if the input file is larger. I used a "naive" solution with dijkstra's + heap, but I think that should run in time. Well, maybe only in C...

[EDIT] Just to answer my own question - Yes, the input file is at most 16MB. I did the 10 queue thingy and optimized the crap out of poor Java and finally get it to pass. Thanks goes to Rio for the circular queue hint.

[RuanZheng]

I am going to crazy for this problem
My code passed all the data on this thread, and I could not find whether there is an error with my dijkstra+heap.
More test data, please.

[Jan]

Post your code.

[baodog]

I think many TLEs become AC on this one in the new server.
My code was at least a factor of 7 faster.
Could be due to increased memory cache size as well.

[lazyboy]

I am getting RE error in this problem.
i didn't find the reason... please help me.

here is my code :

Code: Select all

Code removed


Thanks in advance.

[newkid]

I haven't gone through the full code but i found these..

Code: Select all

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

Code: Select all

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

The array index bound checking should be done first before accessing the array element.
you should do

Code: Select all

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

same goes for the other one..

I am getting RE error in this problem.
i didn't find the reason... please help me.
........

[lazyboy]

Thanks for ur reply.

newkid wrote
"The array index bound checking should be done first before accessing the array element.
you should do"

i think this not the case. i used 'and' operation, and when both the condition returns true then the segment executes.
so this is not standing for RE.