Problem:
 Score: 400 points    Problem Statement  Chokudai made a rectangular cake for contestants in DDCC 2020 Finals.  The cake has H - 1 horizontal notches and W - 1 vertical notches, which divide the cake into H \times W equal sections. K of these sections has a strawberry on top of each of them.  The positions of the strawberries are given to you as H \times W characters s_{i, j}  (1 \leq i \leq H, 1 \leq j \leq W) . If s_{i, j} is # , the section at the i -th row from the top and the j -th column from the left contains a strawberry; if s_{i, j} is . , the section does not contain one. There are exactly K occurrences of # s.  Takahashi wants to cut this cake into K pieces and serve them to the contestants. Each of these pieces must satisfy the following conditions:   Has a rectangular shape.  Contains exactly one strawberry.   One possible way to cut the cake is shown below:   Find one way to cut the cake and satisfy the condition. We can show that this is always possible, regardless of the number and positions of the strawberries.      Constraints   1 \leq H \leq 300  1 \leq W \leq 300  1 \leq K \leq H \times W  s_{i, j} is # or . .  There are exactly K occurrences of # in s .         Input  Input is given from Standard Input in the following format:  H  W  K  s_{1, 1} s_{1, 2} \cdots s_{1, W}  s_{2, 1} s_{2, 2} \cdots s_{2, W}  :  s_{H, 1} s_{H, 2} \cdots s_{H, W}       Output  Assign the numbers 1, 2, 3, \dots, K to the K pieces obtained after the cut, in any order. Then, let a_{i, j} be the number representing the piece containing the section at the i -th row from the top and the j -th column from the left of the cake. Output should be in the following format:  a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}  a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}  :  a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}   If multiple solutions exist, any of them will be accepted.        Sample Input 1 3 3 5
#.#
.#.
#.#      Sample Output 1 1 2 2
1 3 4
5 5 4  One way to cut this cake is shown below:         Sample Input 2 3 7 7
#...#.#
..#...#
.#..#..      Sample Output 2 1 1 2 2 3 4 4
6 6 2 2 3 5 5
6 6 7 7 7 7 7  One way to cut this cake is shown below:         Sample Input 3 13 21 106
.....................
.####.####.####.####.
..#.#..#.#.#....#....
..#.#..#.#.#....#....
..#.#..#.#.#....#....
.####.####.####.####.
.....................
.####.####.####.####.
....#.#..#....#.#..#.
.####.#..#.####.#..#.
.#....#..#.#....#..#.
.####.####.####.####.
.....................      Sample Output 3 12 12 23 34 45 45 60 71 82 93 93 2 13 24 35 35 17 28 39 50 50
12 12 23 34 45 45 60 71 82 93 93 2 13 24 35 35 17 28 39 50 50
12 12 56 89 89 89 60 104 82 31 31 46 13 24 35 35 61 61 39 50 50
12 12 67 67 100 100 60 9 9 42 42 57 13 24 6 72 72 72 72 72 72
12 12 78 5 5 5 20 20 20 53 68 68 90 24 6 83 83 83 83 83 83
16 16 27 38 49 49 64 75 86 97 79 79 90 101 6 94 94 105 10 21 21
16 16 27 38 49 49 64 75 86 97 79 79 90 101 6 94 94 105 10 21 21
32 32 43 54 65 65 80 11 106 95 22 22 33 44 55 55 70 1 96 85 85
32 32 43 54 76 76 91 11 106 84 84 4 99 66 66 66 81 1 96 74 74
14 14 3 98 87 87 102 11 73 73 73 4 99 88 77 77 92 92 63 63 63
25 25 3 98 87 87 7 29 62 62 62 15 99 88 77 77 103 19 30 52 52
36 36 47 58 69 69 18 29 40 51 51 26 37 48 59 59 8 19 30 41 41
36 36 47 58 69 69 18 29 40 51 51 26 37 48 59 59 8 19 30 41 41

