#P5427. [USACO19OPEN] Left Out S

[USACO19OPEN] Left Out S

题目描述

Farmer John正在尝试给他的牛群拍照。根据以往的经验,他知道这一工作往往结果不怎么样。

这一次,Farmer John购买了一台昂贵的无人机,想要拍一张航拍照。为了使照片尽可能好看,他想让他的奶牛们在拍照时都朝向同一个方向。奶牛们现在在一块有围栏的草地上排列成 N×N N \times N 2N1000 2 \leq N \leq 1000 )的方阵,例如:

RLR
RRL
LLR

这里,字符'R'表示一头朝右的奶牛,字符'L'表示一头朝左的奶牛。由于奶牛们都挤在一起,Farmer John没办法走到某一头奶牛面前让她调转方向。他能做的只有对着某一行或某一列的奶牛喊叫让她们调转方向,使得被叫到的这一行或列内的所有L变为R,R变为L。Farmer John可以对任意多的行或列发号施令,也可以对同一行或列多次发令。

就如同Farmer John想象的,他发现他不可能让他的奶牛们都朝向同一个方向。他最多能做的是让所有奶牛中除了一头之外都朝向相同的方向。请找出这样的一头奶牛。

输入格式

输入的第一行包含 N N 。以下 N N 行描述了奶牛方阵的第 1N 1 \ldots N 行,每行包含一个长度为 N N 的字符串。

输出格式

输出一头奶牛的行列坐标,满足这头奶牛被调转方向的话,Farmer John就可以使他的所有奶牛都朝向同一个方向。如果不存在这样的奶牛,输出-1。如果存在多头这样的奶牛,输出其中行坐标最小的,如果多头这样的奶牛具有相同的行坐标,输出其中列坐标最小的。

3
RLR
RRL
LLR
1 1

提示

在这个例子中,位于第1行第1列(左上角)的奶牛是那头令人讨厌的奶牛,因为Farmer John可以喊叫第2行和第3列来让所有奶牛都面向左侧,只有这一头奶牛面向右侧。