题目大意:
Farmer John正在尝试给他的牛群拍照。根据以往的经验,他知道这一工作往往结果不怎么样。这一次,Farmer John购买了一台昂贵的无人机,想要拍一张航拍照。为了使照片尽可能好看,他想让他的奶牛们在拍照时都朝向同一个方向。奶牛们现在在一块有围栏的草地上排列成N×N(2≤N≤1000)的方阵,例如:RLR RRL LLR 这里,字符’R’表示一头朝右的奶牛,字符’L’表示一头朝左的奶牛。由于奶牛们都挤在一起,Farmer John没办法走到某一头奶牛面前让她调转方向。他能做的只有对着某一行或某一列的奶牛喊叫让她们调转方向,使得被叫到的这一行或列内的所有L变为R,R变为L。Farmer John可以对任意多的行或列发号施令,也可以对同一行或列多次发令。 就如同Farmer John想象的,他发现他不可能让他的奶牛们都朝向同一个方向。他最多能做的是让所有奶牛中除了一头之外都朝向相同的方向。请找出这样的一头奶牛。 Input 输入的第一行包含N。以下N行描述了奶牛方阵的第1…N行,每行包含一个长度为NN的字符串。 Output 输出一头奶牛的行列坐标,满足这头奶牛被调转方向的话,Farmer John就可以使他的所有奶牛都朝向同一个方向。如果不存在这样的奶牛,输出-1。如果存在多头这样的奶牛,输出其中行坐标最小的,如果多头这样的奶牛具有相同的行坐标,输出其中列坐标最小的。 Sample Input 3 RLR RRL LLR Sample Output 1 1 在这个例子中,位于第1行第1列(左上角)的奶牛是那头令人讨厌的奶牛,因为Farmer John可以喊叫第2行和第3列来让所有奶牛都面向左侧,只有这一头奶牛面向右侧。
解析:
一个01矩阵,每次翻转一行或一列,最后除了一个元素之外的其他元素完全一样,求这个元素。
乍一看似乎没什么思路。怎么下手呢?
首先我们注意到,0和1是对称的,也就是说因为不限次数,只需把每一行翻转一遍就可以把元素01互换。
于是我们先把第一行和第一列翻转成0。
方法:对于第一行中的1,翻转它所在的列;对于第一列中的1,翻转它所在的行。
于是我们得到了一个新矩阵:(以5*5为例)
于是我们发现:在不改变第一行和第一列的情况下,蓝色部分无法被改变(因为两次翻转同一行等于没有翻转)。 若有解,则解只有以下三种位置:(1,1)、第一行或第一列(除(1,1)外)、蓝色区域中 若答案在蓝色区域中,目标位置此时一定为1并且其他部分全部为0 若答案在(1,1),则蓝色区域一定此时全部为1(翻转第一行再翻转第一列后,图中只有(1,1)为0) 若答案在第一行或第一列(除(1,1))上,则目标位置所在列或行在蓝色区域中一定全部为1且蓝色区域其他部分全部为0(翻转该列或行后,图中只有目标位置为1) 若不符合这三种情况,则无解。
附上AC Pascal代码:
var
n,i,j,ans:longint;
ch:char;
a:array[1..1000,1..1000] of longint;
begin
assign(input,'leftout.in');reset(input);
assign(output,'leftout.out');rewrite(output);
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(ch);
if ch='R' then a[i][j]:=1;
end;
readln;
end;
for i:=1 to n do
begin
if a[i][1]=1 then
for j:=1 to n do
begin
a[i][j]:=(a[i][j]+1) mod 2;
end;
end;
for j:=1 to n do
begin
if a[1][j]=1 then
for i:=1 to n do
begin
a[i][j]:=(a[i][j]+1) mod 2;
end;
end;
for i:=1 to n do
begin
for j:=1 to n do
begin
ans:=ans+a[i][j];
end;
end;
if ans=(n-1)*(n-1) then
begin
write(1,' ',1);
exit;
end
else if ans=1 then
begin
for i:=1 to n do
begin
for j:=1 to n do
begin
if a[i][j]=1 then
begin
write(i,' ',j);
exit;
end;
end;
end;
end
else if ans=n-1 then
begin
for i:=1 to n do
begin
ans:=0;
for j:=1 to n do
begin
ans:=ans+a[i][j];
end;
if ans=n-1 then
begin
write(i,' ',1);
exit;
end;
end;
end
else
begin
for j:=1 to n do
begin
ans:=0;
for i:=1 to n do
begin
ans:=ans+a[i][j];
end;
if ans=n-1 then
begin
write(1,' ',j);
exit;
end;
end;
end;
write(-1);
close(input);
close(output);
end.
谢谢!
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/200825.html原文链接:https://javaforall.cn