Submission #21282822


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }




void main() {
  try {
    for (; ; ) {
      const H = readInt();
      const W = readInt();
      auto S = new string[H];
      foreach (x; 0 .. H) {
        S[x] = readToken();
      }
      
      auto A = new int[][](H, W);
      foreach (x; 0 .. H) foreach (y; 0 .. W) {
        A[x][y] = (S[x][y] == '.') ? 0 : 1;
      }
      
      auto row = new int[][](H, 2);
      auto col = new int[][](W, 2);
      foreach (x; 0 .. H) foreach (y; 0 .. W) {
        ++row[x][A[x][y]];
        ++col[y][A[x][y]];
      }
      
      DList!int que;
      auto delX = new bool[H];
      auto delY = new bool[W];
      foreach (x; 0 .. H) {
        if (row[x][0] == 0 || row[x][1] == 0) {
          delX[x] = true;
          que ~= x;
        }
      }
      foreach (y; 0 .. W) {
        if (col[y][0] == 0 || col[y][1] == 0) {
          delY[y] = true;
          que ~= H + y;
        }
      }
      
      int ans;
      for (; !que.empty; ) {
        const z = que.front;
        que.removeFront;
        ++ans;
        if (z < H) {
          const x = z;
          foreach (y; 0 .. W) {
            if (!delY[y]) {
              if (--col[y][A[x][y]] == 0) {
                delY[y] = true;
                que ~= H + y;
              }
            }
          }
        } else {
          const y = z - H;
          foreach (x; 0 .. H) {
            if (!delX[x]) {
              if (--row[x][A[x][y]] == 0) {
                delX[x] = true;
                que ~= x;
              }
            }
          }
        }
      }
      
      chmin(ans, H + W - 1);
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task H - Grid Eraser
User hos_lyric
Language D (LDC 1.20.1)
Score 100
Code Size 2893 Byte
Status AC
Exec Time 236 ms
Memory 23828 KB

Judge Result

Set Name sample All sample
Score / Max Score 0 / 0 100 / 100 0 / 0
Status
AC × 2
AC × 47
AC × 2
Set Name Test Cases
sample sample_00, sample_01
All almost_black_00, almost_black_01, almost_white_00, almost_white_01, col_same_00, col_same_01, line_00, line_01, line_02, line_03, line_04, max_00, max_01, max_02, max_03, max_04, one_b, one_w, rnd_00, rnd_01, rnd_02, rnd_03, rnd_04, rnd_05, rnd_06, rnd_07, rnd_08, rnd_09, rnd_10, rnd_11, rnd_12, rnd_13, rnd_14, row_same_00, row_same_01, sample_00, sample_01, super2_00, super2_01, super2_02, super2_03, super2_04, super_00, super_01, zero_00, zero_01, zero_02
sample sample_00, sample_01
Case Name Status Exec Time Memory
almost_black_00 AC 16 ms 5680 KB
almost_black_01 AC 52 ms 17316 KB
almost_white_00 AC 34 ms 16540 KB
almost_white_01 AC 56 ms 21760 KB
col_same_00 AC 226 ms 23656 KB
col_same_01 AC 236 ms 23792 KB
line_00 AC 5 ms 3376 KB
line_01 AC 4 ms 3352 KB
line_02 AC 7 ms 3300 KB
line_03 AC 4 ms 3340 KB
line_04 AC 4 ms 3128 KB
max_00 AC 146 ms 23708 KB
max_01 AC 137 ms 23776 KB
max_02 AC 142 ms 23536 KB
max_03 AC 136 ms 23692 KB
max_04 AC 146 ms 23560 KB
one_b AC 4 ms 3284 KB
one_w AC 6 ms 3364 KB
rnd_00 AC 21 ms 6912 KB
rnd_01 AC 44 ms 17296 KB
rnd_02 AC 29 ms 14228 KB
rnd_03 AC 14 ms 6164 KB
rnd_04 AC 78 ms 21648 KB
rnd_05 AC 3 ms 3224 KB
rnd_06 AC 4 ms 3600 KB
rnd_07 AC 7 ms 3592 KB
rnd_08 AC 49 ms 17328 KB
rnd_09 AC 42 ms 18096 KB
rnd_10 AC 48 ms 19840 KB
rnd_11 AC 38 ms 14660 KB
rnd_12 AC 22 ms 7304 KB
rnd_13 AC 51 ms 15464 KB
rnd_14 AC 62 ms 23376 KB
row_same_00 AC 69 ms 23576 KB
row_same_01 AC 66 ms 23552 KB
sample_00 AC 3 ms 3360 KB
sample_01 AC 4 ms 3288 KB
super2_00 AC 111 ms 23708 KB
super2_01 AC 106 ms 23720 KB
super2_02 AC 146 ms 23680 KB
super2_03 AC 158 ms 23640 KB
super2_04 AC 109 ms 23596 KB
super_00 AC 146 ms 23828 KB
super_01 AC 148 ms 23744 KB
zero_00 AC 12 ms 4904 KB
zero_01 AC 11 ms 4548 KB
zero_02 AC 17 ms 5984 KB