레이팅 미적용농부 존은 자기 소 떼의 사진을 찍으려 하고 있다. 과거 경험으로 미루어 보아, 이 일이 순조롭게 끝나는 경우는 거의 없다는 것을 그는 잘 알고 있다.
이번에 농부 존은 항공 사진을 찍기 위해 값비싼 드론을 구입했다. 사진이 최대한 멋지게 나오도록, 그는 사진을 찍는 순간 모든 소가 같은 방향을 바라보고 있기를 원한다. 소들은 현재 울타리로 둘러싸인 정사각형 목초지 안에 \(N \times N\) 격자 (\(2 \leq N \leq 1000\)) 형태로 배치되어 있다. 예를 들면 다음과 같다:
RLR
RRL
LLR
여기서 'R'은 오른쪽을 바라보는 소, 'L'은 왼쪽을 바라보는 소를 의미한다. 소들이 빽빽이 모여 있어서, 농부 존은 개별 소에게 다가가 방향을 돌리게 할 수 없다. 그가 할 수 있는 일은 소들의 임의의 행이나 열에 소리를 질러 방향을 돌리게 하는 것뿐이다. 이렇게 하면 해당 행이나 열의 L은 R로, R은 L로 바뀐다. 농부 존은 원하는 만큼 많은 행이나 열에 소리칠 수 있으며, 같은 행이나 열에 여러 번 소리칠 수도 있다.
예상대로, 농부 존은 모든 소가 하나의 공통 방향을 바라보게 만들 수 없다는 것을 알아차린다. 그가 할 수 있는 최선은 한 마리를 제외한 모든 소가 같은 방향을 바라보게 하는 것이다. 그러한 소가 어떤 소인지 알아내시오.
문제 제공: Brian Dean
문제 제공: Brian Dean
첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄은 소 격자의 행 \(1 \ldots N\)을 나타내며, 각 줄에는 길이 \(N\)의 문자열이 주어진다.
그 소의 방향을 뒤집으면 농부 존이 모든 소를 같은 방향으로 바라보게 만들 수 있는 소의 행 번호와 열 번호를 출력한다. 그러한 소가 존재하지 않으면 -1을 출력한다. 그러한 소가 여러 마리라면 행 번호가 가장 작은 소를 출력하고, 가장 작은 행 번호가 같은 소가 여러 마리라면 그중 열 번호가 가장 작은 소를 출력한다.
leftout.in · 출력을 쓸 파일 leftout.out3
RLR
RRL
LLR1 1In the example above, the cow in row 1, column 1 (the upper-left corner) is the
offending cow, since Farmer John can shout at row 2 and column 3 to make all
other cows face left, with just this cow facing right.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > US Open > Silver