#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template < class S, class T> inline S chmin( S & a, T b) {
if ( a> b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
int x;
int y;
int xy;
int arr[ 3 ] [ 3 ] ;
int dx[ 5 ] = { 0 , - 1 , 1 , 0 , 0 } ;
int dy[ 5 ] = { 0 , 0 , 0 , - 1 , 1 } ;
class Solution{
public :
int minFlips( vector< vector< int >> & mat) {
int mask;
int i;
int j;
int si;
int sj;
int d;
int cnt;
int res = 1073709056 ;
x = mat.size ( ) ;
y = mat[ 0 ] .size ( ) ;
xy = x * y;
for ( mask= ( 0 ) ; mask< ( ( 1 << xy) ) ; mask++ ) {
cnt = 0 ;
for ( i= ( 0 ) ; i< ( x) ; i++ ) {
for ( j= ( 0 ) ; j< ( y) ; j++ ) {
arr[ i] [ j] = mat[ i] [ j] ;
}
}
for ( i= ( 0 ) ; i< ( x) ; i++ ) {
for ( j= ( 0 ) ; j< ( y) ; j++ ) {
if ( mask & ( 1 << ( i* y+ j) ) ) {
cnt++ ;
for ( d= ( 0 ) ; d< ( 5 ) ; d++ ) {
si = i + dx[ d] ;
sj = j + dy[ d] ;
if ( 0 <= si && si < x && 0 <= sj && sj < y) {
arr[ si] [ sj] ^ = 1 ;
}
}
}
}
}
for ( i= ( 0 ) ; i< ( x) ; i++ ) {
for ( j= ( 0 ) ; j< ( y) ; j++ ) {
if ( arr[ i] [ j] ) {
goto Lj4PdHRW;
}
}
}
chmin( res, cnt) ;
Lj4PdHRW:;
}
if ( res== 1073709056 ) {
res = - 1 ;
}
return res;
}
}
;
// cLay varsion 20191214-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int x, y, xy;
// int arr[3][3];
// int dx[5] = {0, -1, 1, 0, 0};
// int dy[5] = {0, 0, 0, -1, 1};
//
// class Solution {
// public:
// int minFlips(vector<vector<int>>& mat) {
// int i, j, si, sj, d, cnt;
// int res = int_inf;
//
// x = mat.size();
// y = mat[0].size();
// xy = x * y;
//
// rep(mask,(1<<xy)){
// cnt = 0;
// rep(i,x) rep(j,y) arr[i][j] = mat[i][j];
// rep(i,x) rep(j,y) if(mask & (1<<(i*y+j))){
// cnt++;
// rep(d,5){
// si = i + dx[d];
// sj = j + dy[d];
// if(0 <= si < x && 0 <= sj < y) arr[si][sj] ^= 1;
// }
// }
// rep(i,x) rep(j,y) if(arr[i][j]) break_break_continue;
// res <?= cnt;
// }
// if(res==int_inf) res = -1;
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBTIGNobWluKFMgJmEsIFQgYil7CiAgaWYoYT5iKXsKICAgIGE9YjsKICB9CiAgcmV0dXJuIGE7Cn0KI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICByZXR1cm4gMDsKfQojdW5kZWYgbWFpbgppbnQgeDsKaW50IHk7CmludCB4eTsKaW50IGFyclszXVszXTsKaW50IGR4WzVdID0gezAsIC0xLCAxLCAwLCAwfTsKaW50IGR5WzVdID0gezAsIDAsIDAsIC0xLCAxfTsKY2xhc3MgU29sdXRpb257CiAgcHVibGljOgogIGludCBtaW5GbGlwcyh2ZWN0b3I8dmVjdG9yPGludD4+JiBtYXQpewogICAgaW50IG1hc2s7CiAgICBpbnQgaTsKICAgIGludCBqOwogICAgaW50IHNpOwogICAgaW50IHNqOwogICAgaW50IGQ7CiAgICBpbnQgY250OwogICAgaW50IHJlcyA9IDEwNzM3MDkwNTY7CiAgICB4ID0gbWF0LnNpemUoKTsKICAgIHkgPSBtYXRbMF0uc2l6ZSgpOwogICAgeHkgPSB4ICogeTsKICAgIGZvcihtYXNrPSgwKTttYXNrPCgoMTw8eHkpKTttYXNrKyspewogICAgICBjbnQgPSAwOwogICAgICBmb3IoaT0oMCk7aTwoeCk7aSsrKXsKICAgICAgICBmb3Ioaj0oMCk7ajwoeSk7aisrKXsKICAgICAgICAgIGFycltpXVtqXSA9IG1hdFtpXVtqXTsKICAgICAgICB9CiAgICAgIH0KICAgICAgZm9yKGk9KDApO2k8KHgpO2krKyl7CiAgICAgICAgZm9yKGo9KDApO2o8KHkpO2orKyl7CiAgICAgICAgICBpZihtYXNrICYgKDE8PChpKnkraikpKXsKICAgICAgICAgICAgY250Kys7CiAgICAgICAgICAgIGZvcihkPSgwKTtkPCg1KTtkKyspewogICAgICAgICAgICAgIHNpID0gaSArIGR4W2RdOwogICAgICAgICAgICAgIHNqID0gaiArIGR5W2RdOwogICAgICAgICAgICAgIGlmKDAgPD0gc2kgICYmICBzaSA8IHggJiYgMCA8PSBzaiAgJiYgIHNqIDwgeSl7CiAgICAgICAgICAgICAgICBhcnJbc2ldW3NqXSBePSAxOwogICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgfQogICAgICAgIH0KICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoeCk7aSsrKXsKICAgICAgICBmb3Ioaj0oMCk7ajwoeSk7aisrKXsKICAgICAgICAgIGlmKGFycltpXVtqXSl7CiAgICAgICAgICAgIGdvdG8gTGo0UGRIUlc7CiAgICAgICAgICB9CiAgICAgICAgfQogICAgICB9CiAgICAgIGNobWluKHJlcywgY250KTsKICAgICAgTGo0UGRIUlc6OwogICAgfQogICAgaWYocmVzPT0xMDczNzA5MDU2KXsKICAgICAgcmVzID0gLTE7CiAgICB9CiAgICByZXR1cm4gcmVzOwogIH0KfQo7Ci8vIGNMYXkgdmFyc2lvbiAyMDE5MTIxNC0xCgovLyAtLS0gb3JpZ2luYWwgY29kZSAtLS0KLy8gI2RlZmluZSBtYWluIGR1bW15X21haW4KLy8ge30KLy8gI3VuZGVmIG1haW4KLy8gCi8vIGludCB4LCB5LCB4eTsKLy8gaW50IGFyclszXVszXTsKLy8gaW50IGR4WzVdID0gezAsIC0xLCAxLCAwLCAwfTsKLy8gaW50IGR5WzVdID0gezAsIDAsIDAsIC0xLCAxfTsKLy8gCi8vIGNsYXNzIFNvbHV0aW9uIHsKLy8gcHVibGljOgovLyAgIGludCBtaW5GbGlwcyh2ZWN0b3I8dmVjdG9yPGludD4+JiBtYXQpIHsKLy8gICAgIGludCBpLCBqLCBzaSwgc2osIGQsIGNudDsKLy8gICAgIGludCByZXMgPSBpbnRfaW5mOwovLyAKLy8gICAgIHggPSBtYXQuc2l6ZSgpOwovLyAgICAgeSA9IG1hdFswXS5zaXplKCk7Ci8vICAgICB4eSA9IHggKiB5OwovLyAKLy8gICAgIHJlcChtYXNrLCgxPDx4eSkpewovLyAgICAgICBjbnQgPSAwOwovLyAgICAgICByZXAoaSx4KSByZXAoaix5KSBhcnJbaV1bal0gPSBtYXRbaV1bal07Ci8vICAgICAgIHJlcChpLHgpIHJlcChqLHkpIGlmKG1hc2sgJiAoMTw8KGkqeStqKSkpewovLyAgICAgICAgIGNudCsrOwovLyAgICAgICAgIHJlcChkLDUpewovLyAgICAgICAgICAgc2kgPSBpICsgZHhbZF07Ci8vICAgICAgICAgICBzaiA9IGogKyBkeVtkXTsKLy8gICAgICAgICAgIGlmKDAgPD0gc2kgPCB4ICYmIDAgPD0gc2ogPCB5KSBhcnJbc2ldW3NqXSBePSAxOwovLyAgICAgICAgIH0KLy8gICAgICAgfQovLyAgICAgICByZXAoaSx4KSByZXAoaix5KSBpZihhcnJbaV1bal0pIGJyZWFrX2JyZWFrX2NvbnRpbnVlOwovLyAgICAgICByZXMgPD89IGNudDsKLy8gICAgIH0KLy8gICAgIGlmKHJlcz09aW50X2luZikgcmVzID0gLTE7Ci8vICAgICByZXR1cm4gcmVzOwovLyAgIH0KLy8gfTsK