目次

• 問題
  • 入力
  • 出力
  • 入出力例
• 解説
• 計算量
• 解答

# 問題

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_c

# 入力

H W K
s_1,1 s_1,2 ... s_1,W
...
s_H,1 s_H,2 ... s_H,W

• H, W - マップの高さ・横幅
• K - #の数
• s_i,j - 1マス. . または #

# 出力

マップをすべての長方形に#が1つずつ含まれるように長方形に分割する問題です.
分割した長方形に1からKまで連番をつけて各長方形に含まれるマスの位置にその番号を出力してください.

a_1,1 a_1,2 ... a_1,W
...
a_H,1 a_H,2 ... a_H,W

# 入出力例

3 3 5
#.#
.#.
#.#

1 2 2
1 3 4
5 5 4

# 解説

マスを２つずつにどんどん分割していく深さ優先探索を使用します.
すべての長方形がたった１つだけ#を含むという制約があります.
なので分割されて小さくなった長方形にたった１つだけ#が含まれるくらい小さくなったら探索を終了します.
その長方形に含まれるすべてのマスを色で塗ります.

問題はどこを境として２つの長方形に切り分けるかです.
すべてのマスを先頭から訪問していき２つ目の#に出会った段階で、その手前を境として２つの長方形に切り分けます.
そうすると２つに分かれたどちらの長方形にも#が含まれることになります.

出会った２つの#が異なる高さにある時には水平に（横に）切り分けます.
同じ高さの場合には垂直に（縦に）切り分けます.

これは計算量$O((H+W) \times (HW))$程度で、$H, W$の最大値は300なので$10^8$で間に合います.
（計算量の見積もりは以下を参照してください.）

# 計算量

$O((H + W) \times (HW))$

深さ優先探索で1つの深さにつき全マスを探索する必要があります.
例えば深さ0では当然マップ全体なので全マスです.
次に深さ1では長方形1, 2の２つに分割されているので、長方形1全体と長方形2全体の探索が必要です.
長方形1と2は合わせると結局全マスなので深さ1でも全マスの探索です.
次に深さ2では長方形は4つに分割されていますが、繋げると結局全マスになります.
このようにどの深さの段階でも全マスの探索が必要です.
まとめると、深さを$d$とすると全体の計算量は$O(d \times (HW))$となります.

次に深さ$d$を求めます.
マップの切る箇所はマスとマスの間なので縦に$H-1$個、横に$W-1$個あります.
約$H$個、 $W$個です.
これ以上マップは分割出来ません.
1回切るごとに深さは+1されていくので、深さの最大は約$d = H + W$です.

先程の式に代入すると計算量が得られます.

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_H 300
#define HH (300*300)
#define MAX_K (300*300)

Int H, W, K;
vector<bool> B(HH, false);
vector<Int> M(HH, 0);

Int at(Int x, Int y) {
  return y*W+x;
}

void input() {
  char _c;
  cin >> H >> W >> K;
  loop(h,0,H) {
    loop(w,0,W) {
      cin >> _c;
      if (_c == '#') B.at(at(w, h)) = true;
    }
  }
}

Int color = 1;

struct Point {
  Int x, y;

  Point(): x(0), y(0) {}
  Point(Int x, Int y): x(x), y(y) {}
  bool operator < (const Point &v) const {
    return y != v.y ? y < v.y : x < v.x;
  }

  bool operator == (const Point &v) const {
    return x == v.x && y == v.x;
  }
};

void dfs(Point upleft, Point downright) {
  if (M.at(at(upleft.x, upleft.y))) return; // 探索済み
  vector<Point> ks;
  loop(h,upleft.y,downright.y+1) {
    loop(w,upleft.x,downright.x+1) {
      if (B.at(at(w, h))) {
        ks.push_back(Point(w, h));
      }
      if (ks.size() == 2) goto l1; // 2重ループ脱出
    }
  }

l1:
  // 2個見つかった時だけ分割
  if (ks.size() == 2) {
    sort(span_all(ks));
    bool horizontal = ks.at(0).y < ks.at(1).y;
    if (horizontal) {
      // 長方形を２つに切るための座標計算
      ks.at(1).x = upleft.x;
      dfs(ks.at(1), downright);
      ks.at(1).y--;
      ks.at(1).x = downright.x;
      dfs(upleft, ks.at(1));
    } else {
      ks.at(1).y = upleft.y;
      dfs(ks.at(1), downright);
      ks.at(1).x--;
      ks.at(1).y = downright.y;
      dfs(upleft, ks.at(1));
    }
    return;
  }

  // 1個しか見つからない場合は長方形確定. 色を塗る.
  loop(h,upleft.y,downright.y+1) {
    loop(w,upleft.x,downright.x+1) {
      M.at(at(w, h)) = color;
    }
  }
  color++;
}

void solve() {
  dfs(Point(0, 0), Point(W-1, H-1));
  loop(h,0,H) {
    loop(w,0,W) {
      cout << M.at(at(w, h)) << " ";
    }
    cout << endl;
  }
}

int main(void) {
  input();
  solve();
  return 0;
}