|
|
back to boardPlease somebody give mesome test I got WA3! Thank you Posted by Husan 31 Jul 2008 11:14 This is my prog #include<iostream> using namespace std; int a[102][502]={{0}},path[102][502]={{0}}; int n,m; void matr(int i) { int j; int p1[500]={0},p2[500]={0}; int pre1[500],pre2[500]; p1[0]=p2[n+1]=10000; // left to right for(j=1;j<=n;j++) if(p1[j-1]+a[i][j]>a[i][j]+a[i-1][j]){p1[j]=a[i][j]+a[i-1][j];pre1[j]=j;} else{p1[j]=p1[j-1]+a[i][j];pre1[j]=j-1;} //right to left for(j=n;j>=1;j--) if(p2[j+1]+a[i][j]>a[i][j]+a[i-1][j]){p2[j]=a[i][j]+a[i-1][j];pre2[j]=j;} else {p2[j]=p2[j+1]+a[i][j];pre2[j]=j+1;} //sravnenie for(j=1;j<=n;j++) { if(p1[j]>p2[j]){a[i][j]=p2[j];path[i][j]=pre2[j];}else{a[i][j]=p1[j];path[i][j]=pre1[j];} p1[j]=p2[j]=0; } } int main() { int i,j,min=10000,mini;
cin>>m>>n; for(i=1;i<=m;i++) { a[i][0]=a[i][n+1]=10000; for(j=1;j<=n;j++)cin>>a[i][j]; } for(i=2;i<=m;i++)matr(i); for(i=1;i<=n;i++) if(min>a[m][i]){min=a[m][i];mini=i;}; int k1=m,k2=mini,kol=1,ans[500]; if(m==1)cout<<mini;else{ ans[kol]=k2; do { kol++; ans[kol]=path[k1][k2]; if(path[k1][k2]==k2)k1--;else k2=path[k1][k2]; }while(path[k1][k2]!=0);
for(i=kol;i>=1;i--)cout<<ans[i]<<" ";} return 0; } |
|
|