Created
February 17, 2016 01:43
-
-
Save SLrepo/6c0ca0ffe6c44f364a3d to your computer and use it in GitHub Desktop.
longest cross of ones.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment