谷歌面试 | 电面 | Lights Out Puzzle

Problem

English

Given a binary 2D grid (each element can either be a 1 or a 0). You have the ability to choose any element and flip its value. The only condition is that when you choose to flip any element at index (r, c), the 4 neighbors of that element also get flipped. Find the minimum number of flips that you need to do in order to set all the elements in the matrix equal to 0. If it’s not possible, return -1.

Chinese

给定二维2D网格（每个元素要么是1，要么是0）。您可以选择任何元素并翻转其值。唯一的条件是，当您选择翻转索引为（r，c）的元素时，该元素的4个邻居也会被翻转。找到将矩阵中所有元素设置为0所需的最小翻转次数。如果不可能，则返回-1。

Example 1:

Input:
 [[0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]]
 
Output: 0

Example 2:

Input:
 [[0, 1, 0],
  [1, 1, 1],
  [0, 1, 0]]

Output: 1

Explanation: Flip (1, 1) to make the whole matrix consisting of only 0s.

Code

// Author: LiRe
#include <iostream>
#include <cstdio>
using namespace std;
#define INF 0x3fffff
char k[5][5]; int a[5][5];
int vx[5] = {-1, 0, 1, 0, 0}, vy[5] = {0, 1, 0, -1, 0};
inline void click(int c, int t) {
    for(int i = 0; i < 5; ++i)
        if(c + vx[i] >= 0 && t + vy[i] >= 0 && c + vx[i] < 5 && t + vy[i] < 5){
            a[c + vx[i]][t + vy[i]] ^= 1;
        }

}
int main() {
    int T; 
    scanf("%d", &T);
    while(T--) {
        for(int i = 0; i < 5; ++i)
            for(int j = 0; j < 5; ++j)
                cin>>k[i][j];
        for(int i = 0; i < 5; ++i)
            for(int j = 0; j < 5; ++j)
                a[i][j] = (int)(k[i][j] - '0');
        int ans = INF, cnt = 0, flag = 0;
        for(int i = 0; i < 32; ++i) {
            flag = 0; cnt = 0;
            for(int j = 0; j < 5; ++j)
                if((i >> j) & 1) ++cnt, click(0, j);
            for(int j = 0; j < 4; ++j) {
                for(int k = 0; k < 5; ++k) {
                    if(!a[j][k]) ++cnt, click(j + 1, k);
                }

            }
            for(int i = 0; i < 5; ++i)
                for(int j = 0; j < 5; ++j)
                    if(!a[i][j]) {flag = 1; break;}
            if(!flag) ans = min(ans, cnt);
            for(int i = 0; i < 5; ++i)
                for(int j = 0; j < 5; ++j)
                    a[i][j] = k[i][j] - '0';
        }
        if(ans == INF || ans > 6) printf("%d\n", -1);
        else printf("%d\n", ans);
    }
}