#include #define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++) using namespace std; const int INF = 1 << 28; vector dy = { -1, +1, +0, +0 }; vector dx = { +0, +0, -1, +1 }; int eval(vector< vector > &A, int N, int i, int j) { int w = 0; REP(k, 0, 4) { int y = i + dy[k]; int x = j + dx[k]; if(0 <= y && y < N && 0 <= x && x < N) { if(A[i][j] == A[y][x]) w++; } } return w; } int main(void) { int N, K; cin >> N >> K; vector L(K); REP(i, 0, K) cin >> L[i]; vector< vector > A(N, vector(N)); REP(i, 0, N) REP(j, 0, N) { char c; cin >> c; A[i][j] = c - '0'; } int init = 0; REP(i, 0, N) REP(j, 0, N) if(A[i][j] == 0) init++; vector lx(K), ly(K), rx(K), ry(K); REP(i, 0, K) { int maxw = -INF, maxt, maxy, maxx; REP(y, 0, N - L[i]) REP(x, 0, N) { int w = 0; if(L[i] <= 25) { REP(k, y, y + L[i]) A[k][x] = !A[k][x]; REP(k, y, y + L[i]) w += eval(A, N, k, x); REP(k, y, y + L[i]) A[k][x] = !A[k][x]; } REP(k, y, y + L[i]) { if(A[k][x] == 0) w--; if(A[k][x] == 1) w++; } if(w > maxw) { maxw = w; maxt = 0; maxy = y; maxx = x; } } REP(y, 0, N) REP(x, 0, N - L[i]) { int w = 0; if(L[i] <= 25) { REP(k, x, x + L[i]) A[y][k] = !A[y][k]; REP(k, x, x + L[i]) w += eval(A, N, y, k); REP(k, x, x + L[i]) A[y][k] = !A[y][k]; } REP(k, x, x + L[i]) { if(A[y][k] == 0) w--; if(A[y][k] == 1) w++; } if(w > maxw) { maxw = w; maxt = 1; maxy = y; maxx = x; } } if(maxt == 0) { ly[i] = maxy + 1; lx[i] = maxx + 1; ry[i] = maxy + L[i]; rx[i] = maxx + 1; REP(k, maxy, maxy + L[i]) A[k][maxx] = !A[k][maxx]; } if(maxt == 1) { ly[i] = maxy + 1; lx[i] = maxx + 1; ry[i] = maxy + 1; rx[i] = maxx + L[i]; REP(k, maxx, maxx + L[i]) A[maxy][k] = !A[maxy][k]; } } REP(i, 0, K) cout << ly[i] << " " << lx[i] << " " << ry[i] << " " << rx[i] << endl; #ifdef LOCAL int score = 0; REP(i, 0, N) REP(j, 0, N) if(A[i][j] == 0) score++; score -= init; cerr << "score: " << score << endl; // REP(i, 0, N) { // REP(j, 0, N) cerr << A[i][j]; // cerr << endl; // } #endif }