50183. Lights out, again

I'm a slow walker, but I never walk backwards.

Task Description

Let us play Lights Out, again.

Lights Out is a puzzle game consisting of an $N$ by $N$ grid of lights which can be turned on and off. Each of these $N^2$ lights has an id from $0$ to $N^2-1$ from left to right, and from top to bottom. When the game starts, a random number of these lights are turned on. Please refer to the following figure.

figurefigure

Pressing any of the lights will toggle it and all of its immediate vertical and horizontal neighbors. The goal of the puzzle is to turn off all the lights with the minimum number of pressing. Note that the order in which the lights are pressed does not affect the results. Also note that we do not need to press a light more than once since pressing it twice is the same as not to press it at all. Please refer to the following figure.

figurefigure

We will solve this problem by objects. First, you have to design your own object Lights in lights.h. Lights needs to implement four functions. Function init will turn off all lights. Function flip will toggle the i-th light, and the size of lights is NxN. Function numOfLights returns the number of the lights that are on, and the size of lights is NxN. For efficency you should not examine all lights to find their status. Instead you should remember the number of lights and update with flip, so that *numOfLights can return it immediately. Function printLights will print the status of all lights. The prototype of the four functions are in lights.h as follows.

typedef struct _lights{
    // Design by yourself
}Lights;
 
void init(Lights *l);
int numOfLights(Lights *l,int N);
void flip(Lights *l,int i,int N);
void printLights(Lights *l,int N);

You need to implement all four functions. You can test your flip function with the following main_flip.c:

#include<stdio.h>
#include "lights.h"
int main()
{
    Lights l;
    init(&l);
    int n;
    int index;
    int N;
 
    scanf("%d",&N);
    while(scanf("%d",&n)!=EOF)
        flip(&l,n,N);
    printLights(&l,N);
    return 0;
}

You can test your numOfLights with the following main_numOfLights.c

#include<stdio.h>
#include "lights.h"
#define ROUND 200000000
int main()
{
    Lights l;
    init(&l);
    int n;
    int N;
    scanf("%d",&N);
    while(scanf("%d",&n)!=EOF)
        flip(&l,n,N);
    int num=0;
    for(int i=0;i<ROUND;i++){
        num=numOfLights(&l,N);
    }
    printf("%d\n",num);
    return 0;
}

Finally write a main.c to find the minimum set of lights that need to be pressed to turn off all lights with the object Light provided by the TA. If there are multiple sets of them, output the first one in dictionary order. For example, 1 2 4 appears earlier than 1 3 4 in the dictionary order.

Compile

gcc -std=c99 -O2 main_flip.c lights.c
gcc -std=c99 -O2 main_numOfLights.c lights.c
gcc -std=c99 -O2 main.c lights.c

Subtasks

  • 40 points: Only the correctness of init, flip,and printLights will be considered in these subtasks.
  • 40 points: Correctness of all of the four functions will be considered in these subtasks.
  • 20 points: main.c will be checked with TA's functions. So if only the correctness of main.c can still get these points.

Note that if you have not completed all of the functions and you still want to submit your solution for partial credits, your main.c and function numOfLights should be empty so the program will compile, as shown below:

1
int main(){}
1
int numOfLights(Lights *l,int N){}

Input Format

For main_flip.c and main_numOfLights.c and main.c, the input formats are the same. The first line is $N$. The second line has the indices of the lights that will be toggled in order.

  • $3 ≤ N ≤ 4$

Output Format

For main_flip.c, print the status of all of the lights. 1 for the on, and 0 for the off. For main_numOfLights.c, print the number of the lights which are turned on. For main.c, print the indices of the lights that need to be pressed in ascending order. If there are multiple answers, output the first one in dictionary order.

Sample Input 1_0 (for main_flip.c)

4
0 9 13

Sample Output 1_0

1 1 0 0
1 1 0 0
1 0 1 0
1 0 1 0

Sample Input 2_0 (for main_numOfLights.c)

4
0 9 13

Sample Output 2_0

8

Sample Input 3_0 (for main.c)

4
0 1 2 6 10 11 12 13 15

Sample Output 3

0 2 4 5 10






Discussion