ALIABBAS J PETIWALA schrieb:

N -ROOM LIGHTS PROBLEM

========================

THERE IS A BIG SQURE ROOM OF SIDE N WHICH CONSISTS OF N X N SMALLER

SQUARE ROOMS(ARRANGED LIKE CHESS BOARD)

EACH ROOM HAS A LIGHT.

WHEN the light of a smaller room k is toggled then all the

neighboring room's lights get toggled (max 5 lights get toggled

including the kth room if center room gets clicked )

THE PROBLEM IS to formulate an algorithm which will generate an order

in which the lights have to be toggled such that

all the n X n rooms get lit, initially no room is lit.

(toggle means that if the light is on then it is toggled of & if it is

off then it is switched on)

(question asked by Microsoft at IIT)

me>CAN a divide and conquer strategy work?

Me>I think that dynamic programming techniq can be used to solve this

problem?

Dear wade u got it wrong as u said " A light is On iff the number of

Up switches in the room and its horizontal/vertical (not diagonal)

neighbors is odd."

If u toggle a light near the wall of the room as shown:

if its possible I am attaching a sample program.

This is not a C question; if you have found an algorithm

and have problems implementing it in C, you can show it

to us. If you do, then describe your expectations, your

problems, and copy&paste the program.

<OT>

Hints:

- Does order matter?

- N=1 and N=2 are special cases

- What happens if you toggle each room's switch exactly once?

</OT>

Cheers

Michael

--

E-Mail: Mine is an /at/ gmx /dot/ de address.