boopathi

Largest submatrix of binary elements

Oct 27th, 2012
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.75 KB | None | 0 0
  1. int main() {
  2.     int n=GI, a[100][100], s[100][100];
  3.     FOR(i,n) FOR(j,n) a[i][j]=GI^1;//tweak
  4.     /*s[0][0] = a[0][0]==0;
  5.     REP(i,1,n) s[0][i] = 0==s[0][i]?s[0][i-1]+1:0;
  6.     REP(i,1,n) s[i][0] = 0==s[i][0]?s[i-1][0]+1:0;*/
  7.     FOR(i,n) s[0][i] = a[0][i], s[i][0] = a[i][0];
  8.     REP(i,1,n) REP(j,1,n) if(a[i][j] == 1) s[i][j] = MIN(MIN(s[i][j-1], s[i-1][j]),s[i-1][j-1]) +1;
  9.     else s[i][j] = 0;
  10.     cout<<"DP RESULT"<<endl;
  11.     FOR(i,n) { FOR(j,n) cout<<s[i][j]<" "; cout<<endl; }
  12.     int im=0, jm=0, max=a[0][0], size=0;
  13.     FOR(i,n) FOR(j,n) if(s[i][j]>=max){ max=s[i][j]; im=i; jm=j; }
  14.     cout<<"POSITION OF MAX : ("<<im<<", "<<jm<<")"<<endl;
  15.     //REV(i,im+1){ REV(j,jm+1){ if(a[i][j]==0) break; size++; cout<<(a[i][j]^1);} cout<<endl; }
  16.     cout<<"Size : "<<size<<endl;
  17.     return 0;
  18. }
Advertisement
Add Comment
Please, Sign In to add comment