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

const max=250;
var a,b:array[1..max,1..max] of byte;
    h,v:array[1..max] of byte;
    m,n:byte;
    dem:longint;

procedure rf;
var i,j:byte;
begin
     fillchar(h,sizeof(h),0);
     fillchar(v,sizeof(v),0);
     readln(m,n);
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(a[i,j]);
               if a[i,j]=1 then
               begin
                    inc(h[i]);
                    inc(v[j]);
               end;
          end;
          readln;
     end;
end;

function find(var i:byte):byte;
var j:byte;
begin
     for j:=1 to m do
         if h[j] mod 2 = 1 then
         begin
              i:=j;
              exit(1);
         end;
     for j:=1 to n do
         if v[j] mod 2 = 1 then
         begin
              i:=j;
              exit(2);
         end;
     for j:=1 to m do
         if h[j]>0 then
         begin
              i:=j;
              exit(3);
         end;
     for j:=1 to n do
         if v[j]>0 then
         begin
              i:=j;
              exit(4);
         end;
     exit(0);
end;

procedure work(k,c:byte);
var i:byte;
begin
     if (k=1) or (k=3) then
     begin
          repeat
                for i:=1 to n do
                    if a[c,i]=1 then
                    begin
                         b[c,i]:=1+dem mod 2;
                         inc(dem);
                         dec(h[c]);
                         dec(v[i]);
                         a[c,i]:=0;
                         break;
                    end;
                c:=i;
                if v[c]=0 then break;
                for i:=1 to m do
                    if a[i,c]=1 then
                    begin
                         b[i,c]:=1+dem mod 2;
                         inc(dem);
                         dec(h[i]);
                         dec(v[c]);
                         a[i,c]:=0;
                         break;
                    end;
                c:=i;
                if h[c]=0 then break;
          until false;
     end
     else
     begin
          repeat
                for i:=1 to m do
                    if a[i,c]=1 then
                    begin
                         b[i,c]:=1+dem mod 2;
                         inc(dem);
                         dec(h[i]);
                         dec(v[c]);
                         a[i,c]:=0;
                         break;
                    end;
                c:=i;
                if h[c]=0 then break;
                for i:=1 to n do
                    if a[c,i]=1 then
                    begin
                         b[c,i]:=1+dem mod 2;
                         inc(dem);
                         dec(h[c]);
                         dec(v[i]);
                         a[c,i]:=0;
                         break;
                    end;
                c:=i;
                if v[c]=0 then break;
          until false;
     end;
end;

procedure pr;
var i,j:byte;
begin
     fillchar(b,sizeof(b),0);
     dem:=1;
     repeat
           i:=find(j);
           if i=0 then break;
           work(i,j);
     until false;
end;

procedure wf;
var i,j:byte;
begin
     for i:=1 to m do
     begin
          for j:=1 to n do
              write(b[i,j],' ');
          writeln;
     end;
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <vector>

#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 FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define MAXN 255
#define P pair<int,int>
#define X first
#define Y second
#define PB push_back
using namespace std;

int m,n,a[MAXN][MAXN],ind[MAXN][MAXN],npoint,color[MAXN*MAXN];
P pos[MAXN*MAXN];
vector<int> ke[MAXN*MAXN];

void inp() {
    scanf("%d %d",&m,&n);
    FOR(i,1,m)
    FOR(j,1,n) {
        scanf("%d",&a[i][j]);
        if (a[i][j]) {
            npoint++;
            pos[npoint].X=i; pos[npoint].Y=j;
            ind[i][j]=npoint; 
        }
    }
}

void init() {
    int last;
    FOR(i,1,m) {
        int cnt=0;
        FOR(j,1,n)
            if (a[i][j]) {
                if (cnt&1) {
                    ke[ind[i][j]].PB(last);
                    ke[last].PB(ind[i][j]);
                }
                cnt++;
                last=ind[i][j];
            }
    }

    FOR(j,1,n) {
        int cnt=0;
        FOR(i,1,m)
            if (a[i][j]) {
                if (cnt&1) {
                    ke[ind[i][j]].PB(last);
                    ke[last].PB(ind[i][j]);
                }
                cnt++;
                last=ind[i][j];
            }
    }
}

int first,last,qu[MAXN*MAXN],n1,n2;

inline void paint(int u,int k) {
    color[u]=k;
    if (k==1) n1++;
    else n2++;
}

void bfs(int u) {
    first=1; last=1; qu[1]=u;
    if (n1<n2) paint(u,1);
    else paint(u,2);
    while (first<=last) {
        u=qu[first]; first++;
        FORV(v,ke[u])
        if (!color[*v]) {
            paint(*v,3-color[u]);
            last++; qu[last]=*v;
        }
    }
}

