-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMaximum square matrix with 1 s.cpp
108 lines (55 loc) · 1.44 KB
/
Maximum square matrix with 1 s.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// problem link - https://leetcode.com/problems/maximal-square/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define bug cout <<"-----------------"<<endl
int main() {
vector < vector <char > > matrix = {
{'1' ,'0' ,'1' ,'0', '0'},
{'1', '0' ,'1' ,'1' ,'1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0' }
};
//special case -> if matrix size == 0 , return 0 ;
int row = matrix.size();
int col = matrix[0].size();
//cout << row << " " << col << endl;
int grid[100][100];
memset(grid, false, sizeof grid);
for (int i = 1; i <=row; i++) {
for (int j = 1; j <= col; j++) {
grid[i][j] = (matrix[i-1][j-1]) -48;
}
}
int ans[100][100] = { 0 };
memset(ans, 0, sizeof ans);
for (int i = 2; i <= row+1; i++) {
for (int j = 2; j <= col+1; j++) {
if (grid[i-1][j-1] == 0) {
ans[i][j] = 0;
}
else if(grid[i-1][j-1]==1) {
int up = ans[i - 1][j];
int left = ans[i][j - 1];
int diago = ans[i - 1][j - 1];
ans[i][j] = min({ up ,left , diago }) + 1;
}
}
}
int mx = -1;
for (int i = 1; i <= row+1; i++) {
for (int j = 1; j <= col+1; j++) {
mx = max(ans[i][j], mx);
}
//cout << endl;
}
cout << mx * mx << endl;
//solve();
/*int kase;
cin >> kase;
while (kase--)
{
solve();
}*/
return 0;
}