문제

1915번: 가장 큰 정사각형

풀이

• 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);
}