longest cross of ones.

gistfile1.txt

//the program is to find the longest cross made of ones in a matrix containing only ones and zeros. 
//small helper class 
class Four {
  public:
    Four(): up(0), bottom(0), left(0), right(0){}
    int up;
    int bottom;
    int left;
    int right;
};

class Solution {
 public:
  int largest(vector<vector<int>> matrix) {
    Four start;
    int m=matrix.size();
    int n=matrix[0].size();
    vector<Four> N(n, start);
    vector<vector<Four> > M(m, N); // creat a matrix of Four class for every number in the matrix.
    
    // preprocessing to get the longest continuous 1s for all the positions in the matrix in four directions. 
    for (int i=0; i<m; i++){
      for (int j=0; j<n;j++){
        if (j==0){
          M[i][j].left=matrix[i][j];
          M[i][n-1].right=matrix[i][n-1];
          continue;
        }
        if (matrix[i][j]==1){
          M[i][j].left=M[i][j-1].left+1;
        }
        else
          M[i][j].left=0;
        if (matrix[i][n-j-1] ==1)
           M[i][n-j-1].right=M[i][n-j].right+1;
        else
          M[i][n-j-1].right=0;
      }
    }
    for (int j=0; j<n;j++){
      for(int i=0; i<m;i++){
        if(i==0){
          M[0][j].up=matrix[0][j];
          M[m-1][j].bottom=matrix[m-1][j];
          continue;
        }
        if (matrix[i][j]==1)
          M[i][j].up=M[i-1][j].up+1;
        else
          M[i][j].up = 0;
        if (matrix[m-i-1][j]==1)
          M[m-i-1][j].bottom = M[m-i][j].bottom+1;
        else
          M[m-i-1][j].bottom = 0;
      }
    }
    
    // go over all the nodes to get the result
    int arm = 0;
    int maxx = 0;
    for(int i =0; i<m;i++){
      for (int j=0; j<n; j++){
        arm = min(min(M[i][j].right, (M[i][j].left)), min(M[i][j].up, M[i][j].bottom) );
        maxx = max(maxx, arm);
      }
    }
    return maxx;
  }
};