929 - Number Maze
Moderator: Board moderators
To mmonish, check your code with a table of all zeroes. Post your code if it passes.
Ami ekhono shopno dekhi...
HomePage
HomePage
I check my code with a table of all zero's. it gives correct output.
Here is my code
Here is my code
Code: Select all
removed after AC.
Last edited by mmonish on Mon Jul 16, 2007 8:40 pm, edited 2 times in total.
Try the cases.
Input:
Output:
Hope these help.
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
Code: Select all
59
88
76
Last edited by Jan on Sat Jul 14, 2007 10:27 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage
HomePage
Sorry, I haven't read the description again. However, the cases are correct ( hopefully
) now.

Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Learning poster
- Posts: 74
- Joined: Sat Jul 15, 2006 6:28 am
- Location: CUET , bangladesh
- Contact:
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]);
}
}
SHAKIL
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.
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.
Re: 929 - Number Maze
I am getting RE error in this problem.
i didn't find the reason... please help me.
here is my code :
Thanks in advance.
i didn't find the reason... please help me.
here is my code :
Code: Select all
Code removed
Last edited by lazyboy on Sat Feb 07, 2009 9:12 pm, edited 2 times in total.
Re: 929 - Number Maze
I haven't gone through the full code but i found these..
The array index bound checking should be done first before accessing the array element.
you should do
same goes for the other one..
Code: Select all
if(flag[i-1][j]==0 && i>0)
Code: Select all
if(flag[i][j-1]==0 && j>0)
you should do
Code: Select all
if(j>0 && flag[i][j-1]==0)
lazyboy wrote:I am getting RE error in this problem.
i didn't find the reason... please help me.
........
hmm..
Re: 929 - Number Maze
Thanks for ur reply.
so this is not standing for RE.
i think this not the case. i used 'and' operation, and when both the condition returns true then the segment executes.
newkid wrote
"The array index bound checking should be done first before accessing the array element.
you should do"
so this is not standing for RE.