#include #include #include int DEBUG = 0; typedef struct { int l; int i; } LI_t; typedef struct { int horizonalp; int size; int i; int j; } target_t; typedef struct { int a, b, c, d; } ans_t; int N, K; int L[500]; LI_t LI[500]; int A[60][60], B[60][60]; int FirstScore; int cmp(const void *a, const void *b) { return ((LI_t*)b)->l - ((LI_t*)a)->l; } int count_white(void) { int res = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { res += A[i][j] ^ 1; } } return res; } int calc_score(void) { return count_white() - FirstScore; } target_t get_target(int len) { int found = 0; target_t res; int max = 0; for (int i = 0; i < N; ++i) { int sum = 0; int cusum[N+1]; cusum[0] = sum; for (int j = 0; j < N; ++j) { cusum[j+1] = sum += A[i][j]; } for (int j = 0; j <= N-len; ++j) { if (cusum[j+len] - cusum[j] > max) { found = 1; max = cusum[j+len] - cusum[j]; res.horizonalp = 1; res.size = max; res.i = i; res.j = j; if (max >= len) return res; } } } for (int i = 0; i < N; ++i) { int sum = 0; int cusum[N+1]; cusum[0] = sum; for (int j = 0; j < N; ++j) { cusum[j+1] = sum += B[i][j]; } for (int j = 0; j <= N-len; ++j) { if (cusum[j+len] - cusum[j] > max) { found = 1; max = cusum[j+len] - cusum[j]; res.horizonalp = 0; res.size = max; res.i = i; res.j = j; if (max >= len) return res; } } } if (!found) { res.horizonalp = rand() % 2; res.size = -1; res.i = rand() % N; res.j = rand() % N; } return res; } int main(void) { srand(time(NULL)); scanf("%d %d", &N, &K); for (int i = 0; i < K; ++i) { int l; scanf("%d", &l); L[i] = l; LI[i].l = l; LI[i].i = i; } qsort(LI, K, sizeof(LI[0]), cmp); // for (int i = 0; i < K; ++i) { // printf("l:%d,i:%d ", LI[i].l, LI[i].i); // } for (int i = 0; i < N; ++i) { char s[100]; scanf("%s\n", s); for (int j = 0; j < N; ++j) { A[i][j] = B[j][i] = s[j] - 48; } } FirstScore = count_white(); if (DEBUG) printf("FirstScore: %d\n", FirstScore); ans_t ans[K]; for (int i = 0; i < K; ++i) { int a, b, c, d; target_t target = get_target(LI[i].l); if (target.j > N - LI[i].l) target.j = N - LI[i].l; if (target.horizonalp) { for (int j = target.j; j < target.j+LI[i].l; ++j) { A[target.i][j] ^= 1; B[j][target.i] ^= 1; } a = c = target.i+1; b = target.j+1; d = target.j+LI[i].l; } else { for (int j = target.j; j < target.j+LI[i].l; ++j) { B[target.i][j] ^= 1; A[j][target.i] ^= 1; } b = d = target.i+1; a = target.j+1; c = target.j+LI[i].l; } ans[LI[i].i].a = a; ans[LI[i].i].b = b; ans[LI[i].i].c = c; ans[LI[i].i].d = d; } for (int i = 0; i < K; ++i) { printf("%d %d %d %d\n", ans[i].a, ans[i].b, ans[i].c, ans[i].d); } if (DEBUG) printf("Score: %d\n", calc_score()); }