[ 백준 21609 ] 상어 중학교 (C++)
백준의 상어중학교(21609) 문제이다.
[ 문제 바로가기 ]
[ 문제풀이 ]
블록을 문제에서 제시한 과정대로 진행하였을 때, 최종적으로 얻을 수 있는 점수를 출력해야 하는 문제이다.
문제 해결을 위해 필요한 정보들을 관리하는 방법부터, 각 과정별 단계 및 정답도출까지 순차적으로 진행해보자.
#1 - 1) "가장 큰 블록 그룹 찾기" - 필요한 정보 및 정보 관리
맵이 주어졌을 때, 가장 처음으로 진행해야 하는 것은 "가장 큰 블록 그룹을 찾는 과정" 이 될 것이다.
그런데 이 "가장 큰 블록 그룹"을 선정은 몇 가지 조건들에 의해서 결정된다.
이 조건들부터 파악을 해보자.
1. 1차적으로 크기가 더 큰 블록 그룹이 가장 큰 블록 그룹으로 선정된다.
2. 1번 조건을 만족하는 블록 그룹이 여러 개일 경우, 무지개블록의 수가 가장 많은 블록 그룹이 선정된다.
3. 2번 조건을 만족하는 블록 그룹이 여러 개일 경우, "기준 블록"의 행이 가장 큰 블록 그룹이 선정된다.
4. 3번 조건을 만족하는 블록 그룹이 여러 개일 경우, "기준 블록"의 열이 가장 큰 블록 그룹이 선정된다.
그렇다면 위의 조건들을 통해서 "가장 큰 블록 그룹"을 선정하기 위해서 우리가 알아야 할 정보가 무엇이 있는지 부터 알아보자.
1. 블록 그룹의 크기
- 1번 조건을 파악하기 위해서 "블록 그룹의 크기"를 알고 있어야 한다.
2. 무지개 블록의 수
- 2번 조건을 파악하기 위해서 "무지개 블록의 수"를 알고 있어야 한다.
3. 기준 블록
- 3번과 4번 조건을 파악하기 위해서 "기준 블록" 에 대한 정보를 알고 있어야 한다.
3 - 1) 기준 블록 선정
- 기준 블록은 "무지개 블록이 아닌 블록 중에서, 행의 번호가 가장 작으면서도 열의 번호가 가장 작은 블록" 이 된다.
따라서 우리는, "무지개 블록이 아닌 블록 중에서" 위의 조건을 만족하는 블록에 대한 정보를 알고 있어야 한다.
그럼 우리는 위와 같이 4가지 정보를 알아낸 후에, 비교를 하면서 가장 큰 블록 그룹을 찾아 낼 수 있을 것이다.
따라서, 본인은 위의 정보들을 관리하기 위해서 다음과 같은 구조체를 하나 선언해 주었다.
struct BLOCK
{
int Size;
int Rainbow_Cnt;
int x;
int y;
vector<pair<int, int>> Block_Pos;
};
"BLOCK" 구조체이다 .
멤버변수로는, 블록 그룹의 크기를 나타내는 "Size", 무지개 블록의 수를 파악하기 위한 "Rainbow_Cnt",
그리고 기준 블록의 행과 열 좌표를 나타내는 "(x , y)" 가 있다.
마지막으로 Block_Pos라는 vector하나 존재하는데, 이 vector는 단순히 블록들의 위치를 저장하기 위함이다.
아래쪽에서 더 구체적으로 이야기 하겠지만, 간략하게만 이야기해보면 우리는 결국 "가장 큰 블록 그룹"을 찾아서 그 블록 그룹을 지워줄 것이다. 그럼 이 블록 그룹을 지울 때, 어떤 좌표에 있는 데이터들을 지워야 하는지를 알아야 할 것이다.
이 때 사용하기 위해서, "지워야 할 블록 그룹에 속해 있는 데이터들의 좌표 정보를 저장" 하기 위한 vector이다.
#1 - 2) "가장 큰 블록 그룹 찾기" - 블록 그룹 찾기
#1 - 1)에서 가장 큰 블록 그룹을 찾기 위한 정보들에 대해서 알아보았고, 이 정보들을 관리하기 위한 구조체를 선언하는 과정까지 진행해 보았다. 이제는 이 정보들을 기반으로 가장 큰 블록 그룹을 찾아내는 과정을 진행해보자.
본인은 이 과정을 완전탐색, 완전탐색 중에서도 너비우선탐색(BFS)을 이용해서 접근해 보았다.
탐색을 할 때에는, #1 - 1)에서 이야기한 정보들을 파악하기 위해서 다음과 같이 진행해 주었다.
1. 블록 그룹에 속하는 "모든 블록"에 대한 좌표 정보를 저장
2. 블록 그룹에 속하는 블록들 중에서, "무지개 블록이 아닌 블록"에 대한 좌표 정보를 저장
3. 블록 그룹에 속하는 "무지개 블록" 에 대한 갯수 정보를 저장
본인은 위와 같이 3개의 탐색을 동시에 진행해 주었다.
그렇다면 위의 3개의 정보들을 어떻게 사용할 것인지, 왜 필요한지에 대해서 이야기해보자.
1. 블록 그룹에 속하는 "모든 블록"에 대한 좌표 정보를 저장.
- 이 정보를 통해서 "블록 그룹의 크기"를 알 수 있을 것이다. 결국, 블록 그룹의 크기는, 해당 그룹에 속하는 좌표가 몇 개인지에
의해서 결정되어 지기 때문에, "블록 그룹의 크기"를 알 수 있을 것이다.
- 이 정보를 통해서 #1 - 1)에서 선언해놓은 구조체의 멤버변수 중, 가장 마지막 멤버변수 였던, "지워야 할 블록 그룹에 속해 있는
데이터들의 좌표 정보를 저장" 하기 위한 vector의 정보를 알 수 있을 것이다.
2. 블록 그룹에 속하는 블록들 중에서, "무지개 블록이 아닌 블록"에 대한 좌표 정보를 저장.
- 이 정보를 통해서 "해당 블록 그룹에서의, 기준 블록" 에 대한 정보를 알 수 있을 것이다.
- 무지개 블록이 아닌 일반 블록들의 좌표 정보를 따로 저장해 준 뒤, 가장 행의 번호가 작으면서도 열의 번호가 작은 블록을
파악할 수 있을 것이다.
3. 블록 그룹에 속하는 "무지개 블록"에 대한 갯수 정보를 저장
- 이 정보를 통해서, "무지개 블록"에 대한 갯수 정보를 알 수 있을 것이다.
BFS 탐색을 진행할 때에는, 주의해야 할 점이 한 가지 있다.
보통 BFS탐색을 진행할 때에는 "중복 탐색 방지"를 위해서 이미 탐색을 했는지 아닌지를 체크해 주면서 진행을 하게 된다.
그런데 다음과 같은 예시를 한번 보자.
위와 같은 맵을 한번 살펴보자. 가장 왼쪽 위의 좌표를 (0 , 0)이라고 가정했을 때, 우리는 (0 , 0)에서 BFS탐색을 진행하게 될 것이다. 그리고, 가장 큰 블록 그룹을 찾기 위해서, "자기와 같은 색깔을 가진 블록 or 무지개 블록" 들에 한해서 탐색을 진행하게 될 것이다. 그럼 (0 , 0)에서 탐색을 시작하여 종료되었다면, 중복적인 탐색을 방지하기 위해서 "이미 탐색했으므로 더 이상 탐색하지 마세요." 라고 표시되어 있는 좌표들은 어떤 좌표들이 될까? 아마 다음과 같은 좌표들이 표시가 되어 있을 것이다.
위의 파랑색으로 칠한 좌표들이 (0 , 0)에서 시작해서 탐색을 종료했을 시점에, "이미 탐색한 좌표입니다." 라고 표시된 좌표들일 것이다. 전혀 잘못되거나 이상하지 않다. 제대로된 탐색을 했다고 볼 수 있는 상황이다.
그리고 그 이후에, (5 , 3)에 있는 '2'에서 탐색을 시작하게 된다면, 어떤 블록들을 탐색을 하게 될까 ??
위와 같이 빨강색으로 칠한 블록들이 탐색을 진행하게 될 것이다. 그 이외의 블록들은, 이미 탐색을 완료한 블록들이기 때문에 탐색을 더 이상 진행하지 않을 것이다.
그렇다면 자연스럽게, 가장 큰 블록 그룹을 "파랑색으로 칠한 블록 그룹"으로 판단하게 될 것이다. 하지만 ! 이는 잘못되었다는 것을 눈치 챘을 것이다. 사실 위의 상황에서 "가장 큰 블록 그룹"은 다음과 같이 빨강색으로 칠한 부분이다.
하지만 우리는 위와 같이 탐색을 할 수가 없었다. 왜 그럴까 ??
바로, "무지개 블록은 중첩되어 탐색이 가능해야 하기 때문" 이다.
무지개 블록을 파랑색에서 이미 탐색을 했다고 해서, 빨강색으로 탐색을 할 때, 탐색을 못하게 하면 안된다는 것이다.
그럼, 매번 중복체크를 따로 해주면 이를 해결할 수 있지만, 다음과 같은 상황을 한번 살펴보자.
(2 , 2)에 있는 '3'에서 탐색을 시작했다고 가정해보자. 탐색을 진행하게 되면, 옆에 초록색으로 표시된 '3'은 물론, 파랑색으로 표시된 '3'까지 모두 탐색을 하게 될 것이다.
그리고 우리는, "매번 중복체크를 따로 해주기 위해서" 이미 탐색을 했던 부분을 해제시키고, 다시 초록색 '3'에서 탐색을 시작하게 된다면, 또 마찬가지로 옆에 주황색으로 표시된 '3'은 물론, 파랑색으로 표시된 '3'까지 모두 탐색을 한번 더 하게 될 것이다.
이렇게 되면, 너무나도 의미없는 탐색을 여러번 하게 될 것이다.
즉 ! 우리는 "전체적으로는 일관된 중복 체크를 해줘야 하지만, "무지개 블록"에 대해서는 개별적인 중복 체크"를 해줘야 한다.
이 부분을 코드로 확인해보자.
BLOCK BFS(int a, int b, int Color)
{
memset(R_Visit, false, sizeof(R_Visit));
vector<pair<int, int>> Block;
vector<pair<int, int>> Except_Rainbow_Block;
queue<pair<int, int>> Q;
Block.push_back(make_pair(a, b));
Except_Rainbow_Block.push_back(make_pair(a, b));
Q.push(make_pair(a, b));
Visit[a][b] = true;
int Rainbow = 0;
while (Q.empty() == false)
{
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (MAP[nx][ny] == 0)
{
if (R_Visit[nx][ny] == false)
{
R_Visit[nx][ny] = true;
Rainbow++;
Block.push_back(make_pair(nx, ny));
Q.push(make_pair(nx, ny));
}
}
else if(MAP[nx][ny] == Color)
{
if (Visit[nx][ny] == false)
{
Visit[nx][ny] = true;
Q.push(make_pair(nx, ny));
Block.push_back(make_pair(nx, ny));
Except_Rainbow_Block.push_back(make_pair(nx, ny));
}
}
}
}
}
sort(Except_Rainbow_Block.begin(), Except_Rainbow_Block.end(), Cmp);
BLOCK R_Block;
R_Block.Size = Block.size();
R_Block.Rainbow_Cnt = Rainbow;
R_Block.x = Except_Rainbow_Block[0].first;
R_Block.y = Except_Rainbow_Block[0].second;
R_Block.Block_Pos = Block;
return R_Block;
}
BLOCK Find_Biggest_Block()
{
memset(Visit, false, sizeof(Visit));
BLOCK Result;
Result.Size = -1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (Visit[i][j] == true) continue;
if (MAP[i][j] == -1 || MAP[i][j] == -2 || MAP[i][j] == 0) continue;
BLOCK Temp_Result = BFS(i, j, MAP[i][j]);
if (Result.Size == -1) Result = Temp_Result;
else
{
if (Compare_Block(Temp_Result, Result) == true) Result = Temp_Result;
}
}
}
return Result;
}먼저, 아래쪽에 있는 함수인 'Find_Biggest_Block()' 함수에서, 모든 좌표를 탐색하면서, 아직 탐색하지 않은 좌표에 대해서 탐색을 시작하게 된다. 이 때, "탐색하지 않은 좌표"에 "무지개 블록"은 포함되지 않는다. 일반 블록에 대해서만 탐색을 진행해주게 된다. 여기서 "탐색"을 판단하기 위해서는, "전체에 대한 중복체크"를 위한 'Visit'함수에서 판단을 하게 된다.
하지만 ! BFS 함수 안에 들어가게 되면, 'R_Visit'(Rainbow_Visit)이라는 무지개 블록에 대한 개별적인 중복체크를 하게 된다.
또한, 이를 위해서 탐색을 할 때, 탐색하려는 좌표의 블록이 '무지개 블록인지 아닌지' 에 따라서 다르게 탐색을 하게 된다.
이 부분은 위의 코드에서 line 25)와 line 35)를 보면 확인할 수 있다.
이 외에도, BFS함수 안에서 벡터가 되게 많이 선언되어 있는데, 이 Vector들은 모두 위에서 이야기 했던, 3개의 정보들을 파악하기 위한 Vector들이다.
최종적으로, line49 ~ 56)에서 보게 되면, "일반 블록들 중에서, 기준 블록"을 찾고, "현재 블록 그룹에 대한 정보"를 저장해서 return 해주는 것을 확인할 수 있다.
# 가장 큰 블록 그룹을 찾기 위해서 필요한 정보들을 저장하는 'BLOCK' 구조체 선언
# BFS탐색을 진행하면서, 필요한 정보들 파악 및 저장
# 탐색 진행 시, "무지개 그룹"은 개별적인 중복체크가 필요하며, "전체"에 대해서는 일관적인 중복체크가 필요.
#2. 중력 작용
중력 작용은 주어진 맵에서, '-1'로 표시된 검은 블록을 제외한 나머지 블록들을 모두 내려갈 수 있는 가장 아래칸까지 내려주면 되는 과정이다. 이 과정은 별도의 설명보다는 소스코드로 대체하겠다.
(이렇게 인덱스를 가지고 장난을 쳐야 하는 과정은, 특별한 방법이나 알고리즘 보다 본인이 가장 이해하기 쉽고 구현하기 쉬운 방법이 가장 좋은 방법이라 생각합니다.)
void Gravity()
{
for (int i = N - 2; i >= 0; i--)
{
for (int j = 0; j < N; j++)
{
if (MAP[i][j] == -2) continue;
if (MAP[i][j] == -1) continue;
int Color = MAP[i][j];
int nx = i + 1;
while (1)
{
if (MAP[nx][j] != -2) break;
if (nx == N) break;
nx++;
}
nx--;
MAP[i][j] = -2;
MAP[nx][j] = Color;
}
}
}
#3. 회전하기
격자를 90도 반시계 방향으로 회전하는 과정을 알아보자.
(이 과정 또한, 인덱스로 장난을 쳐야 하는 과정으로써, 자기가 가장 편한 방법으로 하는 것이 좋습니다. 이 글에서는 저의 방법을 소개하도록 하겠습니다.)
먼저, 돌려야 할 사각형의 갯수를 파악해보자.
위와 같이 4개의 사각형에 대해서 이야기를해보자.
편의상, 가장 왼쪽에 있는 사각형부터 1, 2, 3, 4번으로 번호를 붙여 표현하겠다.
한 변의 길이가 '2'인 1번 사각형은, 빨강색으로 표시된 1개의 사각형만 회전을 시키면 된다.
한 변의 길이가 '3'인 2번 사각형은, 빨강색으로 표시된 사각형, 파랑색으로 표시된 사각형 2개의 사각형을 회전시키면 된다.
한 변의 길이가 '4'인 3번 사각형은, 빨강색으로 표시된 사각형, 파랑색으로 표시된 사각형 2개의 사각형을 회전시키면 된다.
한 변의 길이가 '5'인 4번 사각형은, 빨강색으로 표시된 사각형, 파랑색으로 표시된 사각형, 초록색으로 표시된 사각형 3개의
사각형을 회전시키면 된다.
그렇다면 ! 한 변의 길이가 'N'인 사각형은 몇 개의 사각형을 돌리면 될까 ??? 바로 N / 2 개의 사각형을 회전시키면 된다.
그럼, 이제 하나의 사각형 안에서 색깔별로 다른 사각형을 회전하는 과정을 알아보자. 가장 복잡하게 위의 그림에서 4번 그림인, 한 변의 길이가 '5'인 사각형으로 진행해보자.
본인은 가장 먼저, "기준이 되는 2개의 좌표"를 설정 및 "사각형의 번호"를 설정해준다.
기준이 되는 2개의 좌표는 "돌려야 하는 사각형에서, 가장 왼쪽 상단의 좌표와 가장 우측 하단의 좌표" 로 설정을 하게 된다.
그리고, 사각형의 번호는 가장 바깥 사각형부터 0번, 1번, 2번.. 순으로 번호를 붙이게 된다.
그럼 빨간 사각형부터 위의 설정을 진행해보자.
[ 빨강 사각형 ] - 0번 사각형
1. 기준이 되는 2개의 좌표.
- 왼쪽 상단의 좌표 = (0 , 0)
- 우측 하단의 좌표 = (N - 1 , N - 1)
[ 파랑 사각형 ] - 1번 사각형
1. 기준이 되는 2개의 좌표.
- 왼쪽 상단의 좌표 = (1 , 1)
- 우측 하단의 좌표 = (N - 2 , N - 2)
[ 초록 사각형 ] - 2번 사각형
1. 기준이 되는 2개의 좌표
- 왼쪽 상단의 좌표 = (2 , 2)
- 우측 하단의 좌표 = (N - 3 , N - 3)
위와 같이 설정을 할 수 있다. 그렇다면, K번 사각형의 기준이 되는 2개의 좌표는 어떻게 구할 수 있을까 ??
0번 사각형의 왼쪽 상단의 좌표는 (0 , 0)이였고, 1번 사각형의 왼쪽 상단의 좌표는 (1 , 1)이였다.
K번 사각형의 왼쪽 상단의 좌표는 어떻게 될까 ?? 바로 (K , K)일 것이다.
0번 사각형의 우측 하단의 좌표는 (N - 0 - 1, N - 0 - 1)이였고, 1번 사각형의 우측 하단의 좌표는 (N - 1 - 1 , N - 1 - 1) 이였다.
K번 사각형의 우측 하단의 좌표는 어떻게 될까 ?? 바로 (N - K - 1 , N - K - 1) 이 될 것이다.
우리는 이와 같이, 사각형의 한 변의 길이와, 사각형의 번호 만으로 기준이 되는 2개의 좌표를 구할 수 있다.
그럼 실제로 사각형을 돌리는 과정을 진행해보자.
우리는 위의 사각형에서 빨강색 사각형을 회전 시킬 것이다. 보다 편하게, 빨강색 사각형을 여러개의 색으로 나눠서 표현해 보겠다.
진행 과정을 먼저 말로 표현해보면 다음과 같다.
1. 빨강색 부분을 임시 저장 공간에 저장 해준다.
2. 파랑색 부분을 빨강색 부분에 덮어쓴다.
3. 초록색 부분을 파랑색 부분에 덮어쓴다.
4. 노랑색 부분을 초록색 부분에 덮어쓴다.
5. 노랑색 부분을 임시 저장 공간에 저장되어 있는 값으로 덮어쓴다.
위와 같이 진행을 한다면, 반시계 방향으로 90도 회전한 것과 같은 효과를 얻을 것이다.
그럼 각 색깔을 표시한 부분을 좌표로써 표현해보자. 실제로 구현하려면 좌표로 표현을 해야 하기 때문이다.
지금부터 편하게 가장 왼쪽 상단의 좌표를 (Sx , Sy), 가장 우측 하단의 좌표를 (Ex , Ey) 로 표현해보자.
1. 빨강색 부분에 대한 좌표정보
- (Ex ~ Sx + 1 , Sy) 로 표현할 수 있다. x좌표에 대한 정보만 Ex 에서 Sx + 1까지 감소하게 되고, y좌표는 Sy로 고정되어 있다.
2. 파랑색 부분에 대한 좌표정보
- (Sx , Sy ~ Ey - 1) 로 표현할 수 있다. y좌표에 대한 정보만 Sy ~ Ey - 1 까지 증가하게 되고, x좌표는 Sx로 고정되어 있다.
3. 초록색 부분에 대한 좌표 정보
- (Sx ~ Ex - 1 , Ey) 로 표현할 수 있다. x좌표에 대한 정보만 Sx ~ Ex - 1까지 증가하게 되고, y좌표는 Ey로 고정되어 있다.
4. 노랑색 부분에 대한 좌표 정보
- (Ex , Sy + 1 ~ Ey) 로 표현할 수 있다. y좌표에 대한 정보만, Sy + 1 ~ Ey까지 증가하게 되고, x좌표는 Ex로 고정되어 있다.
이렇게 각 색깔들을 기준점이 되는 좌표들로 표현을 할 수 있고, 이를 통해 위에서 진행했던 회전하는 과정을 구현할 수 있다.
코드로 나타내면 다음과 같다.
void Rotate()
{
for (int i = 0; i < N / 2; i++)
{
int Sx = i;
int Sy = i;
int Ex = N - i - 1;
int Ey = N - i - 1;
int x_Idx = Ex;
int y_Idx = Sy;
int Idx = 0;
vector<int> Temp;
for (int x = Ex; x > Sx; x--) Temp.push_back(MAP[x][Sy]);
for (int y = Sy; y < Ey; y++) MAP[x_Idx--][Sy] = MAP[Sx][y];
for (int x = Sx; x < Ex; x++) MAP[Sx][y_Idx++] = MAP[x][Ey];
for (int y = Ey; y > Sy; y--) MAP[x_Idx++][Ey] = MAP[Ex][y];
for (int y = Ey; y > Sy; y--) MAP[Ex][y] = Temp[Idx++];
}
}# 회전을 하기에 앞서, 몇 개의 사각형을 회전해야 하는지 구할 수 있다. = N / 2개의 사각형을 회전
# 회전을 하기 위해서, 기준점이 되는 2개의 좌표와 사각형의 번호를 설정한다.
# 사각형을 총 4개의 구역으로 나눠서, 회전을 진행하는데, 각 구역을 기준점을 이용해서 표현하자.
[ 소스코드 ]
|
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stdio.h>
#define MAX 25
using namespace std;
struct BLOCK
{
int Size;
int Rainbow_Cnt;
int x;
int y;
vector<pair<int, int>> Block_Pos;
};
int N, M, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool R_Visit[MAX][MAX];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0 ,0 };
void Input()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> MAP[i][j];
}
}
}
bool Cmp(pair<int, int> A, pair<int, int> B)
{
if (A.first <= B.first)
{
if (A.first == B.first)
{
if (A.second < B.second)
{
return true;
}
return false;
}
return true;
}
return false;
}
BLOCK BFS(int a, int b, int Color)
{
memset(R_Visit, false, sizeof(R_Visit));
vector<pair<int, int>> Block;
vector<pair<int, int>> Except_Rainbow_Block;
queue<pair<int, int>> Q;
Block.push_back(make_pair(a, b));
Except_Rainbow_Block.push_back(make_pair(a, b));
Q.push(make_pair(a, b));
Visit[a][b] = true;
int Rainbow = 0;
while (Q.empty() == false)
{
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (MAP[nx][ny] == 0)
{
if (R_Visit[nx][ny] == false)
{
R_Visit[nx][ny] = true;
Rainbow++;
Block.push_back(make_pair(nx, ny));
Q.push(make_pair(nx, ny));
}
}
else if(MAP[nx][ny] == Color)
{
if (Visit[nx][ny] == false)
{
Visit[nx][ny] = true;
Q.push(make_pair(nx, ny));
Block.push_back(make_pair(nx, ny));
Except_Rainbow_Block.push_back(make_pair(nx, ny));
}
}
}
}
}
sort(Except_Rainbow_Block.begin(), Except_Rainbow_Block.end(), Cmp);
BLOCK R_Block;
R_Block.Size = Block.size();
R_Block.Rainbow_Cnt = Rainbow;
R_Block.x = Except_Rainbow_Block[0].first;
R_Block.y = Except_Rainbow_Block[0].second;
R_Block.Block_Pos = Block;
return R_Block;
}
bool Compare_Block(BLOCK A, BLOCK B)
{
if (A.Size >= B.Size)
{
if (A.Size == B.Size)
{
if (A.Rainbow_Cnt >= B.Rainbow_Cnt)
{
if (A.Rainbow_Cnt == B.Rainbow_Cnt)
{
if (A.x >= B.x)
{
if (A.x == B.x)
{
if (A.y > B.y)
{
return true;
}
return false;
}
return true;
}
return false;
}
return true;
}
return false;
}
return true;
}
return false;
}
BLOCK Find_Biggest_Block()
{
memset(Visit, false, sizeof(Visit));
BLOCK Result;
Result.Size = -1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (Visit[i][j] == true) continue;
if (MAP[i][j] == -1 || MAP[i][j] == -2 || MAP[i][j] == 0) continue;
BLOCK Temp_Result = BFS(i, j, MAP[i][j]);
if (Result.Size == -1) Result = Temp_Result;
else
{
if (Compare_Block(Temp_Result, Result) == true) Result = Temp_Result;
}
}
}
return Result;
}
void Delete_Block(BLOCK Result)
{
vector<pair<int, int>> V = Result.Block_Pos;
for (int i = 0; i < V.size(); i++)
{
int x = V[i].first;
int y = V[i].second;
MAP[x][y] = -2;
}
Answer += (V.size() * V.size());
}
void Gravity()
{
for (int i = N - 2; i >= 0; i--)
{
for (int j = 0; j < N; j++)
{
if (MAP[i][j] == -2) continue;
if (MAP[i][j] == -1) continue;
int Color = MAP[i][j];
int nx = i + 1;
while (1)
{
if (MAP[nx][j] != -2) break;
if (nx == N) break;
nx++;
}
nx--;
MAP[i][j] = -2;
MAP[nx][j] = Color;
}
}
}
void Rotate()
{
for (int i = 0; i < N / 2; i++)
{
int Sx = i;
int Sy = i;
int Ex = N - i - 1;
int Ey = N - i - 1;
int x_Idx = Ex;
int y_Idx = Sy;
int Idx = 0;
vector<int> Temp;
for (int x = Ex; x > Sx; x--) Temp.push_back(MAP[x][Sy]);
for (int y = Sy; y < Ey; y++) MAP[x_Idx--][Sy] = MAP[Sx][y];
for (int x = Sx; x < Ex; x++) MAP[Sx][y_Idx++] = MAP[x][Ey];
for (int y = Ey; y > Sy; y--) MAP[x_Idx++][Ey] = MAP[Ex][y];
for (int y = Ey; y > Sy; y--) MAP[Ex][y] = Temp[Idx++];
}
}
void Solution()
{
while (1)
{
BLOCK Result = Find_Biggest_Block();
if (Result.Size < 2) break;
Delete_Block(Result);
Gravity();
Rotate();
Gravity();
}
cout << Answer << endl;
}
void Solve()
{
Input();
Solution();
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("Input.txt", "r", stdin);
Solve();
return 0;
}
|
cs |