void solve() {
    n1 = n2 = 0;
    FOR(i,1,m)
    FOR(j,1,n)
        if (a[i][j] && !color[ind[i][j]]) {
            bfs(ind[i][j]);
        }

    FOR(i,1,m) {
        FOR(j,1,n)
            if (!a[i][j]) printf("0 ");
            else printf("%d ",color[ind[i][j]]);
        printf("\n");
    }
}

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

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#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 Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) {
    stringstream ss;
    if (p >= 0)
        ss << fixed << setprecision(p);
    ss << a;
    T r;
    ss >> r;
    return r;
}
template<class T> T gcd(T a, T b) {
    T r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
template<class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template<class T> T sqr(T x) {
    return x * x;
}
template<class T> T cube(T x) {
    return x * x * x;
}
template<class T> int getbit(T s, int i) {
    return (s >> i) & 1;
}
template<class T> T onbit(T s, int i) {
    return s | (T(1) << i);
}
template<class T> T offbit(T s, int i) {
    return s & (~(T(1) << i));
}
template<class T> int cntbit(T s) {
    return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;
const ld PI = acos(-1.0);
const ld eps = 1e-12;
const int dr[] = { -1, 0, +1, 0};
const int dc[] = { 0, +1, 0, -1};
const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e18 + 5;
const int mod = (ll) (1e9 + eps);

using namespace std;
#define maxv 1005
#define maxe 250005

struct Dinic {
    int n, s, t, E, adj[maxe], flow[maxe], cap[maxe], next[maxe], last[maxv], run[maxv], level[maxv], que[maxv];

    void init(int _n, int _s, int _t) {
        n = _n; s = _s; t = _t; E = 0;
        For(i, 0, n) last[i] = -1;
    }

    void add(int u, int v, int c1, int c2) {
        adj[E] = v; flow[E] = 0; cap[E] = c1; next[E] = last[u]; last[u] = E++;
        adj[E] = u; flow[E] = 0; cap[E] = c2; next[E] = last[v]; last[v] = E++;
    }

    bool bfs() {
        For(i, 0, n) level[i] = -1;
        level[s] = 0;

        int qsize = 0;
        que[qsize++] = s;

        Rep(i, qsize) {
            for (int u = que[i], e = last[u]; e != -1; e = next[e]) {
                int v = adj[e];
                if (flow[e] < cap[e] && level[v] == -1) {
                    level[v] = level[u] + 1;
                    que[qsize++] = v;
                }
            }
        }

        return level[t] != -1;
    }

    int dfs(int u, int bot) {
        if (u == t) return bot;
        for (int &e = run[u]; e != -1; e = next[e]) {
            int v = adj[e], delta = 0;
            if (level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0) {
                flow[e] += delta; flow[e ^ 1] -= delta;
                return delta;
            }
        }
        return 0;
    }

    int maxflow() {
        int total = 0;
        while (bfs()) {
            For(i, 0, n) run[i] = last[i];
            for (int delta = dfs(s, inf); delta > 0; delta = dfs(s, inf)) total += delta;
        }
        return total;
    }
} dinic;

int n, m, row[maxv], col[maxv], oddrow, oddcol, a[maxv][maxv], sum;

int main(){
//  freopen("in.txt", "r", stdin);

    cin >> n >> m;
    ms(row, 0); ms(col, 0); sum = 0;
    dinic.init(n + m + 4, n + m + 3, n + m + 4);
    For(i, 1, n) For(j, 1, m) {
        scanf("%d", &a[i][j]);
        row[i] += a[i][j];
        col[j] += a[i][j];
        sum += a[i][j];
    }

    oddrow = 0; oddcol = 0;
    For(i, 1, n) oddrow += (row[i] & 1);
    For(i, 1, m) oddcol += (col[i] & 1);

    For(i, 1, n) For(j, 1, m) if(a[i][j]){
        dinic.add(i, j + n, 1, 0);
    }

    For(i, 1, n) dinic.add(n + m + 1, i, row[i] / 2, 0);
    For(i, 1, m) dinic.add(i + n, n + m + 2, col[i] / 2, 0);
    dinic.add(n + m + 3, n + m + 1, sum / 2, 0);
    dinic.add(n + m + 2, n + m + 4, sum / 2, 0);
    dinic.maxflow();
    if(oddrow > oddcol){
        Rep(i, n) dinic.cap[i * 2 + sum * 2] = row[i + 1] - row[i + 1] / 2;
        dinic.maxflow();
        Rep(i, m) dinic.cap[i * 2 + n * 2 + sum * 2] = col[i + 1] - col[i + 1] / 2;
        dinic.maxflow();
    }
    else{
        Rep(i, m) dinic.cap[i * 2 + n * 2 + sum * 2] = col[i + 1] - col[i + 1] / 2;
        dinic.maxflow();
        Rep(i, n) dinic.cap[i * 2 + sum * 2] = row[i + 1] - row[i + 1] / 2;
        dinic.maxflow();
    }

    int run = 0;
    For(i, 1, n) For(j, 1, m){
        if(a[i][j]){
            if(dinic.flow[run]) printf("1%c", j == m ? '\n' : ' ');
            else printf("2%c", j == m ? '\n' : ' ');
            run += 2;
        }
        else printf("0%c", j == m ? '\n' : ' ');
    }

    return 0;
}

Code mẫu của ll931110

{$R+,Q+}
{$MODE DELPHI}
program GARDEN25;
const
  input = '';
  output = '';
  maxn = 250;
var
  hz,ve,a,res: array[1..maxn,1..maxn] of integer;
  free: array[1..maxn,1..maxn] of boolean;
  m,n,delta: integer;

procedure init;
var
  f: text;
  i,j: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, m, n);
  for i := 1 to m do
    for j := 1 to n do read(f, a[i,j]);

  close(f);
  delta := 0;
end;

procedure construct;
var
  t,i,j: integer;
begin
  fillchar(hz, sizeof(hz), 0);
  fillchar(ve, sizeof(ve), 0);

  for i := 1 to m do
    begin
      t := 0;
      for j := 1 to n do if a[i,j] = 1 then
        if t = 0 then t := j else
          begin
            hz[i,t] := j;
            hz[i,j] := t;
            t := 0;
          end;
    end;

  for j := 1 to n do
    begin
      t := 0;
      for i := 1 to m do if a[i,j] = 1 then
        if t = 0 then t := i else
          begin
            ve[t,j] := i;
            ve[i,j] := t;
            t := 0;
          end;
    end;
end;

procedure DFS(i,j: integer);
var
  k,t: integer;
begin
  free[i,j] := false;

  t := hz[i,j];
  if (t <> 0) and (a[i,t] = 1) then
    if free[i,t] then
      begin
        res[i,t] := 3 - res[i,j];
        if res[i,t] = 1 then inc(delta) else dec(delta);
        DFS(i,t);
      end;

  t := ve[i,j];
  if (t <> 0) and (a[t,j] = 1) then
    if free[t,j] then
      begin
        res[t,j] := 3 - res[i,j];
        if res[t,j] = 1 then inc(delta) else dec(delta);
        DFS(t,j);
      end;
end;

procedure solve;
var
  i,j: integer;
begin
  fillchar(free, sizeof(free), true);
  fillchar(res, sizeof(res), 0);

  for i := 1 to m do
    for j := 1 to n do if free[i,j] and (a[i,j] = 1) then
      begin
        if delta <= -1 then
          begin
            inc(delta);
            res[i,j] := 1;
          end
        else
          begin
            dec(delta);
            res[i,j] := 2;
          end;
        DFS(i,j);
      end;
end;

procedure printresult;
var
  f: text;
  i,j: integer;
begin
  assign(f, output);
    rewrite(f);

  for i := 1 to m do
    begin
      write(f, res[i,1]);
      for j := 2 to n do write(f, ' ', res[i,j]);
      if i <> m then writeln(f);
    end;
  close(f);
end;

begin
  init;
  construct;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   555
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int INF=(int)1e9+7;
class DinicFlow {
    public:
    vector<int> dist,head,q,work;
    vector<int> point,capa,flow,next;
    int n,m;
    DinicFlow() {
        n=0;m=0;
    }
    DinicFlow(int n) {
        this->n=n;m=0;
        dist.assign(n+7,0);
        head.assign(n+7,-1);
        q.assign(n+7,0);
        work.assign(n+7,0);
    }
    void addedge(int u,int v,int c1,int c2) {
        point.push_back(v);capa.push_back(c1);flow.push_back(0);next.push_back(head[u]);head[u]=m++;
        point.push_back(u);capa.push_back(c2);flow.push_back(0);next.push_back(head[v]);head[v]=m++;
    }
    bool bfs(int s,int t) {
        FOR(i,1,n) dist[i]=-1;
        int sz=0;
        q[sz++]=s;dist[s]=0;
        REP(x,sz) {
            int u=q[x];
            for (int i=head[u];i>=0;i=next[i])
                if (dist[point[i]]<0 && flow[i]<capa[i]) {
                    dist[point[i]]=dist[u]+1;
                    q[sz++]=point[i];
                }
        }
        return (dist[t]>=0);
    }
    int dfs(int s,int t,int f) {
        if (s==t) return (f);
        for (int &i=work[s];i>=0;i=next[i])
            if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
                int d=dfs(point[i],t,min(f,capa[i]-flow[i]));
                if (d>0) {
                    flow[i]+=d;
                    flow[i^1]-=d;
                    return (d);
                }
            }
        return (0);
    }
    int getflow(int s,int t) {
        int totflow=0;
        while (bfs(s,t)) {
            FOR(i,1,n) work[i]=head[i];
            while (true) {
                int d=dfs(s,t,INF);
                if (d<=0) break;
                totflow+=d;
            }
        }
        return (totflow);
    }
};
class DemandFlow {
    public:
    DinicFlow G;
    vector<int> si,so;
    int n;
    DemandFlow() {
        n=0;
    }
    DemandFlow(int n) {
        this->n=n;
        si.assign(n+7,0);
        so.assign(n+7,0);
        G=DinicFlow(n+2);
    }
    void addedge(int u,int v,int d,int c) {
        si[v]+=d;
        so[u]+=d;
        G.addedge(u,v,c-d,0);
    }
    bool haveflow(int s,int t) {
        int sd=0;
        FOR(i,1,n) {
            sd+=si[i];
            if (si[i]>0) G.addedge(n+1,i,si[i],0);
            if (so[i]>0) G.addedge(i,n+2,so[i],0);
        }
        G.addedge(t,s,INF-7,0);
        return (G.getflow(n+1,n+2)==sd);
    }
};
DemandFlow DF;
int n,m,cnt;
int sr[MAX],sc[MAX],a[MAX][MAX];
void process(void) {
    scanf("%d%d",&m,&n);
    DF=DemandFlow(m+n+3);
    FOR(i,1,m) FOR(j,1,n) {
        scanf("%d",&a[i][j]);
        if (a[i][j]) {
            sr[i]++;
            sc[j]++;
            cnt++;
            DF.addedge(i,m+j,0,1);
        }
    }
    FOR(i,1,m) DF.addedge(m+n+1,i,sr[i]/2,sr[i]-sr[i]/2);
    FOR(i,1,n) DF.addedge(m+i,m+n+2,sc[i]/2,sc[i]-sc[i]/2);
    DF.addedge(m+n+3,m+n+1,cnt/2,cnt-cnt/2);
    assert(DF.haveflow(m+n+3,m+n+2));
    int id=0;
    FOR(i,1,m) FOR(j,1,n) {
        if (a[i][j]) printf("%d",2-DF.G.flow[2*id++]); else printf("0");
        if (j<n) printf(" "); else printf("\n");
    }
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif
    int id=0;
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
using namespace std;

int m, n;
int a[255][255], b[255][255];
int degx[255], degy[255];
// int start_color;
int C[3];

void gox(int i, int color);
void goy(int j, int color);

void gox(int i, int color) {
    for(int j=0;j<n;++j)
        if(a[i][j] == 1 && b[i][j] == 0) {
            b[i][j] = color;
            ++C[color];
            --degx[i]; --degy[j];
            goy( j, 3 - color);
            return;
        }
}

void goy(int j, int color) {
    for(int i=0;i<m;++i)
        if(a[i][j] == 1 && b[i][j] == 0) {
            b[i][j] = color;
            ++C[color];
            --degx[i]; --degy[j];
            gox( i, 3 - color);
            return;
        }
}

int main() {
    scanf("%d%d", &m, &n);
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j)
            scanf("%d", &a[i][j]);
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j)
            if(a[i][j]) {
                ++degx[i];
                ++degy[j];
            }
    // start_color = 1;
    for(int i=0;i<m;++i)
        if(degx[i] % 2 == 1) {
            if(C[1] > C[2]) gox( i, 2);
            else gox( i, 1);
            // start_color = 3 - start_color;
        }
    for(int j=0;j<n;++j)
        if(degy[j] % 2 == 1) {
            if(C[1] > C[2]) goy( j, 2);
            else goy( j, 1);
            // goy( j, start_color);
            // start_color = 3 - start_color;
        }
    for(int i=0;i<m;++i)
        if(degx[i] > 0)
            gox( i, 1);
    for(int j=0;j<n;++j)
        if(degy[j] > 0)
            goy( j, 1);
    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) printf("%d ", b[i][j]);
        printf("\n");
    }
    // system("pause");
    return 0;   
}