이번 문제는 42 피씬과정에서 있었던 BSQ 과제의 알고리즘과 똑같았다.
크게 어려운 부분은 없었지만 입력이 숫자로 들어오는게 아니라 문자 배열로 들어오는 것을 고려했어야 했다.
그래서 string을 입력받고 인덱스 접근을 통해서 벡터에 넣어주었다.
2021/02/24
5996 KB
12 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int N;
int M;
int result;
std::vector<std::vector<int> > map;
void output()
{
std::cout << result * result;
}
void solution()
{
for (int i = 1 ; i <= N ; i++)
for (int j = 1 ; j <= M ; j++)
{
if(map[i][j] == 1)
map[i][j] += std::min({map[i - 1][j], map[i - 1][j - 1], map[i][j - 1]});
result = std::max(result, map[i][j]);
}
}
void input()
{
std::string str;
std::cin >> N >> M;
map = std::vector(N + 1, std::vector(M + 1, 0));
for (int i = 1 ; i <= N ; i++)
{
std::cin >> str;
for (int j = 1 ; j <= M ; j++)
map[i][j] = str[j - 1] - '0';
}
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
input();
solution();
output();
}
2021/02/24
2152 KB
8 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int N;
int M;
int result;
std::vector<std::vector<int> > map;
void output()
{
std::cout << result * result;
}
void solution()
{
std::string str;
int A = 0;
int B = 1;
std::cin >> N >> M;
map = std::vector(2, std::vector(M + 1, 0));
for (int i = 1 ; i <= N ; i++)
{
std::cin >> str;
for (int j = 1 ; j <= M ; j++)
{
if(str[j - 1] == '0')
map[B][j] = 0;
else
{
map[B][j] = std::min({map[A][j], map[B][j - 1], map[A][j - 1]}) + 1;
result = std::max(result, map[B][j]);
}
}
std::swap(A, B);
}
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
solution();
output();
}