谷歌面试 | 电面 | 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);
}
}