Lights OutProblem code: DORADM01 |
All submissions for this problem are available.
Johnny is playing Lights Out, an electronic game consisting of an NxN grid of lights. Initially, each light may be on or off. Pressing a light will toggle it and the lights non-diagonally adjacent to it.
The object of the game is to try and get all the lights turned off. It is not always possible, and what's more, Johnny's game is faulty. Pressing some lights has no effect. (They can still be turned on and off if they are next to working lights.)
Help Johnny write a program that checks whether a puzzle can be solved or not, given the initial description of the grid and the positions of the faulty lights.
Input
The first line contains a number t (about 10), the number of test cases. Each test case has the following form:
The first line contains two numbers N and K (2 <= N <= 200, 0 <= K <= N). Each line in the next N lines contains N characters '0' or '1' representing the initial state of the grid. '1' denotes a light that is on and '0' a light that is off.
Each line in the next K lines contains 2 integers, i and j (1 <= i, j <= N), representing the row and column of a faulty light. Rows are numbered from the top and columns from the left.
Output
For each test case, print YES if there is a solution, otherwise print NO.
Example
Input: 2 3 1 010 111 010 2 2 4 2 1110 1110 1001 1101 2 2 4 3 Output: NO YES
| Author: | MichaelD |
| Date Added: | 9-04-2010 |
| Time Limit: | 2 - 4 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can anyone please explain the
Can anyone please explain the following line ....
Pressing some lights has no effect. (They can still be turned on and off if they are next to working lights.) ...
What part of that sentence
What part of that sentence don't you understand? Pushing a broken light does nothing.
Can anyone tell me whether
Can anyone tell me whether input passed is through standard input or a text file called in.txt? I have read in two different locations which said me that the input is given in standard input format and then through the command java test < in.txt > out.txt.
Which one I should be using to test the program for this competition?
Please let me know asap.
Thanks in advance.
My program seems to be
My program seems to be running into a runtime error when I submit. However, it works fine at my house. Please help.
The FAQ clearly says it will
The FAQ clearly says it will be from standard input/output. The other line you are quoting was a method of testing your code locally without having to enter input at the command prompt all the time.
what's the memory limitation
what's the memory limitation of this problem?
@Amlesh Jayakumar: have you
@Amlesh Jayakumar: have you tried all cases of test?
@Yihe Zhu: there's no memory limit for these problems :-)
Is there any way to improve
Is there any way to improve overall rank if so many people have same points. OR it is randon only?
1>Pressing the fault light
1>Pressing the fault light has no effect. But can it toggle if pressing neighbour light?
2>if next mean any light neighbour to light?
A non-faulty light toggles
A non-faulty light toggles all adjacent lights, regardless of whether those adjacent lights are faulty or not.
Help!I can not understand the
Help!
I can not understand the following sentense.
"Pressing a light will toggle it and the lights non-diagonally adjacent to it. "
if the lights' status are:
111
111
111
and, press (2,2),
which one will I get ?
a)
101
010
101
b)
101
000
101
c) if other ? please type it.
It is crearly mentioned in
It is crearly mentioned in the statement you had copy pasted.
@liubiaoyong - u will get (b)
@liubiaoyong - u will get (b)
@admin I am getting ":(
@admin
I am getting ":( internal error occurred in the system" after submitting the solution. Kindly help.
Same with me!!!!
Same with me!!!!
I have a question about it:
I have a question about it: "They can still be turned on and off if they are next to working lights."
That means if someone press a faulty light , it does not affect adjacent lights ; or if someone press a working light, it does not affect a faulty adjacent light?
I have read the statements
I have read the statements again and that means: pressing faulty button has no affect to nearby buttons; and pressing working buttons have affect to the faulty buttons? It is right?
Working lights affect
Working lights affect adjacent faulty lights. Faulty lights do nothing.
I also keep getting ":(
I also keep getting ":( internal error occurred in the system" when I try to submit a solution! It's happening since couple of hours.
When will the internal error
When will the internal error disappear? I hate it. It is so annoying.
I wonder how people had
I wonder how people had solved this question in 0.25 sec!!!!
Hats off to them!!!!