[ 백준 ] 17085 / 십자가 2개 놓기
# Appreciation
/*
* Problem :: 17085 / 십자가 2개 놓기
*
* Insight
* - max(N,M)=15
* O(N^4) 로 풀어도 괜찮을 것 같은데?
* + 십자가를 각 좌표를 중심으로 일일이 놓아도 괜찮을 것 같다!
*
* Point
* - 두번째 십자가를 놓을 때
* 첫번째 놓여진 십자가가 겹치지 않도록 주의하자
*/
# Code
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N, M;
char A[15][15];
bool isChecked[15][15];
// Set up : Functions Declaration
int getSize(int y, int x);
void check(int y, int x, int s);
void uncheck(int y, int x, int s);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N >> M;
for (int i=0; i<N; i++)
for (int j=0; j<M; j++)
cin >> A[i][j];
// Process
int ans = -1;
for (int y1=0; y1<N; y1++) {
for (int x1=0; x1<M; x1++) {
/* (y1,x1)를 중심으로 가지는 첫번째 십자가 */
if (A[y1][x1] != '#') continue;
int s1 = getSize(y1, x1);
check(y1, x1, s1);
for (int y2=0; y2<N; y2++) {
for (int x2=0; x2<M; x2++) {
/* (y2,x2)를 중심으로 가지는 두번째 십자가 */
if (A[y2][x2] != '#') continue;
int s2 = getSize(y2, x2);
ans = max(ans, (4*s1+1)*(4*s2+1));
}
}
uncheck(y1, x1, s1);
}
}
// Control : Output
cout << ans << endl;
}
// Helper Functions
int getSize(int y, int x)
/* (y,x)를 중심으로 가지는 놓일 수 있는 십자가의 최대 크기를 반환 */
{
int s = min(min(y, N-y-1), min(x, M-x-1));
for (int i=1; i<=s; i++) {
if (A[y+i][x] != '#' || isChecked[y+i][x]) return i-1;
if (A[y-i][x] != '#' || isChecked[y-i][x]) return i-1;
if (A[y][x+i] != '#' || isChecked[y][x+i]) return i-1;
if (A[y][x-i] != '#' || isChecked[y][x-i]) return i-1;
} return s;
}
void check(int y, int x, int s)
/* (y,x)를 중심으로 가지는 크기 s 의 십자가를 놓음 */
{
isChecked[y][x] = true;
for (int i=1; i<=s; i++) {
isChecked[y+i][x] = true;
isChecked[y-i][x] = true;
isChecked[y][x+i] = true;
isChecked[y][x-i] = true;
}
}
void uncheck(int y, int x, int s)
/* (y,x)를 중심으로 가지는 크기 s 의 십자가를 제거 */
{
isChecked[y][x] = false;
for (int i=1; i<=s; i++) {
isChecked[y+i][x] = false;
isChecked[y-i][x] = false;
isChecked[y][x+i] = false;
isChecked[y][x-i] = false;
}
}
Author And Source
이 문제에 관하여([ 백준 ] 17085 / 십자가 2개 놓기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-17085-십자가-2개-놓기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* Problem :: 17085 / 십자가 2개 놓기
*
* Insight
* - max(N,M)=15
* O(N^4) 로 풀어도 괜찮을 것 같은데?
* + 십자가를 각 좌표를 중심으로 일일이 놓아도 괜찮을 것 같다!
*
* Point
* - 두번째 십자가를 놓을 때
* 첫번째 놓여진 십자가가 겹치지 않도록 주의하자
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N, M;
char A[15][15];
bool isChecked[15][15];
// Set up : Functions Declaration
int getSize(int y, int x);
void check(int y, int x, int s);
void uncheck(int y, int x, int s);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N >> M;
for (int i=0; i<N; i++)
for (int j=0; j<M; j++)
cin >> A[i][j];
// Process
int ans = -1;
for (int y1=0; y1<N; y1++) {
for (int x1=0; x1<M; x1++) {
/* (y1,x1)를 중심으로 가지는 첫번째 십자가 */
if (A[y1][x1] != '#') continue;
int s1 = getSize(y1, x1);
check(y1, x1, s1);
for (int y2=0; y2<N; y2++) {
for (int x2=0; x2<M; x2++) {
/* (y2,x2)를 중심으로 가지는 두번째 십자가 */
if (A[y2][x2] != '#') continue;
int s2 = getSize(y2, x2);
ans = max(ans, (4*s1+1)*(4*s2+1));
}
}
uncheck(y1, x1, s1);
}
}
// Control : Output
cout << ans << endl;
}
// Helper Functions
int getSize(int y, int x)
/* (y,x)를 중심으로 가지는 놓일 수 있는 십자가의 최대 크기를 반환 */
{
int s = min(min(y, N-y-1), min(x, M-x-1));
for (int i=1; i<=s; i++) {
if (A[y+i][x] != '#' || isChecked[y+i][x]) return i-1;
if (A[y-i][x] != '#' || isChecked[y-i][x]) return i-1;
if (A[y][x+i] != '#' || isChecked[y][x+i]) return i-1;
if (A[y][x-i] != '#' || isChecked[y][x-i]) return i-1;
} return s;
}
void check(int y, int x, int s)
/* (y,x)를 중심으로 가지는 크기 s 의 십자가를 놓음 */
{
isChecked[y][x] = true;
for (int i=1; i<=s; i++) {
isChecked[y+i][x] = true;
isChecked[y-i][x] = true;
isChecked[y][x+i] = true;
isChecked[y][x-i] = true;
}
}
void uncheck(int y, int x, int s)
/* (y,x)를 중심으로 가지는 크기 s 의 십자가를 제거 */
{
isChecked[y][x] = false;
for (int i=1; i<=s; i++) {
isChecked[y+i][x] = false;
isChecked[y-i][x] = false;
isChecked[y][x+i] = false;
isChecked[y][x-i] = false;
}
}
Author And Source
이 문제에 관하여([ 백준 ] 17085 / 십자가 2개 놓기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-17085-십자가-2개-놓기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)