동적 격자 (라지)
면접 대비시간 제한5초메모리 제한512 MB
이진 격자 셀을 갱신하면서 조회마다 상하좌우로 이어진 1 묶음 개수를 구합니다.
문제
0 또는 1이 적힌 행 열 격자가 있다. 이 격자에 연산을 번 수행한다. 연산은 다음 두 종류 중 하나다.
- 연산 M: 격자의 한 칸의 값을 0 또는 1로 바꾼다.
- 연산 Q: 1로 이루어진 연결 영역의 개수를 구한다. 1의 연결 영역은 값이 모두 1인 칸의 집합이고, 그 집합 안의 어떤 칸에서 출발해도 변을 맞댄 칸을 따라 이동해서 집합의 나머지 칸에 모두 도달한다. 꼭짓점만 맞닿은 두 칸은 이어진 것으로 보지 않는다.
입력
첫 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스의 첫 줄에는 격자의 행 수 과 열 수 가 주어진다. 이어지는 개의 줄에는 각각 0과 1로만 이루어진 길이 의 문자열이 주어지고, 이는 격자의 초기 상태다. 행 번호는 부터 까지, 열 번호는 부터 까지다.
그다음 줄에는 수행할 연산의 개수 이 주어진다. 이어지는 개의 줄에 연산이 한 줄에 하나씩 주어진다. 연산 M은 M x y z 꼴이고, 행 열 칸의 값을 로 바꾼다는 뜻이다. 연산 Q는 Q 한 글자다.
출력
각 테스트 케이스마다 먼저 Case #x:를 한 줄에 출력한다. 여기서 는 1부터 시작하는 테스트 케이스 번호다. 그 뒤에 그 테스트 케이스의 연산 Q마다 입력에 주어진 순서대로 1의 연결 영역 개수를 한 줄에 하나씩 출력한다.