[remanufacturing] poj-3279 Flipile solution
I'm so weak. I record a violence I can't think of for two days
Title Link: POJ-3279.Fliptile
Students who understand the meaning of the question and just want to see the code suggest jumping here directly: Normal code
subject
meaning of the title
Give you a table composed of 0 and 1. Turn a box. You can change itself and the top, bottom, left and right squares from 0 to 1 and from 1 to 0
Ask you to output an operation table. How can you reverse all 0
Note:
- The output is the number of steps you operate each box, not the flip result of the original table
- If there are multiple results, output the one with the smallest dictionary order
Problem solving ideas
- The ontology needs violent enumeration. Try every flip case
However, each grid cannot be tried independently, because there are at most 2 ^ 225 possibilities, which is obviously unreasonable.
However, you can only use the first line to flip. There are only 2 ^ 15 possibilities at most. It can still be traversed - The second row and each subsequent row can determine whether to flip through the 0 / 1 value of the previous row
- The 0 / 1 value of each position can be used to judge its final result through the turnover of four positions [itself, left, right and upper]
Since the result of this grid is used to judge whether the grid below needs to be flipped, it is not necessary to judge the situation below [detailed below in combination with the code] - By the way, it's 0 / 1 because each grid can be turned once at most, because it's meaningless to turn more
Code block parsing
This module was added because the boss posted a code directly in the comment area below vj without comments at all. I finally understood it bit by bit, so I don't want to waste it.
Main function
#include <iostream>
using namespace std;
typedef int hip;
#include <bitset>
int main() {
ios::sync_with_stdio(0); cin.tie(0);
// Enter m rows and n columns of data
cin >> mLine >> nCloum;
for (hip i=1;i<=mLine;i++) for (hip j=1;j<=nCloum;j++) cin >> grass[i][j];
// Defines the minimum number of reversals and the number of reversals
hip ansFlip = 400;
hip ansType = -1;
// Only the first row is enumerated, and then the flipping mode of each row below is calculated according to the flipping result of the first row
// There are 2^n cases in the first line
// As an example:
// 4 4
// 1 0 0 1
// 0 1 1 0
// 0 1 1 0
// 1 0 0 1
// The value of iniType is 0 - 15
// The result of the corresponding first line is
// 0000,0001,0010,0011,0100,0101,0110,0111
// 1000,1001,1010,1011,1100,1101,1110,1111
// These 16 cases
for (hip iniType = 0; iniType < 1<<nCloum; iniType++) {
// Use bitset to automatically convert to binary
bitset<maxn> b = iniType;
// Record all the turnover times corresponding to this [first line turnover]
hip flipNum = 0;
// Mark first line
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++) {
f[iniType][1][cloumNo] = b[nCloum - cloumNo];
// If you flip, increase the number of records
if (b[nCloum - cloumNo]) flipNum += 1;
}
// Mark the flipping of the second line and after
// The marking method is: judge whether the corresponding position of the previous line is 1. If so, flip this grid
// Traverse the second line and every line after it
for (hip lineNo = 2; lineNo <= mLine; lineNo++)
// Traverse each column
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++)
// after_flip() is to judge whether the four positions of a grid [itself, left, right and upper] need to be flipped
// Then return your 0 / 1 value after flipping
// What is judged here is the grid in the previous row of this column. If it is 1, mark this grid as [need to be flipped]
// And turn the number of times + 1
if (after_flip(iniType, lineNo-1, cloumNo))
f[iniType][lineNo][cloumNo] = true, flipNum += 1;
else f[iniType][lineNo][cloumNo] = false;
// After marking the whole map, the upper grid should be 0 except the last line
// If this flipping scheme is feasible, the last line should also be all 0
// end_ line_ all_ The zero () function returns whether the last line of this scheme is all 0
// If all are 0 and the number of flips is the least, the tag is updated
if (end_line_all_zero(iniType) && ansFlip > flipNum)
ansType = iniType, ansFlip = flipNum;
}
// If the scheme mark is still - 1, it indicates that there is no feasible scheme, and the output is impossible
// On the contrary, the corresponding scheme [note format] is output
if (ansType!=-1) {
for (hip i=1;i<=mLine;i++) {
for (hip j=1;j<=nCloum;j++) {
cout << f[ansType][i][j];
if (j == nCloum) cout << endl;
else cout << ' ';
}
}
}
else cout << "IMPOSSIBLE" << endl;
return 0;
}
after_flip() function - returns the flip result of the previous line
hip mLine, nCloum;
// An array that stores grassland source data
bool grass[maxn][maxn];
// Table to store flipped grass:
// The boss's code is to recalculate the flip table after obtaining the feasible data number
// But for this problem, it will not exceed the limit so
// So here we simply save the flip table of each case
bool f[1<<maxn][maxn][maxn];
//Judge whether the grid here is out of bounds. If not, return true
bool not_out_of_range(hip line, hip cloum) {
return (line > 0 && line <= mLine && cloum > 0 && cloum <= nCloum);
}
// Coordinates of the next grid change to be judged
hip nextChange[4][2] = {{0,0}, {0,1}, {0,-1}, {-1,0}};
// Returns the result after the grid is affected by the [itself, left, right, top] flip
// The parameter is the data line number and cloum column number of iniType
bool after_flip(hip iniType, hip line, hip cloum) {
// Initialize tState to its original state
bool tState = grass[line][cloum];
// Traverse the other four grids that will affect this grid except the lower one. If you don't cross the boundary and flip it, flip the current grass
for (hip i = 0; i < 4; i++) {
hip nextLine = line + nextChange[i][0];
hip nextCloum = cloum + nextChange[i][1];
if (not_out_of_range(nextLine, nextCloum) && f[iniType][nextLine][nextCloum])
tState = !tState;
}
// Returns the flipped state
return tState;
}
end_line_all_zero() function - Returns whether the last line is all 0
bool end_line_all_zero(hip type) {
// This function is shown in the question, but you still need to call after_flip() function
// If it is 1 after flipping, it indicates that it is not all 0 and returns false
for (hip cloumNo=1;cloumNo<=nCloum;cloumNo++) if (after_flip(type, mLine, cloumNo)) return false;
// If false is not returned, it means all 0 after turning, then true is returned
return true;
}
Variable long code
//
// _ _ ___ ____ ___ ____ _____
//| | | | / _ \ _ __ / ___/ _ \| _ \| ____|
//| |_| | | | | | '_ \ | | | | | | | | | _|
//| _ | | |_| | | | | | |__| |_| | |_| | |___
//|_| |_|___\___/|_| |_| \____\___/|____/|_____|
// |_____|
//
#include <iostream>
using namespace std;
typedef int hip;
#include <bitset>
const int maxn = 19;
hip mLine, nCloum;
bool grass[maxn][maxn];
bool f[1<<maxn][maxn][maxn];
bool not_out_of_range(hip line, hip cloum) {
return (line > 0 && line <= mLine && cloum > 0 && cloum <= nCloum);
}
hip nextChange[4][2] = {{0,0}, {0,1}, {0,-1}, {-1,0}};
bool after_flip(hip iniType, hip line, hip cloum) {
bool tState = grass[line][cloum];
for (hip i = 0; i < 4; i++) {
hip nextLine = line + nextChange[i][0];
hip nextCloum = cloum + nextChange[i][1];
if (not_out_of_range(nextLine, nextCloum) && f[iniType][nextLine][nextCloum])
tState = !tState;
}
return tState;
}
bool end_line_all_zero(hip type) {
for (hip cloumNo=1;cloumNo<=nCloum;cloumNo++) if (after_flip(type, mLine, cloumNo)) return false;
return true;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> mLine >> nCloum;
for (hip i=1;i<=mLine;i++) for (hip j=1;j<=nCloum;j++) cin >> grass[i][j];
hip ansFlip = 400;
hip ansType = -1;
for (hip iniType = 0; iniType < 1<<nCloum; iniType++) {
bitset<maxn> b = iniType;
hip flipNum = 0;
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++) {
f[iniType][1][cloumNo] = b[nCloum - cloumNo];
if (b[nCloum - cloumNo]) flipNum += 1;
}
for (hip lineNo = 2; lineNo <= mLine; lineNo++)
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++)
if (after_flip(iniType, lineNo-1, cloumNo))
f[iniType][lineNo][cloumNo] = true, flipNum += 1;
else f[iniType][lineNo][cloumNo] = false;
if (end_line_all_zero(iniType) && ansFlip > flipNum)
ansType = iniType, ansFlip = flipNum;
}
if (ansType!=-1) {
for (hip i=1;i<=mLine;i++) {
for (hip j=1;j<=nCloum;j++) {
cout << f[ansType][i][j];
if (j == nCloum) cout << endl;
else cout << ' ';
}
}
}
else cout << "IMPOSSIBLE" << endl;
return 0;
}
Normal code
#include <iostream>
using namespace std;
typedef int hip;
#include <bitset>
const int maxn = 19;
hip m, n;
bool G[maxn][maxn];
bool f[1<<maxn][maxn][maxn];
bool R(hip l, hip c) {return (l > 0 && l <= m && c > 0 && c <= n);}
hip N[4][2] = {{0,0}, {0,1}, {0,-1}, {-1,0}};
bool F(hip i, hip l, hip c) {
bool t = G[l][c];
for (hip _ = 0; _ < 4; _++) {
hip nl = l + N[_][0], nc = c + N[_][1];
if (R(nl, nc) && f[i][nl][nc]) t = !t;
}
return t;
}
bool E(hip i) {
for (hip c=1;c<=n;c++) if (F(i, m, c)) return false;
return true;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> m >> n;
for (hip i=1;i<=m;i++) for (hip j=1;j<=n;j++) cin >> G[i][j];
hip r = 400;
hip t = -1;
for (hip i = 0; i < 1<<n; i++) {
bitset<maxn> b = i;
hip fn = 0;
for (hip c = 1; c <= n; c++) {
f[i][1][c] = b[n-c];
if (b[n-c]) fn += 1;
}
for (hip l = 2; l <= m; l++) for (hip c = 1; c <= n; c++)
if (F(i, l-1, c)) f[i][l][c] = true, fn += 1;
else f[i][l][c] = false;
if (E(i) && r > fn) t = i, r = fn;
}
if (t!=-1) {
for (hip i=1;i<=m;i++) for (hip j=1;j<=n;j++)
cout << f[t][i][j] << ((j==n)?"\n":" ");
}
else cout << "IMPOSSIBLE" << endl;
return 0;
}