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 RR

#include <iostream>
#include <algorithm>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define REP(i,a)    for(int i=0; i<a;  i++)
#define TWO(x) (1<<(x))
#define CONTAIN(S,x) (S&TWO(x))
#define MAXROW 10111
#define MAXCOL 20
using namespace std;

int nRow, nCol;
char a[MAXROW][MAXCOL];
int f[TWO(16)][MAXCOL], nOne[MAXCOL], cost[MAXCOL][MAXCOL];

void inp() {
    scanf( "%d %d\n", &nRow, &nCol );
    REP(i, nRow)
        scanf( "%s\n", &a[i] );
}

int get( int mask, int lastCol) {
    if (f[mask][lastCol] >= 0) return f[mask][lastCol];
    if (!mask) return f[mask][lastCol] = 0;

    int newMask = mask - TWO(lastCol);

    if (newMask == 0) {
        return f[mask][lastCol] = nOne[lastCol];
    }

    int res = 1000111000;

    REP( prevCol, nCol)
        if (CONTAIN(newMask, prevCol) > 0) {
            res = min(res, get(newMask, prevCol) + cost[prevCol][lastCol] );
        }

    return f[mask][lastCol] = res;
}

void solve() {
    REP(j, nCol) {
        nOne[j] = 0;
        REP(i, nRow)
            if (a[i][j] == '1') nOne[j] ++;
    }

    REP(col1, nCol)
    REP(col2, nCol)
    if (col1 != col2) {
        cost[col1][col2] = 0;
        REP(i, nRow)
            if (a[i][col1] != a[i][col2])
                cost[col1][col2] ++;

        if (col1 == col2+1 || col1 == col2-1)
            cost[col1][col2] = min(cost[col1][col2], nOne[col2]);
    }

    REP(mask, TWO(nCol))
    REP(last, nCol)
        f[mask][last] = -1;

    int res = 1000111000;
    REP(lastCol, nCol)
        res = min( res, get(TWO(nCol)-1, lastCol) );

    printf("%d\n",res);
}

int main() {
//    freopen( "input.txt", "r", stdin );
//    freopen( "output.txt", "w", stdout );
    inp();
    solve();
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
int f[70000][17];

int TTD(int x) { return x>0 ? x:-x;}

int main()
{
    //freopen("NHPAINT.in","r",stdin);
    int n,m, a[17][17],b[17],chay=1,gt[17];
    char s[10010][17];
    scanf("%d %d",&m,&n);
    for(int i = 1;i<=m;i++)
         scanf("%s",s[i]);
    for(int i = 0;i<n;i++)
    {
        a[i][i] = 0;
        gt[i] = 0;
        for(int j = 1;j<=m;j++)
             if(s[j][i]=='1')
                  gt[i]++;
       // printf("%d\n",gt[i]);
    }
    for(int i = 0;i<n;i++)
        for(int j = i+1;j<n;j++)
        {
             a[i][j] = 0;
             for(int k = 1;k<=m;k++)
                 if(s[k][i]!=s[k][j])
                      a[i][j]++;
             a[j][i] = a[i][j];
             //printf("%d %d %d\n",i,j,a[i][j]);
        }
    for(int i = 0;i<n;i++)
        f[0][i] = 0;
    b[0] = 1;
    for(int i = 1;i<n;i++)
    {
        b[i] = b[i-1]*2;
        chay = chay + b[i];
    }
    for(int i = 1;i<=chay;i++)
    {
        int t[n],m= i;
        for(int j = 0;j<n;j++)
        {
            t[j] = m%2;
            m = m/2;
        }
        for(int j = 0;j<n;j++)
        {
            if(t[j]==0)
                f[i][j]=0;
            else if(b[j]==i) f[i][j] = gt[j];
            else
            {
                int min = 100000000;
                for(int k = 0;k<n;k++)
                {
                     if(t[k]!=0 && k!=j)
                     {
                          if(f[i-b[j]][k]+a[k][j] < min )
                              min = f[i-b[j]][k]+a[k][j];
                          if(TTD(k-j)==1 && f[i-b[j]][k]+gt[j] < min)
                              min =  f[i-b[j]][k]+gt[j];
                     }
                }  
               // if(min==0) printf("***%d %d***\n",i,j);    
                if(min == 100000000) f[i][j] = 0;
                else f[i][j] = min;
            }
        }
    }
    int Min = 100000000;
    for(int i = 0;i<n;i++)
         if(f[chay][i]<Min)
             Min =f[chay][i];
    printf("%d",Min);
    //getch();
}