Solution Idea

50183. Lights out, again

main.c

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
 
#include "lights.h"
 
#ifndef MAXN
#define MAXN 4
#endif
 
typedef struct _toggle {
  bool toggle[MAXN * MAXN];
  int num;
} Toggles;
 
void printToggles(Toggles *toggles, int N)
{
  for (int i = 0; i < N * N; i++)
    if (toggles->toggle[i])
      printf("%d ", i);
  printf("\n");
}
 
void search(Toggles *toggles, Toggles *best, int level, int N, Lights *lights)
{
  if (level == N * N) {
    if (numOfLights(lights, N) == 0 && toggles->num < best->num)
      *best = *toggles;
    return;
  }
 
  toggles->num++;
  toggles->toggle[level] = true;
  flip(lights, level, N);
  search(toggles, best, level + 1, N, lights);
  toggles->num--;
  toggles->toggle[level] = false;
  flip(lights, level, N);
 
  search(toggles, best, level + 1, N, lights);
}
 
int main()
{
  Lights lights;
  init(&lights);
 
  int N;
  scanf("%d", &N);
 
  int index;
  while(scanf("%d", &index)!=EOF)
    flip(&lights, index, N);
 
  Toggles toggles;
  toggles.num = 0;
  for (int i = 0; i < N * N; i++)
    toggles.toggle[i] = false;
 
  Toggles best;
  best.num = N * N + 1;
 
  search(&toggles, &best, 0, N, &lights);
  printToggles(&best, N);
 
  return 0;
}

lights.c

#include <stdio.h>
#include "lights.h"
 
void init(Lights *lights)
{
  for (int i = 0; i < MAXN * MAXN; i++)
    lights->on[i] = false;
  lights->num = 0;
}
 
int numOfLights(Lights *lights, int N)
{
  return lights->num;
}
 
void flipOne(Lights *lights, int i)
{
  lights->on[i] = !lights->on[i];
  if (lights->on[i])
    lights->num++;
  else
    lights->num--;
}
 
void flip(Lights *lights, int i, int N)
{
  flipOne(lights, i);
  if (i % N != 0)
    flipOne(lights, i - 1);
  if (i % N != N - 1)
    flipOne(lights, i + 1);
  if (i / N != 0)
    flipOne(lights, i - N);
  if (i / N != N - 1)
    flipOne(lights, i + N);
}
 
void printLights(Lights *lights, int N)
{
  int index = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++, index++)
      printf("%d ", lights->on[index]);
    printf("\n");
  }
}

lights.h

#include <stdbool.h>
 
#define MAXN 4
 
typedef struct _lights{
  bool on[MAXN * MAXN];
  int num;
} Lights;
 
void init(Lights *lights);
int numOfLights(Lights *lights, int N);
void flip(Lights *lights, int i, int N);
void printLights(Lights *lights, int N);

Discussion