6093 : 플러드 필 — 2D 격자 영역 채우기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 2D 격자 맵이 주어집니다. 격자의 각 칸은 알파벳 문자(색상)로 채워져 있습니다.
시작 좌표 (r, c)와 바꿀 목표 문자(색상)가 주어질 때, 시작 칸과 인접해 있는(상하좌우 연결된) 동일한 색상의 칸들을 목표 색상으로 칠하려 합니다. 플러드 필 알고리즘을 사용해 최종적으로 색이 바뀌는 총 칸의 수를 계산하시오.
[제약 조건]
• 격자 크기: $1 \le N, M \le 1{,}000$ (정수)
• 각 칸: 알파벳 대문자
• 시작 좌표 $(r, c)$: 0-indexed, $0 \le r < N$, $0 \le c < M$
시작 좌표 (r, c)와 바꿀 목표 문자(색상)가 주어질 때, 시작 칸과 인접해 있는(상하좌우 연결된) 동일한 색상의 칸들을 목표 색상으로 칠하려 합니다. 플러드 필 알고리즘을 사용해 최종적으로 색이 바뀌는 총 칸의 수를 계산하시오.
[제약 조건]
• 격자 크기: $1 \le N, M \le 1{,}000$ (정수)
• 각 칸: 알파벳 대문자
• 시작 좌표 $(r, c)$: 0-indexed, $0 \le r < N$, $0 \le c < M$
입력 설명
첫째 줄에 행의 크기 N과 열의 크기 M (1 ≤ N, M ≤ 1,000)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 M개의 문자(공백 없음)로 구성된 격자 정보가 주어집니다.
마지막 줄에는 시작 좌표 r, c (0-indexed, 0 ≤ r < N, 0 ≤ c < M)와 목표 문자(알파벳 대문자)가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 M개의 문자(공백 없음)로 구성된 격자 정보가 주어집니다.
마지막 줄에는 시작 좌표 r, c (0-indexed, 0 ≤ r < N, 0 ≤ c < M)와 목표 문자(알파벳 대문자)가 공백으로 구분되어 주어집니다.
출력 설명
목표 색상으로 채워지는 영역의 총 칸 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
AAA
ABA
AAA
0 0 C
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8도움
2차원 배열에서 DFS로 상하좌우를 탐색하되, 시작 칸과 문자가 같은 인접한 칸들만 재귀적으로 방문하면서 개수를 카운트하십시오.