Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

int f[10][8][512],a[10],J[8][256],K[512][256],bit1[512];
vector <int> good;

void init()
{
    for (int i=0;i<512;i++)
    {
        for (int j=0;j<9;j++) bit1[i]+=((i>>j)&1);
        if (bit1[i]%2==0) good.push_back(i);
    }
    for (int i=0;i<=9;i++)
        for (int j=0;j<8;j++)
            for (int k=0;k<512;k++)
                f[i][j][k]=100;
    f[0][0][0]=0;
    for (int i=0;i<256;i++)
    {
        int x=good[i];
        for (int j=0;j<8;j++)
        {
            J[j][i]=j;
            for (int p=0;p<9;p++) 
                if ((x>>p)&1) J[j][i]^=(1<<(p/3));
        }
        for (int k=0;k<512;k++)
        {
            K[k][i]=k;
            for (int p=0;p<9;p++)
                if ((x>>p)&1) K[k][i]^=(1<<p);
        }
    }
}

int main()
{
    string s;
    for (int i=1;i<=9;i++) 
    {
        cin >> s;
        for (int j=0;j<9;j++) a[i]=a[i]*2+(s[j]=='1');
    }
    init();
    for (int i=0;i<9;i++)
        for (int j=0;j<8;j++)
            for (int k=0;k<512;k++)
                if (f[i][j][k]<100)
                    for (int s=0;s<256;s++)
                    {
                        int jj=J[j][s],kk=K[k][s];
                        if (i%3==2 && jj) continue;
                        f[i+1][jj][kk]=min(f[i+1][jj][kk],f[i][j][k]+bit1[a[i+1]^good[s]]);
                    }
    cout << f[9][0][0] << endl;
}

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<cstring>
#include<bitset>
#include<cstdio>
using namespace std;

int f[10][512][8], row[9];

void enter() {
    for(int i = 0; i < 9; ++i) {
        string s; cin >> s;
        row[i] = bitset<9>(s).to_ulong();
    }
}

int conv(int v) {
    return (__builtin_popcount(v & 7) & 1)
        | (__builtin_popcount(v >> 3 & 7) & 1) << 1
        | (__builtin_popcount(v >> 6 & 7) & 1) << 2;
}

void checkMin(int &a, int b) {
    if(b < a) a = b;
}

void solve() {
    memset(f, 0x3f, sizeof f);
    f[0][0][0] = 0;
    for(int i = 0; i < 9; ++i)
        for(int mask1 = 0; mask1 < 512; ++mask1)
            for(int mask2 = 0; mask2 < (i % 3 == 0 ? 1 : 8); ++mask2) if(f[i][mask1][mask2] < 82)
                for(int app = 0; app < 512; ++app) {
                    int v = row[i] ^ app;
                    if(__builtin_popcount(v) & 1) continue;
                    checkMin(f[i+1][mask1 ^ v][mask2 ^ conv(v)], f[i][mask1][mask2] + __builtin_popcount(app));
                }
    cout << f[9][0][0] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 9;
const int INF = 99;

int a[N][N];
int dp[N + 1][N][1 << N][1 << 3][2];

void minimize(int &a, int b) { a = a > b ? b : a; }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    char c;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        cin >> c; a[i][j] = c - '0';
    }
    int MC = 1 << N, MB = 1 << 3;
    for (int i = 0; i <= N; ++i) for (int j = 0; j < N; ++j)
        for (int C = 0; C < MC; ++C) for (int B = 0; B < MB; ++B)
            dp[i][j][C][B][0] = dp[i][j][C][B][1] = INF;
    dp[0][0][0][0][0] = 0;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) for (int C = 0; C < MC; ++C) for (int B = 0; B < MB; ++B) for (int p = 0; p <= 1; ++p) if (dp[i][j][C][B][p] < INF) {
        for (int x = 0; x <= 1; ++x) {
            int cost = x != a[i][j];
            int newC = C ^ (x ? (1 << j) : 0);
            int newB = B ^ (x ? (1 << (j / 3)) : 0);
            int newP = p ^ x;
            if (j + 1 == N && newP) continue;
            if (i % 3 == 2 && j % 3 == 2 && (newB >> (j / 3) & 1)) continue;
            int newI = i, newJ = j + 1;
            if (newJ == N) {
                if (i % 3 == 2) newB = 0;
                newP = 0;
                ++newI; newJ = 0;
            }
            minimize(dp[newI][newJ][newC][newB][newP], dp[i][j][C][B][p] + cost);
        }
    }
    cout << dp[N][0][0][0][0] << endl;
    return 0;
}