Solution (Python):
h, w, k = map(int, input().split())
cake = []
piece = []
flg = False
for _ in range(h):
    s = input()
    if flg and s.count("
        cake.append(piece)
        piece = [s]
        continue
    piece.append(s)
    if s.count("
        flg = True
cake.append(piece)

cnt = 0
for ps in cake:
    r = len(ps)
    oo = [0] * w
    for p in ps:
        st = p.count("
        if st == 0:
            continue
        cnt += 1
        for i, v in enumerate(p):
            oo[i] = cnt
            if v == "
                if st == 1:
                    pass
                else:
                    cnt += 1
                    st -= 1
    for _ in range(r):
        print(*oo)

Solution (Python):
import math
from collections import deque
def main():
    h,w,k = tuple([int(t)for t in input().split()])
    s = [list(input())for _ in range(h)]
    output = [[-1]*w for _ in range(h)]

    counter = 1
    for i,s_ in enumerate(s):
        if '
            temp = 0
            for j,piece in enumerate(s_):
                output[i][j] = counter
                if piece == "
                    counter +=1
                    temp = j+1
                    
            if s_[w-1] != "
                counter -=1
                output[i][temp:w] = [counter]*(w-temp)
                counter +=1

    for i in range(h-1):
        if not "
            output[i+1] = output[i]
    for i in range(1,h)[::-1]:
        if not "
            output[i-1] = output[i]

    for o_ in output:
        for o in o_:
            print(o,end=" ")
        print()

if __name__ == "__main__":
    main()

Solution (Python):
H,W,K = map(int,input().split())
cake = []
ls = []
zeroh = [0]*H
for i in range(H):
    c = input()
    tmp = c.rfind("
    if tmp == -1:
        zeroh[i] = 1
        tmp = W-1
    ls.append(tmp)
    cake.append(list(c))
ans = []
num = 1
split = [0]*W
for i in range(H):
    if zeroh[i]:
        ans.append(split)
    if not zeroh[i]:
        split = []
        for j in range(W):
            split.append(num)
            if cake[i][j] == "
                num += 1
        num += 1
        ans.append(split)

notzeropoint = 0
for i in range(H):
    if ans[i][0] != 0:
        notzeropoint = i
        break

for i in range(notzeropoint):
    for j in range(W):
        ans[i][j] = ans[notzeropoint][j]


for i in range(H):
    print(*ans[i])

Solution (Python):
h,w,k = map(int,input().split())
lst = []
cut1 = []
for i in range(h):
    l = input()
    if '
        cut1.append(i)
    lst.append(l)
res = [[float('inf')]*w for _ in range(h)]

cut2 = []
for c in cut1:
    tmp_cut = []
    for j in range(len(lst[c])):
        if lst[c][j]=='
            tmp_cut.append(j)
    cut2.append(tmp_cut)

cnt = 1
for e,i in enumerate(cut1):
    for j in cut2[e]:
        res[i][j] = cnt
        cnt += 1

for r in res:
    mn = min(r)
    mx = max(r)
    if (mn==mx) and (mn==float('inf')):
        pass
    else:
        mx = max(set(r) - {float('inf')})
        if mn==mx:
            for i in range(w):
                if r[i] == float('inf'):
                    r[i] = mn
        else:
            for i in range(w):
                if r[i] == float('inf'):
                    r[i] = mn
                else:
                    mn = min(mx, r[i])

for i in range(w):
    tmp = []
    for j in range(h):
        if res[j][i] != float('inf'):
            tmp.append(res[j][i])
    num = min(tmp)
    for j in range(h):
        if res[j][i] == float('inf'):
            res[j][i] = num
        else:
            num = res[j][i]

for r in res:
    print(*r)

Solution (Python):
h,w,k,*S=open(0).read().split()
h,w=int(h),int(w)
c,n=0,0
for s in S:
  l,r=-1,s.find('
  n+=1
  if r==-1:continue
  t=[]
  while r!=-1:
    c+=1
    t+=[c]*(r-l)
    l,r=r,s.find('
  t+=[c]*(w-l-1)
  for i in range(n):
    print(*t)
  n=0
for i in range(n):
  print(*t)

Solution (Python):
H,W,K=map(int, input().split())
S=[input()for _ in range(H)]
A=[[0]*W for _ in range(H)]
c=0
for i in range(H):
    d=0
    for j in range(W):
        if S[i][j]=="
            c+=1
            d=c
        A[i][j]=d
    p=0
    for j in range(W-1,-1,-1):
        if A[i][j]==0:
            A[i][j]=p
        p=A[i][j]
    if S[i].find("
        A[i][:]=A[i-1]
for i in range(H-2,-1,-1):
    if all(a==0 for a in A[i]):
        A[i][:]=A[i+1]
for i in range(H):
    print(*A[i])

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,k=LI()
  field=[list(S()) for _ in range(h)]
  ans=[[0]*w for _ in range(h)]

  l=[]
  f=False
  y1=0
  x1=0
  for i in range(h):
    for j in range(w):
      if field[i][j]=='
        if f:
          l.append([y1,x1,i-1,w-1])
          y1=i
          x1=0
        f=True
        break
  l.append([y1,x1,h-1,w-1])
  

  l2=[]
  while len(l)>0:
    y1,x1,y2,x2=l.pop()
    st=0
    f=False
    for j in range(x1,x2+1):
      for i in range(y1,y2+1):
        if field[i][j]=='
          if f:
            l2.append([y1,st,y2,j-1])
            st=j
          f=True
          break
    l2.append([y1,st,y2,x2])

  cnt=1
  while len(l2)>0:
    y1,x1,y2,x2=l2.pop()
    for i in range(y1,y2+1):
      for j in range(x1,x2+1):
        ans[i][j]=cnt
    cnt+=1

  for x in ans:
    print(' '.join([str(y) for y in x]))

main()

Solution (Python):
n,m,k=map(int,input().split())
board=[list(input()) for _ in range(n)]
cnt=[0]*n
for i in range(n):
  tmp=0
  for j in range(m):
    if board[i][j]=='
      tmp+=1
  cnt[i]=tmp
ans=[[0]*m for _ in range(n)]
num=1
for i in range(n):
  if cnt[i]==0:
    continue
  tmp=0
  for j in range(m):
    ans[i][j]=num
    if board[i][j]=='
      tmp+=1
      if tmp>=2:
        ans[i][j]+=1
        num+=1
  num+=1
for i in range(1,n):
  if cnt[i]==0:
    for j in range(m):
      ans[i][j]=ans[i-1][j]
for i in range(n-2,-1,-1):
  if cnt[i]==0:
    for j in range(m):
      ans[i][j]=ans[i+1][j]
for i in range(n):
  print(*ans[i])

Solution (Python):
h, w, k = map(int, input().split())
S = [list(input()) for i in range(h)]

ans = [[0 for i in range(w)] for j in range(h)]
cnt = 1
no_sb = ['.' for i in range(w)]
no_sb_row = []

for i in range(h):
    flag = True
    if S[i] == no_sb:
        no_sb_row.append(i)
    else:
        for j in range(w):
            if S[i][j] == '
                flag = False
            elif S[i][j] == '
                cnt += 1
            ans[i][j] = cnt
        cnt += 1

for row in no_sb_row:
    for i in range(row+1, h):
        if i not in no_sb_row:
            ans[row] = ans[i]
            break
    else:
        for j in range(row-1, -1, -1):
            if j not in no_sb_row:
                ans[row] = ans[j]
                break

for a in ans:
    print(*a)

Solution (Python):
h,w,k = map(int,input().split())
s = [input() for _ in range(h)]
row = []
col = []

flagr = flagc = flags = False
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            if flagc:
                col.append(j)
            else:
                flagc = True
            flags = True
    if flags:
        col.append(w)
        if flagr:
            row.append(i)
        else:
            flagr = True
        flagc = flags = False
row.append(h)

ans = [["" for _ in range(w)] for _ in range(h)]
cnt = 1
idx = 0
sr = sc = 0
for er in row:
    while sc != w:
        ec = col[idx]
        for i in range(sr,er):
            for j in range(sc,ec):
                ans[i][j] = str(cnt)
        cnt += 1
        idx += 1
        sc = ec
    sc = 0
    sr = er

for i in range(h): print(" ".join(ans[i]))

Solution (Python):



def main():
    H,W,K = map(int,input().split())
    S = [input() for _ in range(H)]
    answer = [[0]*W for _ in range(H)]
    count = 0

    strobery_count = [0]*H
    for i in range(H):
        strobery_count[i] = S[i].count("
    flag = False
    for i in range(H):
        tmp = 1
        if strobery_count[i] == 0:
            if i >= 1:
                answer[i] = answer[i-1]
            else:
                flag = True
            continue
        
        count += 1
        for j in range(W):
            answer[i][j] = count
            if S[i][j] == "
                count += 1
                tmp += 1
    
    if flag:
        a = 0
        for i in range(H):
            if strobery_count[i] == 0:
                a = i
            else:
                a = i
                break
        
        for h in range(a):
            answer[h] = answer[a]

    for i in range(H):
        print(*answer[i])          

if __name__ == '__main__':
    main()

Solution (Python):
num = 0

def solve(cl, cr):
    P = []
    for i in range(cl, cr+1):
        for j in range(1, W+1):
            if S[i][j] == "
                P.append(j)
    P.sort()

    for i in range(len(P)):
        v1, v2 = 1, W
        if i >= 1:
            v1 = P[i-1] + 1
        if i < len(P) - 1:
            v2 = P[i]

        global num
        num += 1
        for j in range(cl, cr+1):
            for k in range(v1, v2+1):
                A[j][k] = num


H, W, K = map(int, input().split())
A = [[0 for _ in range(303)] for _ in range(303)]
S = [[" " for _ in range(303)] for _ in range(303)]
cnt = [0] * 303
for i in range(1, H+1):
    row = input()
    for j, c in enumerate(row, 1):
        if c == "
            cnt[i] += 1
        S[i][j] = c

vec = []
for i in range(1, H+1):
    if cnt[i] >= 1:
        vec.append(i)
for i in range(len(vec)):
    v1, v2 = 1, H
    if i >= 1:
        v1 = vec[i-1] + 1
    if i < len(vec) - 1:
        v2 = vec[i]

    solve(v1, v2)

for i in range(1, H+1):
    tmp = []
    for j in range(1, W+1):
        tmp.append(str(A[i][j]))
    print(" ".join(tmp))

Solution (Python):
import sys


def main():
    H,W,K = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    ans = [[0 for _ in range(W)] for _ in range(H)]
    up,down = 0,1
    count = 1
    for i in range(H):
        if "
            if down != H:
                down += 1
            else:
                for x in range(up,down):
                    for y in range(W):
                        ans[x][y] = ans[up-1][y]
        else:
            now = 0
            for j in range(W):
                if s[i][j] == "
                    for x in range(up,down):
                        for y in range(now,j+1):
                            ans[x][y] = count
                    now = j+1
                    count += 1
            if s[i][-1] == ".":
                for x in range(up,down):
                    for y in range(now,W):
                        ans[x][y] = count-1
            up = down
            down += 1
    
    for i in range(H):
        print(*ans[i])

if __name__ == "__main__":
    main()

Solution (Python):
h,w,k=map(int,input().split())
ans=[[0]*w for i in range(h)]

num=0
for i in range(h):
 s=input()

 if '
  if i==0 or ans[i-1]==[0]*w:
   continue
  else:
   ans[i]=ans[i-1]

 else:
  for j in range(w):
   if s[j]=='
    num+=1
    ans[i][j]=num
   else:
    if j>=1 and ans[i][j-1]!=0:
     ans[i][j]=ans[i][j-1]

if ans[0]==[0]*w:
 i=0
 while ans[i]==[0]*w:
  i+=1
 for j in range(i):
  ans[j]=ans[i]

for i in range(h):
 if ans[i][0]==0:
  j=0
  while ans[i][j]==0:
   j+=1
  for k in range(j):
   ans[i][k]=ans[i][j]

for i in range(h):
 print(*ans[i])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,k = inpl()
s = [input() for i in range(h)]
res = [[0]*w for i in range(h)]
cnt = 0
bb = set()
for y in range(h):
    if s[y].count('
        bb.add(y); continue
    fg = False
    for x in range(w):
        if s[y][x] == '.':
            if fg:
                res[y][x] = cnt
        else:
            fg = True
            cnt += 1
            res[y][x] = cnt
for y in range(h):
    if y in bb: continue
    for x in range(w)[::-1]:
        if res[y][x]: continue
        res[y][x] = res[y][x+1]

for x in range(w):
    for y in range(h-1):
        if not y+1 in bb: continue
        res[y+1][x] = res[y][x]

for x in range(w):
    for y in range(h-1)[::-1]:
        if not y in bb: continue
        res[y][x] = res[y+1][x]

for i in res:
    print(*i)

Solution (Python):
H,W,K = list(map(int,input().split()))
s = [list(input()) for i in range(H)]
ans = [[0 for i in range(W)] for j in range(H)]
cut = []
for h in range(H):
    if '
        cut.append(h)
count = 1
for j in range(len(cut)):
    cut2 = [0 for i in range(W)]
    for w in range(W):
        if s[cut[j]][w] == '
            cut2[w] = count
            count += 1
    for w in range(W-2,-1,-1):
        if cut2[w] == 0:
            cut2[w] = cut2[w+1]
    for w in range(1,W):
        if cut2[w] == 0:
            cut2[w] = cut2[w-1]    
    if j == 0:
        for k in range(cut[0]+1):
            print(*cut2)
    else:
        for k in range(cut[j]-cut[j-1]):
            print(*cut2)
if cut[-1] != H-1:
    for k in range(H-cut[-1]-1):
        print(*cut2)

Solution (Python):
h, w, k = map(int, input().split())
L = [[0]*w for _ in range(h)]
now = 1
for i in range(h):
  s = input()
  for j in range(w):
    if s[j] == ".":
      L[i][j] = 0
    else:
      L[i][j] = now
      now += 1
for i in range(h):
  for j in range(w-1):
    if L[i][j+1] == 0:
      L[i][j+1] = L[i][j]
for i in range(h):
  for j in range(w-1):
    if L[i][w-2-j] == 0:
      L[i][w-2-j] = L[i][w-1-j]
for i in range(h-1):
  for j in range(w):
    if L[i+1][j] == 0:
      L[i+1][j] = L[i][j]
for i in range(h-1):
  for j in range(w):
    if L[h-2-i][j] == 0:
      L[h-2-i][j] = L[h-1-i][j]
for i in L:
  print(*i)

Solution (Python):
import bisect
import math
import sys
from collections import Counter, defaultdict, deque
from copy import copy, deepcopy
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from queue import Queue

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

def SI():
    return int(readline())
def MI():
    return map(int, readline().split())
def MLI():
    return map(int, open(0).read().split())

inf = float("inf")


def main():
    H, W, K = MI()
    cake = [[s for s in input()] for h in range(H)]

    cursor = 0
    skip_rows = False
    for h in range(H):
        if '
            cursor += 1
            first_flag = True
            for w in range(W):
                if cake[h][w] == '.':
                    cake[h][w] = cursor
                else:
                    if first_flag:
                        cake[h][w] = cursor
                        first_flag = False
                    else:
                        cursor += 1
                        cake[h][w] = cursor
            last_row = h
        else:
            skip_rows = True

    if skip_rows:
        if last_row < H - 1:
            for h in range(last_row + 1, H):
                cake[h] = cake[last_row]
        for h in range(H - 2, -1, -1):
            if '.' in cake[h]:
                cake[h] = cake[h + 1]

    for row in cake:
        row = [str(e) for e in row]
        print(' '.join(row))
        
    
if __name__ == "__main__":
    main()

Solution (Python):
H, W, K = map(int, input().split())

cake = [list(input()) for _ in range(H)]
ans = [[0] * W for _ in range(H)]

id = 1
sign = 0
nothing = 0

for i in range(H):
    if cake[i].count('
        nothing += 1
        if i == H-1:
            for j in range(W):
                for d in range(nothing):
                    ans[i-d][j] = ans[i-nothing][j]
        continue
    for j in range(W):
        if cake[i][j] == '
            ans[i][sign:j+1] = [id] * (j+1-sign)
            sign = j+1
            id += 1
        elif j == W-1:
            ans[i][sign:j+1] = [id-1] * (j+1-sign)
    if nothing != 0:
        for j in range(W):
            for d in range(1,nothing+1):
                ans[i-d][j] = ans[i][j]
    sign = 0
    nothing = 0

for i in range(H):
    for j in range(W):
        print('{} '.format(ans[i][j]), end='')
    print()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = tuple(tuple(input().strip("\n")) for _ in range(H))
    A = [[-1 for _ in range(W)] for i in range(H)]
    startR = 0
    line = 0
    endR = 0
    cakeN = 1
    for i in range(H):
        if "
            line = i
            endR = i + 1
            break
    while endR < H:
        if "
            startC = 0
            for j in range(W):
                if S[line][j] == "
                    endC = j + 1
                    break
            while endC < W:
                if S[line][endC] == "
                    for si in range(startR, endR):
                        for sj in range(startC, endC): A[si][sj] = cakeN
                    startC = endC
                    cakeN += 1
                endC += 1
            for si in range(startR, endR):
                for sj in range(startC, endC):
                    A[si][sj] = cakeN
            cakeN += 1
            startR = line = endR

        endR += 1

    startC = 0
    for j in range(W):
        if S[line][j] == "
            endC = j + 1
            break
    while endC < W:
        if S[line][endC] == "
            for si in range(startR, endR):
                for sj in range(startC, endC):
                    A[si][sj] = cakeN
            startC = endC
            cakeN += 1
        endC += 1
    for si in range(startR, endR):
        for sj in range(startC, endC):
            A[si][sj] = cakeN

    for i, a in enumerate(A): print(" ".join(map(str, a)))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

def main():
    h, w, k = map(int, input().split())
    board = [input().strip() for i in range(h)]

    group = [[0 for i in range(w)] for j in range(h)]

    state = 0   
    num = 1
    stock = 1
    pre = -1
    for i in range(h):
        if "
            stock += 1
            continue
        for j in range(w):
            if board[i][j] == "
                if state == 0:
                    state = 1
                else:
                    num += 1
                group[i][j] = num
            else:
                group[i][j] = num
        for k in range(stock):
            for j in range(w):
                print(group[i][j], end=" ")
            print()
        num += 1
        state = 0
        stock = 1
        pre = i
    
    for k in range(h-pre-1):
        for j in range(w):
            print(group[pre][j], end=" ")
        print()


if __name__ == "__main__":
    main()

Solution (Python):
H,W,K = list(map(int, input().split()))
S = []
for i in range(H):
  S.append(input())
  
A = [[0 for i in range(W)] for j in range(H)]

pt = 1
for i in range(H):
  if S[i][:] == "." * W:
    if i > 0:
      A[i][:] = A[i-1][:]
      continue
      
  firstFlg = True
  for j in range(W):
    if firstFlg and S[i][j] == "
      for k in range(0,j+1):
        A[i][k] = pt
      pt += 1
      firstFlg = False
    elif S[i][j] == "
      A[i][j] = pt
      pt += 1
    else:
      A[i][j] = pt-1

for i in range(H-1,-1,-1):
  if A[i] == [0 for j in range(W)]:
    A[i][:] = A[i+1][:]

for i in range(H):
  print(" ".join(list(map(str,A[i]))))

Solution (Python):
from itertools import accumulate

H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

ans = []
acc = 0
l = 0
for i in s:
    cnt = i.count("
    if cnt == 0:
        if not ans:
            l += 1
        else:
            ans.append(ans[-1])
    else:
        k = [0] * W
        for j in range(W):
            if i[j] == "
                k[j] = 1
        k = list(accumulate(k))
        for j in range(W):
            if k[j] == 0:
                k[j] = 1
            k[j] += acc
        ans.append(k)
    if ans and l >= 1 :
        for _ in range(l):
            ans.append(ans[-1])
        l = 0
    acc += cnt
        
for i in ans:
    print(" ".join(map(str, i)))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W,K = map(int, readline().split())
grid = np.frombuffer(read(), 'S1').reshape(H,-1)[:,:W]

X,Y = np.where(grid == b'

A = np.zeros((H,W), np.int32)
A[X,Y] = np.arange(1,K+1)

np.maximum.accumulate(A, axis = 1, out = A)

for w in range(W-2, -1, -1):
	A[:,w] += A[:,w+1] * (A[:,w] == 0)

for h in range(1,H):
	if A[h,-1] == 0:
		A[h] += A[h-1]
for h in range(H-1,-1,-1):
	if A[h,-1] == 0:
		A[h] += A[h+1]

print('\n'.join(' '.join(row) for row in A.astype(str)))

Solution (Python):
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

ans = [[0 for _ in range(w)] for _ in range(h)]

num = 0
f = False
for i, j in enumerate(s):
    tmp = j.find("
    if tmp == -1:
        if f:
            ans[i] = ans[i - 1]
        continue
    else:
        num += 1
        for k in range(tmp + 1):
            ans[i][k] = num
        for l in range(tmp + 1, w):
            if j[l] == ".":
                ans[i][l] = num
            else:
                num += 1
            ans[i][l] = num
        if f == False:
            f = True
            for x in range(i):
                ans[x] = ans[i]

for i in ans:
    print(*i)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



H,W,K = II()
s = [str(input()) for _ in range(H)]
ans = [[0]*W for _ in range(H)]

count = 0
no_row = []
for i in range(H):
    p = []
    for j in range(W):
        if s[i][j]=='
            p.append(j)
    if len(p):
        count += 1
        for j in range(W):
            if s[i][j] == '
                count += 1
            ans[i][j] = count
    else:
        no_row.append(i)

for i in no_row:
    for j in range(W):
        for k in range(i+1,H):
            if ans[k][j]:
                ans[i][j] = ans[k][j]
                break
        for k in range(i)[::-1]:
            if ans[k][j]:
                ans[i][j] = ans[k][j]
                break

for a in ans:
    print(*a)

Solution (Python):
H,W,K=map(int,input().split(' '))
S=[input() for i in range(H)]
ans = [[0]*W for i in range(H)]
cnt = 1
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            ans[i][j] = cnt
            cnt += 1
def group(h,w,k):
    ans[h][w] = k
    if 0<=w+1<W and ans[h][w+1] == 0:
            group(h,w+1,k)
    if 0<=w-1<W and ans[h][w-1] == 0:
            group(h,w-1,k)
def group_h(h,w,k):
    ans[h][w] = k
    if 0<=h+1<H and ans[h+1][w] ==0:
        group_h(h+1,w,k)
    if 0<=h-1<H and ans[h-1][w] == 0:
        group_h(h-1,w,k)

for h,i in enumerate(ans):
    for w,j in enumerate(i):
        if j != 0:
            group(h,w,j)
for h,i in enumerate(ans):
    for w,j in enumerate(i):
        if j != 0:
            group_h(h,w,j)
for i in ans:
    for j in i:
        print(j,"",end="")
    print("")

Solution (Python):
import bisect

H,W,K=map(int,input().split())
s=[""]*H
ans=[[0]*W for _ in range(H)]
St=[0]*H
St2=[]


for i in range(H):
    s[i]=input()
    if "
        St[i]=1
        St2.append(i)
        
    
    
a=1

for i in range(H):
    if St[i]==1:
        flag=0
        for j in range(W):
            if s[i][j]=="
                if flag==0:
                    flag=1
                else:
                    a+=1
            ans[i][j]=a
        a+=1
        

for i in range(H):
    k=bisect.bisect_left(St2,i)
    
    if k!=0:
        k-=1
    if St[i]==0:
        ans[i]=ans[St2[k]]
        
for i in range(H):
    print(" ".join(map(str, ans[i])))

Solution (Python):
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + (1 if a[r][c] == '
                
        return ret

    def get(self, r1, r2, c1, c2):
        
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys

    sys.setrecursionlimit(10 ** 7)

    def fill_cake(r1, r2, c1, c2) -> None:
        """ケーキに番号を振る"""
        nonlocal piece_number
        for r in range(r1, r2):
            for c in range(c1, c2):
                ret[r][c] = piece_number
        piece_number += 1

    def cut_cake(r1, r2, c1, c2, rest) -> None:
        """[r1,r2),[c1,c2)の範囲にrest個ケーキがある状態からのカット"""
        if rest == 1:
            fill_cake(r1=r1, r2=r2, c1=c1, c2=c2)
            return  

        for r in range(r1 + 1, r2):
            piece_count = acc2D.get(r1=r1, r2=r, c1=c1, c2=c2)
            if 0 < piece_count < rest:  
                cut_cake(r1=r1, r2=r, c1=c1, c2=c2, rest=piece_count)
                cut_cake(r1=r, r2=r2, c1=c1, c2=c2, rest=rest - piece_count)
                return  

        for c in range(c1 + 1, c2):
            piece_count = acc2D.get(r1=r1, r2=r2, c1=c1, c2=c)
            if 0 < piece_count < rest:  
                cut_cake(r1=r1, r2=r2, c1=c1, c2=c, rest=piece_count)
                cut_cake(r1=r1, r2=r2, c1=c, c2=c2, rest=rest - piece_count)
                return  

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    acc2D = Acc2D(s)
    
    

    ret = [[-1] * w for _ in range(h)]
    piece_number = 1

    cut_cake(r1=0, r2=h, c1=0, c2=w, rest=k)

    for row in ret:
        print(*row)


if __name__ == '__main__':
    main()

Solution (Python):
H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = [[0] * W for _ in range(H)]

def calc(h, w, k):
    
    up = h
    for i in range(1, h + 1):
        if S[h - i][w] == '.' and ans[h - i][w] == 0:
            if h == i:
                up = 0
            continue
        else:
            up = h - (i - 1)
            break

    down = h
    for i in range(1, H - h):
        if S[h + i][w] == '.' and ans[h + i][w] == 0:
            if i == H - h - 1:
                down = H - 1
            continue
        else:
            down = h + (i - 1)
            break
    
    
    for i in range(up, down + 1):
        ans[i][w] = k
    
    flag = True
    for i in range(1, w + 1):
        for j in range(up, down + 1):
            if ans[j][w - i] == 0 and S[j][w - i] == '.':
                continue
            else:
                flag = False
                break
        if not flag:
            break
        for j in range(up, down + 1):
            ans[j][w - i] = k
    flag = True
    for i in range(1, W - w):
        for j in range(up, down + 1):
            if ans[j][w + i] == 0 and S[j][w + i] == '.':
                continue
            else:
                flag = False
                break
        if not flag:
            break
        for j in range(up, down + 1):
            ans[j][w + i] = k
        


k = 1
for w in range(W):
    for h in range(H):
        if S[h][w] == '
            
            calc(h, w, k)
            k += 1

for tmp in ans:
    print (*tmp, sep = ' ')