문제
풀이
•
bsq에서 풀었던 문제
•
만약 자기자신이 1이라면 자기자신 = 왼쪽, 위, 왼쪽위 중에 가장 작은 값 + 1
•
이때 n+1, m+1 크기만큼 선언해서 위쪽, 왼쪽에 0으로 여백을 주고 풀면 된다.
•
여백을 안주고 두번째 줄 부터 계산하면 안된다.
◦
첫번째줄에 1 하나만 있는 경우 1이 계산되지 않기떄문..!
구현
#include <iostream>
#include <vector>
using namespace std;
int n;
int m;
vector<vector<int>> map;
void pre() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void input() {
char temp;
pre();
cin >> n >> m;
map.resize(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> temp;
map[i][j] = temp - '0';
}
}
}
void solve() {
int ans;
ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (map[i][j]) {
map[i][j] = min(map[i - 1][j - 1], min(map[i - 1][j], map[i][j - 1])) + 1;
ans = max(ans, map[i][j]);
}
}
}
cout << ans * ans << endl;
}
int main(void) {
input();
solve();
return (0);
}
C++
복사