Code mẫu của RR

#include <stdio.h>
#include <string.h>
char a[9][9];
#define max(a,b) (a>b)?a:b
void solve(){
    int res=0,rx=0,r=0,rp=0,k,i,j,x,y,p;
    for (k=0;k<3;k++){
        rp=rx=0;
        for (i=0;i<3;i++){
            p=0;
            for (j=0;j<9;j++) p^=a[k*3+i][j]-'0';
            if (p) rp++;
        }
        for (i=0;i<3;i++){
            p=0;
            for (x=0;x<3;x++)
                for (y=0;y<3;y++) p^=a[k*3+x][i*3+y]-'0';
            if (p) rx++;
        }
        res+=max(rp,rx);
    }
    for (k=0;k<3;k++){
        rp=rx=0;
        for (i=0;i<3;i++){
            p=0;
            for (j=0;j<9;j++) p^=a[j][k*3+i]-'0';
            if (p) rp++;
        }
        for (i=0;i<3;i++){
            p=0;
            for (x=0;x<3;x++)
                for (y=0;y<3;y++) p^=a[i*3+y][k*3+x]-'0';
            if (p) rx++;
        }
        r+=max(rp,rx);
    }
    printf("%d\n",max(r,res));
}
int main(){
    int i; for (i=0;i<9;i++) gets(a[i]);
    solve();
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 100111
#define oo 1111111111
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int cot[9] = {0} ,hang[9] = {0},vuong[9] = {0} ,hangt[9],cott[9],vuongt[9];
string s[10];

int f(int i,int j){
     return (i/3)*3+j/3;
}

bool thoaman(){
     for(int i = 0;i<9;i++){
          if(cot[i]||hang[i]||vuong[i]) return false;
     }
     return true;
}

bool tim1(int x){
     if(x!=1){
     for(int i = 0;i<9;i++)
          for(int j = 0;j<9;j++){
               if(hang[i]+cot[j]+vuong[f(i,j)] == x){
                    hang[i] = 1-hang[i];
                    cot[j] = 1-cot[j];
                    vuong[f(i,j)] = 1-vuong[f(i,j)];
                    return true;
               }
          }
    }
    else{

     for(int i = 8;i>=0;i--)
         for(int j = 8;j>=0;j--)
          {
               if(hang[i]+cot[j]+vuong[f(i,j)] == x){
                    hang[i] = 1-hang[i];
                    cot[j] = 1-cot[j];
                    vuong[f(i,j)] = 1-vuong[f(i,j)];
                    return true;
               }
          }
    }   
    return false;
}

bool tim2(int x){
     if(x==1){
     for(int i = 0;i<9;i++)
          for(int j = 0;j<9;j++){
               if(hang[i]+cot[j]+vuong[f(i,j)] == x){
                    hang[i] = 1-hang[i];
                    cot[j] = 1-cot[j];
                    vuong[f(i,j)] = 1-vuong[f(i,j)];
                    return true;
               }
          }
    }
    else{

     for(int i = 8;i>=0;i--)
         for(int j = 8;j>=0;j--)
          {
               if(hang[i]+cot[j]+vuong[f(i,j)] == x){
                    hang[i] = 1-hang[i];
                    cot[j] = 1-cot[j];
                    vuong[f(i,j)] = 1-vuong[f(i,j)];
                    return true;
               }
          }
    }   
    return false;
}

int main(){
     for(int i = 0;i<9;i++){
          cin>>s[i];
          for(int j = 0;j<9;j++){
                if(s[i][j]=='1'){
                     hang[i] = 1-hang[i];
                     cot[j] = 1-cot[j];
                     vuong[f(i,j)] = 1-vuong[f(i,j)]; 
                }
          }
     }
     for(int i = 0;i<9;i++) hangt[i] = hang[i], cott[i] = cot[i], vuongt[i] = vuong[i];

     int kq1 = 0,kq2 = 0;
     while(!thoaman()){
          kq1++;    

          int t = 3;
          while(!tim1(t)) t--;

     }
     for(int i = 0;i<9;i++) hang[i] = hangt[i], cot[i] = cott[i], vuong[i] = vuongt[i];
     while(!thoaman()){
          kq2++;    

          int t = 3;
          while(!tim2(t)) t--;

     }
     printf("%d",min(kq1,kq2));
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

string grid[9];
int cell[9][9];
int diff[9][512];
int rowMask[512],colMask[512];
int prev[512][8][3];

vector<int> able;
vector<int> dp1[3];
int dp2[512][3];

void calcDiff(int idx) {
    int rowFrom = idx/3,colFrom = idx % 3;
    int xa = rowFrom * 3,xb = xa + 2,ya = colFrom * 3,yb = ya + 2;
    int element[9],num = 0;
    for (int i = xa; i <= xb; i++)
      for (int j = ya; j <= yb; j++) element[num++] = cell[i][j];
    for (int mask = 0; mask < 512; mask++)
      for (int i = 0; i < 9; i++)
        if ((mask & (1 << i)) > 0 != element[i] > 0) diff[idx][mask]++;
}

vector<int> firstDP(int low,int high) {
    for (int i = 0; i < 512; i++)
      for (int j = 0; j < 8; j++)
        for (int k = 0; k < 3; k++) prev[i][j][k] = 100;

    for (int i = 0; i < able.size(); i++) {
      int u = able[i];
      prev[colMask[u]][rowMask[u]][0] = min(prev[colMask[u]][rowMask[u]][0],diff[low][u]);
    }

    for (int i = 0; i < 2; i++)
      for (int j1 = 0; j1 < able.size(); j1++)
        for (int k1 = 0; k1 < 8; k1++) {
            int oldMask = able[j1],oldRow = k1;
            if (prev[oldMask][oldRow][i] < 0) continue;
            for (int j2 = 0; j2 < able.size(); j2++) {
                int newMask = colMask[able[j2]];
                newMask <<= ((i + 1) * 3);
                newMask ^= oldMask;
                int newRow = oldRow ^ rowMask[able[j2]];
                int tmp = prev[oldMask][oldRow][i] + diff[low + i + 1][able[j2]];
                prev[newMask][newRow][i + 1] = min(prev[newMask][newRow][i + 1],tmp);
            }
        }

    vector<int> ans(512);
    for (int i = 0; i < 512; i++) ans[i] = prev[i][0][2];
    return ans;
}

void secondDP() {
    for (int i = 0; i < 512; i++)
      for (int j = 0; j < 3; j++) dp2[i][j] = 100;

    for (int i = 0; i < 512; i++) dp2[i][0] = dp1[0][i];
    for (int j = 1; j < 3; j++)
      for (int oldMask = 0; oldMask < 512; oldMask++)
        for (int newMask = 0; newMask < 512; newMask++) {
            int next = oldMask ^ newMask;
            dp2[next][j] = min(dp2[next][j],dp2[oldMask][j - 1] + dp1[j][newMask]);
        }
}

int main() {
//    freopen("bsudoku.in","r",stdin);
//    freopen("bsudoku.out","w",stdout);

    for (int i = 0; i < 9; i++) cin >> grid[i];
    for (int i = 0; i < 9; i++)
      for (int j = 0; j < 9; j++) cell[i][j] = grid[i][j] - '0';

    for (int mask = 0; mask < 512; mask++) {
        int bit = 0;
        for (int i = 0; i < 9; i++) if (mask & (1 << i)) {
            rowMask[mask] ^= (1 << (i/3));
            colMask[mask] ^= (1 << (i%3));
            bit ^= 1;
        }
        if (bit == 0) able.push_back(mask);
    }
    for (int i = 0; i < 9; i++) calcDiff(i);
    for (int i = 0; i < 3; i++) dp1[i] = firstDP(i * 3,i * 3 + 2);
    secondDP();
    printf("%d\n", dp2[0][2]);
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
const int INF=107;
char fst[11][11];
int bc[531];
int row[11];
int col[11];
int sub[11];
int ssr[11];
int f[11][531][11];
int fc;
const int sb[]={7,56,448};
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
void init(void) {
    int i,j;
    for (i=0;i<9;i=i+1) scanf("%s",fst[i]);
    for (i=0;i<9;i=i+1)
        for (j=0;j<9;j=j+1) {
            row[i]=row[i]^(fst[i][j]-48);
            col[j]=col[j]^(fst[i][j]-48);
            sub[3*(i/3)+(j/3)]=sub[3*(i/3)+(j/3)]^(fst[i][j]-48);
        }
    //for (i=0;i<9;i=i+1) printf("%d ",row[i]); printf("\n");
    //for (i=0;i<9;i=i+1) printf("%d ",col[i]); printf("\n");
    for (i=0;i<9;i=i+1) fc=fc|(col[i]<<i);
    //printf("%d\n",fc);
    for (i=0;i<(1<<9);i=i+1)
        for (j=0;j<9;j=j+1)
            bc[i]=bc[i]+((i|(1<<j))==i);
    for (i=0;i<(1<<9);i=i+1) assert(bc[i]<10);
    for (i=0;i<3;i=i+1)
        for (j=0;j<3;j=j+1)
            ssr[i]=ssr[i]|(sub[3*i+j]<<j);
    //for (i=0;i<3;i=i+1) printf("%d ",ssr[i]); printf("\n");
    for (i=0;i<3;i=i+1) assert(ssr[i]<8);
}
int sub_change(const int &ch) { 
    int i;
    int ret=0;
    for (i=0;i<3;i=i+1)
        ret=ret|((bc[ch&sb[i]]%2)<<i);
    assert(ret<8);
    return (ret);
}
void optimize(void) {
    memset(f,0x3f,sizeof f);
    int r,sc,ss,ch,nss; 
    for (ch=0;ch<(1<<9);ch=ch+1)
        if ((row[0]+bc[ch])%2==0) {
            minimize(f[0][fc^ch][sub_change(ch)^ssr[0]],bc[ch]);
            //printf("Init f(%d,%d,%d)=%d\n",0,fc^ch,sub_change(ch)^ssr[0],f[0][fc^ch][sub_change(ch)^ssr[0]]);
        }           
    for (r=0;r<8;r=r+1)
        for (sc=0;sc<(1<<9);sc=sc+1)
            for (ss=0;ss<(1<<3);ss=ss+1)
                if (f[r][sc][ss]<INF && ((r%3!=2) || (ss==0)))
                    for (ch=0;ch<(1<<9);ch=ch+1)
                        if ((row[r+1]+bc[ch])%2==0) {
                            if (r%3==2) nss=ssr[r/3+1]^sub_change(ch);
                            else nss=ss^sub_change(ch);
                            minimize(f[r+1][sc^ch][nss],f[r][sc][ss]+bc[ch]);
                            //if (r<2) printf("Update from f(%d,%d,%d)=%d to f(%d,%d,%d)=%d with %d\n",r,sc,ss,f[r][sc][ss],r+1,sc^ch,nss,f[r+1][sc^ch][nss],ch);
                        }
    //printf("%d\n",f[2][1<<5][0]);
    printf("%d",f[8][0][0]);
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
    //freopen("tmp.out","w",stdout);
#endif
    init();
    optimize();
    return 0;
}