SLIKAR - Slikar
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
int mx[4] = {0,0,1,1};
int my[4] = {0,1,0,1};
int n;
int a[520][520],b[520][520],fin[520][520];
int f[520][520][11],p0[520][520][11],p1[520][520][11];
int get(int x1,int y1,int x2,int y2)
{
return b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1];
};
int rec(int x,int y,int k)
{
if (f[x][y][k] != -1) return f[x][y][k];
if (!k)
{
f[x][y][k] = 0; return 0;
};
int best = 1000000000,len = 1 << (k - 1);
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) if (i != j)
{
int tmp = get(x + len * mx[i],y + len * my[i],x - 1 + len * mx[i] + len,y - 1 + len * my[i] + len); //color with 0
tmp += len * len - get(x + len * mx[j],y + len * my[j],x - 1 + len * mx[j] + len,y - 1 + len * my[j] + len); //color with 1
for (int t = 0; t < 4; t++) if (t != i && t != j)
tmp += rec(x + len * mx[t],y + len * my[t],k - 1);
if (best > tmp)
{
best = tmp; p0[x][y][k] = i; p1[x][y][k] = j;
};
};
f[x][y][k] = best; return best;
};
void track(int x,int y,int k)
{
if (!k)
{
fin[x][y] = a[x][y]; return;
};
int pos = p1[x][y][k],len = 1 << (k - 1);
for (int i = x + len * mx[pos]; i < x + len * mx[pos] + len; i++)
for (int j = y + len * my[pos]; j < y + len * my[pos] + len; j++) fin[i][j] = 1;
for (int t = 0; t < 4; t++) if (t != p0[x][y][k] && t != p1[x][y][k]) track(x + len * mx[t],y + len * my[t],k - 1);
};
int main()
{
// freopen("slikar.in","r",stdin);
// freopen("slikar.ou","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
char ch;
while (1)
{
scanf("%c", &ch);
if (ch == '0' || ch == '1') break;
};
a[i][j] = ch - '0';
};
/* for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++) cout << a[i][j];
cout << endl;
};*/
memset(b,0,sizeof(b));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) b[i][j] = a[i][j];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= n; j++) b[i][j] += b[i - 1][j];
for (int i = 1; i <= n; i++)
for (int j = 2; j <= n; j++) b[i][j] += b[i][j - 1];
memset(f,-1,sizeof(f));
int tmp = n,k = 0;
while (tmp > 1)
{
tmp /= 2; k++;
};
int ret = rec(1,1,k);
memset(fin,0,sizeof(fin));
track(1,1,k);
printf("%d\n", ret);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++) printf("%d", fin[i][j]);
printf("\n");
};
};