N -ROOM LIGHTS PROBLEM

Discussion in 'C Programming' started by ALIABBAS J PETIWALA, Apr 1, 2006.

  1. 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.
    ALIABBAS J PETIWALA, Apr 1, 2006
    #1
    1. Advertising

  2. ALIABBAS J PETIWALA

    Michael Mair Guest

    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.
    Michael Mair, Apr 1, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ady

    Chat room type textarea

    Ady, Nov 5, 2003, in forum: ASP .Net
    Replies:
    2
    Views:
    456
  2. Andy K

    Traffic lights with java

    Andy K, Mar 1, 2004, in forum: Java
    Replies:
    5
    Views:
    7,686
    Andrew Hobbs
    Mar 2, 2004
  3. Now You Know
    Replies:
    0
    Views:
    329
    Now You Know
    Nov 10, 2008
  4. Replies:
    0
    Views:
    346
  5. Replies:
    0
    Views:
    447
Loading...

Share This Page