📄 2811 -- 熄灯问题.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0035)http://poj.grids.cn/problem?id=2811 -->
<HTML><HEAD><TITLE>2811 -- 熄灯问题</TITLE>
<META http-equiv=Pragma content=no-cache>
<META http-equiv=Content-Type content="text/html; charset=gb2312"><LINK
href="2811 -- 熄灯问题.files/poj.css" type=text/css rel=stylesheet>
<SCRIPT language=javascript src="2811 -- 熄灯问题.files/poj.js"></SCRIPT>
<META content="MSHTML 6.00.2900.2180" name=GENERATOR></HEAD>
<BODY vLink=blue aLink=blue link=blue leftMargin=5><A name=top></A>
<TABLE style="BORDER-COLLAPSE: collapse" borderColor=#ffffff width="100%"
border=1>
<TBODY>
<TR>
<TD
style="BACKGROUND-IMAGE: url(images/header.jpg); BACKGROUND-REPEAT: no-repeat; TEXT-ALIGN: right"
vAlign=bottom align=middle colSpan=5 height=160>
<DIV style="MARGIN-BOTTOM: 0px"><IMG src="2811 -- 熄灯问题.files/logopku.gif"
border=0> <IMG src="2811 -- 熄灯问题.files/logo4.gif"
border=0></DIV></TD></TR>
<TR vAlign=top align=middle bgColor=#6589d1>
<TH class=h>Online Judge</TH>
<TH class=h>Problem Set</TH>
<TH class=h>Authors</TH>
<TH class=h>Online Contests</TH>
<TH class=h>User</TH></TR>
<TR vAlign=top align=middle bgColor=#f1f1fd>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)"><A
href="http://poj.grids.cn/bbs">Web Board</A><BR><A
href="http://poj.grids.cn/">Home Page</A><BR><A
href="http://poj.grids.cn/faq.htm"
target=_blank>F.A.Qs</A><BR>Announcement</TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)">
<FORM action=gotoproblem method=get><A
href="http://poj.grids.cn/problemlist">Problems</A><BR><A
href="http://poj.grids.cn/submit">Submit Problem</A><BR><A
href="http://poj.grids.cn/status">Online Status</A><BR><FONT
color=blue>Prob.ID:</FONT><INPUT size=6 name=pid><INPUT type=submit value=Go name=pb1></FORM></TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)">
<FORM action=searchuser method=get><A
href="http://poj.grids.cn/register">Register</A><BR><A
href="http://poj.grids.cn/modifyuser">Update your info</A><BR><A
href="http://poj.grids.cn/userlist">Authors ranklist</A><BR><INPUT size=10
name=key><INPUT type=submit value=Search name=B1></FORM></TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)"><FONT
color=#1a5cc8>Current Contest</FONT><BR><A
href="http://poj.grids.cn/pastcontests">Past Contests</A><BR><A
href="http://poj.grids.cn/contests"><FONT color=red>Scheduled
Contests</FONT></A><BR><A
href="http://poj.grids.cn/awardcontest_announce.htm" target=_blank><FONT
color=red>Award Contest</FONT></A></TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)"
align=left>Welcome<BR><A
href="http://poj.grids.cn/userstatus?user_id=tatalove"
target=_parent><B>tatalove</B></A> <A
href="http://poj.grids.cn/login?action=logout&url=/problem?id=2811">Log
Out</A><BR><A href="http://poj.grids.cn/mail" target=_parent><FONT
color=blue>Mail:0(<B>0</B>)</FONT></A></TD></TR></TBODY></TABLE>
<TABLE width="100%" background="2811 -- 熄灯问题.files/table_back.jpg" border=0>
<TBODY>
<TR>
<TD>
<P align=center><FONT color=blue size=5>熄灯问题</FONT> <BR>Time
Limit:1000MS Memory Limit:65536K<BR>Total Submit:1265 Accepted:768
</P>
<P><FONT color=blue size=5>Description</FONT><BR><FONT
face="Times New Roman"
size=3>有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。
<BR><BR><IMG src="2811 -- 熄灯问题.files/2811_1.gif">
<BR><BR>在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。
<BR><BR><IMG src="2811 -- 熄灯问题.files/2811_2.gif">
<BR><BR>请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道1）第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次；2）各个按钮被按下的顺序对最终的结果没有影响；3）对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。
<BR><BR><BR></FONT></P>
<P><FONT color=blue size=5>Input</FONT><BR><FONT face="Times New Roman"
size=3>第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。</FONT></P>
<P><FONT color=blue size=5>Output</FONT><BR><FONT face="Times New Roman"
size=3>对每个案例，首先输出一行，输出字符串“PUZZLE
#m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。每个数字以一个空格隔开。
<BR></FONT></P>
<P><FONT color=blue size=5>Sample Input</FONT><BR><FONT
face="Times New Roman" size=3><PRE>2
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0 </PRE></FONT>
<P></P>
<P><FONT color=blue size=5>Sample Output</FONT><BR><FONT
face="Times New Roman" size=3><PRE>PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1
</PRE></FONT>
<P></P>
<P><FONT color=blue size=5>Source</FONT><BR><FONT face="Times New Roman"
size=3><A
href="http://poj.grids.cn/searchproblem?field=source&key=1222">1222</A></FONT></P></TD></TR></TBODY></TABLE><FONT
color=#333399 size=3>
<P align=center>[<A
href="http://poj.grids.cn/submit?problem_id=2811">Submit</A>] [<A
href="javascript:history.go(-1)">Go Back</A>] [<A
href="http://poj.grids.cn/problemstatus?problem_id=2811">Status</A>]
[<A href="http://poj.grids.cn/bbs?problem_id=2811">Discuss</A>] </FONT></P>
<P><IMG height=30 src="2811 -- 熄灯问题.files/home.gif" width=40 border=0><FONT
size=3><A href="http://poj.grids.cn/">Home Page</A> </FONT> <IMG
height=30 src="2811 -- 熄灯问题.files/goback.gif" width=40 border=0><FONT size=3><A
href="javascript:history.go(-1)">Go Back</A> <IMG height=30
src="2811 -- 熄灯问题.files/top.gif" width=40 border=0><A
href="http://poj.grids.cn/problem?id=2811#top">To top</A></FONT><BR>
<HR>
<P style="FONT-FAMILY: Arial," align=center sans-serif Helvetica,>All Rights
Reserved 2003-2006 Ying Fuchen,Xu Pengcheng,Xie Di<BR>Any problem, Please <A
href="mailto:xiedipoj@yahoo.com">Contact Administrator</A></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -