i attempting to solve a problem where a triangle contains many white triangles and black triangles inside it. it is required to find the largest white triangle.
the whole question can be found at : http://acm.uva.es/p/v5/585.html my code is pasted below : can anyone please test my code and tell where it fails ! #include<stdio.h> #include<stdlib.h> #define COMPLETE 1 #define NOTCOMPLETE 0 #define UP 2 #define DOWN 3 #define R 4 #define L 5 #define U 6 #define D 7 int max(int x,int y,int z); int func(int x,int y,int a ,int b,int p,int q,int bin,int dir,int bsize); char input[200][200]; int dp[200][200]; int nol,n; int main() { int count=0; int i,j,k; int x,y,z; int bin; int lmax,gmax; int out; for(count=1;;count++){ scanf("%d",&nol); if (nol==0) exit(1); lmax=0; gmax=0; n=2*nol-1; for(i=0;i<nol;i++) { for(j=0;j<n;j++) { dp[i][j]=NOTCOMPLETE; } } for(i=0;i<nol;i++) { getchar(); for(j=0;j<n-i;j++) { scanf("%c",&input[i][j]); } } for(i=0,k=0;i<nol;i++,k++) { for(j=k,bin=DOWN;j<(n-k);j++) { if(input[i][j]=='-') { if(gmax==0) gmax=1; if(bin==DOWN) { x=func(i,j,i,j+2,i+1,j+1,bin,R,2); y=func(i,j-2,i,j,i+1,j-1,bin,L,2); z=func(i-1,j-1,i-1,j+1,i,j,bin,U,2); } if(bin==UP) { x=func(i-1,j+1,i,j,i,j+2,bin,R,2); y=func(i-1,j-1,i,j-2,i,j,bin,L,2); z=func(i,j,i+1,j-1,i+1,j+1,bin,D,2); } lmax=max(x,y,z); if(lmax>gmax) gmax=lmax; } if(bin==DOWN) bin=UP; else bin=DOWN; } } out = gmax*2 - 1; if(out!=1) { for(i=out-2;i>=1;i-=2) { out+=i; } } if(gmax==0) printf("Triangle #%d\nThe largest triangle area is %d.\n",count,0); else printf("Triangle #%d\nThe largest triangle area is %d.\n",count,out); } } int func(int x,int y,int a ,int b,int p,int q,int bin,int dir,int bsize) { int i,j,k; int m,l,h; int ret; int lmax; if(y<x||y>=(n-x)||b<a||b>=(n-a)||q<p||q>=(n-p)) return 0; else if(x<0||x>nol||a<0||a>nol||p<0||p>nol) return 0; else if(dp[x][y]==COMPLETE&&dp[a][b]==COMPLETE&&dp[p] [q]==COMPLETE) return 0; else { dp[x][y]=COMPLETE; dp[a][b]=COMPLETE; dp[p][q]=COMPLETE; if(bin==DOWN) { if(dir==R) { for(i=p,j=q;i>=a;i--,j++) { if(i==p) { if(input[i][j]!='-') return 0; } else { if(!(input[i][j]=='-'&&input[i] [j-1]=='-')) return 0; } } } if(dir==L) { for(i=p,j=q;i>=x;i--,j--) { if(i==p) { if(input[i][j]!='-') return 0; } else { if(!(input[i][j]=='-'&&input[i][j +1]=='-')) return 0; } } } if(dir==U) { for(i=x,j=y;j<=b;j++) { if(input[i][j]!='-') return 0; } } ret=bsize; m=func(x,y,a,b+2,p+1,q+1,bin,R,bsize+1); l=func(x,y-2,a,b,p+1,q-1,bin,L,bsize+1); h=func(x-1,y-1,a-1,b+1,p,q,bin,U,bsize +1); lmax=max(m,l,h); if(lmax>0) ret=lmax; return ret; } if(bin==UP) { if(dir==R) { for(i=p,j=q;i>=x;i--,j--) { if(i==x) { if(input[i][j]!='-') return 0; } else { if(!(input[i][j]=='-'&&input[i] [j-1]=='-')) return 0; } } } if(dir==L) { for(i=a,j=b;i>=x;i--,j++) { if(i==x) { if(input[i][j]!='-') return 0; } else { if(!(input[i][j]=='-'&&input[i][j +1]=='-')) return 0; } } } if(dir==D) { for(i=a,j=b;j<=q;j++) { if(input[i][j]!='-') return 0; } } ret=bsize; m=func(x-1,y+1,a,b,p,q+2,bin,R,bsize+1); l=func(x-1,y-1,a,b-2,p,q,bin,L,bsize+1); h=func(x,y,a+1,b-1,p+1,q+1,bin,D,bsize +1); lmax=max(m,l,h); if(lmax>0) ret=lmax; return ret; } } } int max(int x,int y,int z) { if(x>=y&&x>=z) return x; else if(y>=x&&y>=z) return y; else if(z>=x&&z>=y) return z; } --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
