도시
시간 제한2초메모리 제한1024 MB
N x N 격자를 도시 세포 수가 같은 두 연결 영역으로 나누고, 각 세포가 어느 영역에 속하는지 1과 2로 출력한다.
문제
어린 프로그래머가 자신만의 게임을 만들기로 했다. 게임은 N × N 칸의 격자에서 진행되며, 일부 칸에는 도시가 있다. 도시는 한 칸을 차지하고, 한 칸에 도시가 둘 이상 있을 수는 없다. 도시의 총 개수는 짝수여야 한다.
처음에 각 칸에 도시가 있는지 없는지는 모두 알려져 있다. 게임을 시작하려면 격자를 두 나라로 나누어야 하고, 각 나라에 도시가 같은 수만큼 있어야 한다.
두 나라의 국경은 칸의 경계를 따라 지나가야 하며, 각 나라의 임의의 칸에서 같은 나라의 다른 임의의 칸으로 그 나라의 칸만 거쳐 이동하는 경로가 있어야 한다. 두 칸이 변을 공유하면 서로 이동할 수 있다. 격자의 모든 칸은 두 나라 중 한 곳에만 속해야 하고, 두 나라가 차지하는 칸 수가 같을 필요는 없다.
주어진 격자의 칸을 두 나라로 나누는 프로그램을 작성하시오.
입력
첫째 줄에 격자의 크기를 나타내는 양의 정수 N이 주어진다. (1 ≤ N ≤ 50)
다음 N개 줄에는 격자의 각 칸을 나타내는 N개의 대문자 알파벳이 공백 없이 주어진다. ‘C’는 도시가 있는 칸, ‘D’는 빈 칸을 뜻한다. 격자에는 도시가 적어도 둘 있고 그 수는 짝수임이 보장된다.
출력
N개 줄에 각각 N개의 숫자를 공백 없이 출력한다. 숫자 1은 그 칸이 첫 번째 나라에 속함을, 숫자 2는 두 번째 나라에 속함을 뜻한다.
답이 여러 개면 아무거나 하나 출력한다.