44J - Triminoes - CodeForces Solution

/* -*- coding: utf-8 -*-
 *
 * 0044J.cc: J. Triminoes
 */

#include<cstdio>
#include<queue>
#include<algorithm>
#include<utility>
 
using namespace std;

/* constant */

const int MAX_H = 1000;
const int MAX_W = 1000;
const int dxs[] = { 1, 0, -1, 0 }, dys[] = { 0, -1, 0, 1 };

/* typedef */

typedef pair<int,int> pii;
typedef queue<pii> qpii;
typedef queue<int> qi;

/* global variables */

char fs[MAX_H][MAX_W + 4];
int bds[MAX_H][MAX_W], gs[MAX_H][MAX_W];

/* subroutines */

inline bool inside(int y, int x, int h, int w) {
  return y >= 0 && y < h && x >= 0 && x < w;
}

inline bool valid(int y0, int x0, int di, int h, int w) {
  int y1 = y0 + dys[di], x1 = x0 + dxs[di];
  int y2 = y1 + dys[di], x2 = x1 + dxs[di];
  return
    inside(y0, x0, h, w) && inside(y2, x2, h, w) &&
    fs[y0][x0] == 'w' && bds[y0][x0] < 0 &&
    fs[y1][x1] == 'b' && bds[y1][x1] < 0 &&
    fs[y2][x2] == 'w' && bds[y2][x2] < 0;
}

inline void check(int y, int x, int h, int w, int &bits) {
  if (inside(y, x, h, w) && gs[y][x] >= 0) bits |= (1 << gs[y][x]);
}

inline int unused(int bits) {
  int b = 0;
  while (bits & 1) b++, bits >>= 1;
  return b;
}

/* main */

int main() {
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);

  int h, w;
  scanf("%d%d", &h, &w);

  qpii q;
  int wn = 0, bn = 0;
  for (int y = 0; y < h; y++) {
    scanf("%s", fs[y]);
    for (int x = 0; x < w; x++) {
      if (fs[y][x] == 'w') wn++, q.push(pii(y, x));
      else if (fs[y][x] == 'b') bn++;
    }
  }
  //printf("wn=%d, bn=%d\n", wn, bn);

  if (wn != bn * 2) { puts("NO"); return 0; }

  for (int y = 0; y < h; y++) fill(bds[y], bds[y] + w, -1);
  int gn = 0;

  while (! q.empty()) {
    qpii q1;
    bool cont = false;
    while (! q.empty()) {
      auto u = q.front(); q.pop();
      int y = u.first, x = u.second;
      if (bds[y][x] >= 0) continue;

      int c = 0, udi = -1;
      for (int di = 0; di < 4; di++)
	if (valid(y, x, di, h, w)) c++, udi = di;
      if (c == 0) { puts("NO"); return 0; }
      if (c == 1) {
	bds[y][x] =
	  bds[y + dys[udi]][x + dxs[udi]] =
	  bds[y + dys[udi] * 2][x + dxs[udi] * 2] = gn++;
	cont = true;
      }
      else
	q1.push(u);
    }

    if (! cont && ! q1.empty()) { puts("NO"); return 0; }
    swap(q, q1);
  }

  //for (int y = 0; y < h; y++)
  //for (int x = 0; x < w; x++)
  //printf("%2d%c", bds[y][x], (x + 1 < w) ? ' ' : '\n');

  for (int y = 0; y < h; y++) fill(gs[y], gs[y] + w, -1);

  for (int y = 0; y < h; y++)
    for (int x = 0; x < w; x++)
      if (fs[y][x] == 'w' && gs[y][x] < 0) {
	if (x + 2 < w && bds[y][x] == bds[y][x + 2]) {
	  int bits = 0;
	  check(y, x - 1, h, w, bits);
	  check(y, x + 3, h, w, bits);
	  for (int x0 = x; x0 <= x + 2; x0++) {
	    check(y - 1, x0, h, w, bits);
	    check(y + 1, x0, h, w, bits);
	  }
	  int c = unused(bits);
	  gs[y][x] = gs[y][x + 1] = gs[y][x + 2] = c;
	}
	else if (y + 2 < h && bds[y][x] == bds[y + 2][x]) {
	  int bits = 0;
	  check(y - 1, x, h, w, bits);
	  check(y + 3, x, h, w, bits);
	  for (int y0 = y; y0 <= y + 2; y0++) {
	    check(y0, x - 1, h, w, bits);
	    check(y0, x + 1, h, w, bits);
	  }
	  int c = unused(bits);
	  gs[y][x] = gs[y + 1][x] = gs[y + 2][x] = c;
	}
	else { puts("NO"); return 0; }
      }

  puts("YES");
  for (int y = 0; y < h; y++) {
    for (int x = 0; x < w; x++)
      putchar((gs[y][x] >= 0) ? 'a' + gs[y][x] : '.');
    putchar('\n');
  }

  return 0;
}