Posted: Sat Jul 14, 2007 5:06 pm
To mmonish, check your code with a table of all zeroes. Post your code if it passes.
The Online Judge board
https://uva.onlinejudge.org/board/
https://uva.onlinejudge.org/board/viewtopic.php?f=34&t=12583
Code: Select all
removed after AC.
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
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]);
}
}
Code: Select all
Code removed
Code: Select all
if(flag[i-1][j]==0 && i>0)
Code: Select all
if(flag[i][j-1]==0 && j>0)
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.
........
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"