Problem:


休憩スペース (Refreshment Area)

問題

世界的なプログラミングコンテストが日本で開催されることになり，現在会場の設営が行われている．この会場は南北方向に N マス，東西方向に M マスのマス目状に区切られており，いくつかのマスには競技用の機材が置かれている．

このコンテストでは，選手が競技中に休憩するために，軽食や飲み物などを置いた休憩スペースを 1 箇所会場内に設けることになった．休憩スペースは南北方向または東西方向に連続した D マスでなければならない．ただし，機材の置かれたマス目に休憩スペースを設けることはできない．

会場内に休憩スペースを設ける方法は何通りあるかを求めるプログラムを作成せよ．

入力

入力は 1 + N 行からなる．

1 行目には 3 個の整数 N, M, D (1 ≦ N ≦ 100, 1 ≦ M ≦ 100, 2 ≦ D ≦ 100) が空白を区切りとして書かれており，会場が南北方向に N マス，東西方向に M マスのマス目状に区切られており，休憩スペースが南北方向または東西方向に連続した D マスからなることを表す．

続く N 行にはそれぞれ M 文字からなる文字列が書かれており，会場の情報を表す．
N 行のうちの i 行目の j 文字目 (1 ≦ i ≦ N, 1 ≦ j ≦ M) は，会場のマス目の北から i 行目，西から j 列目のマスの状態を表す '#' または '.' のいずれかの文字である．'#' はそのマスに機材が置かれていることを，'.' はそのマスに機材が置かれていないことを表す．

出力

会場内に休憩スペースを設ける方法は何通りあるかを 1 行で出力せよ．

入出力例

入力例 1

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

出力例 1

12

入力例 2

4 7 5
.#.....
.....##
.......
#......

出力例 2

7

入出力例 1 では，下の図に示すように，休憩スペースを設ける方法は全部で 12 通りある．

情報オリンピック日本委員会作 『第 16 回日本情報オリンピック JOI 2016/2017 予選競技課題』



Sample input:
3 5 2
...#.
#...#
....#


Sample output:
12

Submission status: Wrong Answer

Solution code:
def count_dots(spaces):
    global ans
    for space in spaces:
        tmp = [s for s in space.split('#') if len(s) >= D]
        for t in tmp:
            if len(t) == D:
                ans += 1
                continue
            if len(t) % D:
                a, b = divmod(len(t), D)
                ans += a + b
            else:
                a, b = divmod(len(t)-1, D)
                ans += a + b + 1

N, M, D = map(int, input().split())
ans = 0
spaces = [input() for _ in range(N)]
count_dots(spaces)
spaces = [''.join(line) for line in list(zip(*spaces))]
count_dots(spaces)
print(ans)

Submission status: Accepted

Solution code:
n, m, d = map(int, input().split())
mp = [input() for _ in range(n)]
ans = 0
for line in mp:
  cnt = 0
  for c in line:
    if c == ".":
      cnt += 1
    else:
      if cnt >= d:
        ans += cnt - d + 1
      cnt = 0
  if cnt >= d:
    ans += cnt - d + 1

for x in range(m):
  cnt = 0
  for y in range(n):
    if mp[y][x] == ".":
      cnt += 1
    else:
      if cnt >= d:
        ans += cnt - d + 1
      cnt = 0
  if cnt >= d:
    ans += cnt - d + 1

print(ans)

Submission status: Accepted

Solution code:
N,M,D = map(int, input().split())
field = [list(input()) for _ in range(N)]
sum = 0

for y in range(N):
	count = 0
	for x in range(M):
		if field[y][x] == '.':
			count += 1
			continue
		elif count == 0:
			continue
		elif count >= D:
			sum += count-D+1
			count = 0
			continue
		count = 0
	else:
		if count >= D:
			sum += count-D+1
			count = 0

field = list(zip(*field[::-1]))

for y in range(M):
	count = 0
	for x in range(N):
		if field[y][x] == '.':
			count += 1
			continue
		elif count == 0:
			continue
		elif count >= D:
			sum += count-D+1
			count = 0
			continue
		count = 0
	else:
		if count >= D:
			sum += count-D+1
			count = 0

print(sum)

Submission status: Accepted

Solution code:
# coding: utf-8

N, M, D = list(map(int, input().split(' ')))
field = [list(input()) for i in range(N)]

pattern_num = 0
cont = 0
for i in range(N):
    for j in range(M):
        if field[i][j] == '.':
            cont += 1
            if cont >= D: pattern_num += 1
        else:
            cont = 0
    cont = 0

cont = 0
for j in range(M):
    for i in range(N):
        if field[i][j] == '.':
            cont += 1
            if cont >= D: pattern_num += 1
        else:
            cont = 0
    cont = 0

print(pattern_num)

Submission status: Accepted

Solution code:
n, m, d = map(int, raw_input().split())
fld = [raw_input() for i in range(n)]

ans = 0
for i in range(n):
  for j in range(m):
    if i <= n-d:
      fl = True
      for k in range(d):
        fl &= fld[i+k][j] == '.'
      if fl:
        ans += 1
    if j <= m-d:
      fl = True
      for k in range(d):
        fl &= fld[i][j+k] == '.'
      if fl:
        ans += 1

print ans

Submission status: Accepted

Solution code:
N, M, D = map(int, input().split())
space = [input() for _ in range(N)]
a = sum(len(r)-D+1 for row in space for r in row.split('#') if len(r) >= D)
space = [''.join(l) for l in list(zip(*space))]
b = sum(len(r)-D+1 for row in space for r in row.split('#') if len(r) >= D)
print(a+b)

Submission status: Accepted

Solution code:
def main():
    N,M,D = map(int,input().split())
    s,X,Y = [],[],[]
    for _ in N*[0]:
        s.append(input())
        X.append(M*[0])
        Y.append(M*[0])
    for y in range(0,N,1):
        for x in range(M-1,-1,-1):
            if( s[y][x] != '#' ):
                X[y][x] += 1
            if( s[y][x] != '#' and x+1<M ):
                X[y][x] = X[y][x+1] + 1
    for y in range(N-1,-1,-1):
        for x in range(0,M,1):
            if( s[y][x] != '#' ):
                Y[y][x] += 1
            if( s[y][x] != '#' and y+1<N ):
                Y[y][x] = Y[y+1][x] + 1
    ans = 0
    for y in range(N):
        for x in range(M):
            if( X[y][x] >= D ):
                ans += 1
            if( Y[y][x] >= D ):
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,d=[int(s)for s in input().split(" ")]
map_=[input()for i in range(n)]
cnt=0
for i in range(n):
    for j in range(m):
        t='.'*d
        if j<=m-d and map_[i][j:j+d]==t:cnt+=1
        if i<=n-d:
            state_ns=""
            for k in range(d):state_ns+=map_[i+k][j]
            if state_ns==t:cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
a = [int(i) for i in input().split(' ')]
N, M, D = a[0], a[1], a[2]

area = []
for i in range(N):
    area.append(input())

toori = 0
reverse_area = []
for tate in range(N):
    row_area = list(area[tate])
    for yoko in range(M - D + 1):
        mass = D
        for now_mass in range(D):
            if row_area[now_mass + yoko] == ".":
                mass -= 1
            if row_area[now_mass + yoko] == '#':
                break

            if mass == 0:
                toori += 1
                break


for tate in range(N - D + 1):
    for yoko in range(M):
        mass = D
        for now_mass in range(D):
            if area[now_mass + tate][yoko] == ".":
                mass -= 1
            if area[now_mass + tate][yoko] == '#':
                break

            if mass == 0:
                toori += 1
                break
print(toori)

Submission status: Accepted

Solution code:
N, M, D = map(int, input().split())
S = [input() for i in range(N)]
def calc(f, N, M):
    res = 0
    for i in range(N):
        cnt = 0
        for j in range(M):
            c = f(i, j)
            if c is '#':
                cnt = 0
            else:
                cnt += 1
                if cnt >= D:
                    res += 1
    return res
print(calc(lambda i, j: S[i][j], N, M) + calc(lambda i, j: S[j][i], M, N))

Submission status: Accepted

Solution code:
n, m, d = map(int, input().split())
count = 0
a = []
for _ in range(n):
    a.append(input() + "#")
a.append("#" * m)
for i in range(n):
    for j in range(m):
        if a[i][j] == ".":
            for k in range(1, d):
                if a[i + k][j] == "#":
                    break
            else:
                count += 1
            for k in range(1,d):
                if a[i][j + k] == "#":
                    break
            else:
                count += 1
print(count)

Submission status: Accepted

Solution code:
n,m,d=map(int,input().split())
s=[]
for i in range(n):
   s.append(list(input()))
count=0
for i in range(n):
    for j in range(m):
        if s[i][j]==".":
            for k in range(1,d):
                if j+d>m:
                    break
                elif s[i][j+k]=="#":
                    break
            else:
                count+=1
for j in range(m):
    for i in range(n):
        if s[i][j]==".":
            for k in range(1,d):
                if i+d>n:
                    break
                elif s[i+k][j]=="#":
                    break
            else:
                count+=1             
    
print(count)

Submission status: Accepted

Solution code:
N, M, D = map(int, input().split())
A = []
for _ in range(N):
	A.append(list(input()))

r = 0
for n in range(N):
	for m in range(M):
		if A[n][m]=='#':
			pass
		elif A[n][m]=='.':
			if m+D>M:  # 水平方向
				pass
			else:
				if A[n][m:m+D].count('#')==0:
					r += 1
			if n+D>N:  #水平方向
				pass
			else:
				temp = True
				for i in range(1, D):
					if A[n+i][m]=='#':
						temp = False
						break
				if temp==True: r += 1

print(r)

Submission status: Accepted

Solution code:
N,M,D = [int(i) for i in input().split(" ")]
space=[]
for i in range(N):
    S=input()
    row=[]
    for s in S:
        if s==".":
            row.append(0)
        else:
            row.append(1)
    space.append(row)

retval=0
for i in range(N):
    for j in range(M):
        if space[i][j]==1:
            continue
        try:
            for k in range(D):
                if space[i+k][j]==1:
                    break
            else:
                retval+=1
        except IndexError:
            pass
        try:
            for k in range(D):
                if space[i][j+k]==1:
                    break
            else:
                retval+=1
        except IndexError:
            pass

print(retval)

Submission status: Accepted

Solution code:
n,m,d = map(int,input().split())
a = [[' ' for _ in range(m)] for _ in range(n)]
b = [[' ' for _ in range(n)] for _ in range(m)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        a[i][j] = s[j]
        b[j][i] = s[j]
cnt = 0
for i in range(n):
    tmp = ''.join(a[i])
    for j in range(m-d+1):
        if '.'*d == tmp[j:j+d]:
            cnt += 1
for i in range(m):
    tmp = ''.join(b[i])
    for j in range(n-d+1):
        if '.'*d == tmp[j:j+d]:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n, m, d = map(int, input().split())
x = [input() for _ in range(n)]
cnt = sum(len(r)-d+1 for row in x for r in row.split("#") if len(r) >= d)
x = ["".join(c) for c in list(zip(*x))]
cnt += sum(len(r)-d+1 for row in x for r in row.split("#") if len(r) >= d)
print(cnt)

Submission status: Accepted

Solution code:
#C
N,M,D = map(int,input().split())
S = [list(str(input())) for i in range(N)]
ans = 0

for i in range(N):
    yoko = S[i]
    count = 0
    for j in range(M):
        if yoko[j] == ".":
            count+=1
            if count >= D:
                ans+=1
        else:
            count = 0
            
T = [["" for i in range(N)] for j in range(M)]
for i in range(N):
    for j in range(M):
        T[j][i] = S[i][j]
        
for j in range(M):
    tate = T[j]
    count = 0
    for i in range(N):
        if tate[i] == ".":
            count+=1
            if count >= D:
                ans+=1
        else:
            count = 0
            
print(ans)

Submission status: Accepted

Solution code:
N, M, D = map(int, input().split())
S = [input() for i in range(N)]

ans = 0

if D == 1: print(sum([s.count('.') for s in S]))
else:
    for i in range(N):
        count = 0
        
        for s in S[i]:
            if s == '.': count += 1
            else: 
                if count >= D: ans += 1 + count - D
                count = 0
        if count >= D: ans += 1 + count - D
        
    for j in range(M):
        count = 0
        for i in range(N):
            if S[i][j] == '.': count += 1
            else:
                if count >= D: ans += 1 + count - D
                count = 0
        if count >= D: ans += 1 + count - D
    print(ans)

Submission status: Accepted

Solution code:
n, m, d = map(int, input().split())
fig = [list(input()) for i in range(n)]

hor = []
for i in range(n):
    tmp = 0
    for j in range(m):
        if fig[i][j]==".": tmp += 1
        else:
            hor.append(tmp)
            tmp = 0
    hor.append(tmp)

ver = []
for i in range(m):
    tmp = 0
    for j in range(n):
        if fig[j][i]==".": tmp += 1
        else:
            ver.append(tmp)
            tmp = 0
    ver.append(tmp)

ans = 0
for i in hor:
    if i-d>=0: ans += i-d+1
for i in ver:
    if i-d>=0: ans += i-d+1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Refreshment Area
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0632

"""
import sys


def solve(area, n, m, d):
    ans = 0
    for y in range(n):
        for x in range(m):
            horizontal = area[y][x:x+d]
            ans += '.' * d in horizontal
            vertical = ''.join([area[yy][x] for yy in range(y, n)])[:d]
            ans += '.' * d in vertical
    return ans


def main(args):
    n, m, d = map(int, input().split())
    area = [input() for _ in range(n)]
    ans = solve(area, n, m, d)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
n,m,d=map(int,input().split())
mp=[input() for _ in range(n)]
t='.'*d
cnt=0
for i in range(n):
    for j in range(m):
        if j<=m-d and mp[i][j:j+d]==t:
            cnt+=1
        if i<=n-d:
            ns=''
            for l in range(d):
                ns+=mp[i+l][j]
                if ns==t:
                    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N, M, D = map(int, input().split())
input_list = [["."]*M]*N
for i in range(N):
    input_list[i] = list(input())

# 連続した領域の長さの集合
area_list = []
    
# 横方向
for i in range(N):
    if M < D:
        break
        
    tmp_count = 0
    for j in range(M):
        if input_list[i][j] == ".":
            tmp_count += 1
        else:
            if tmp_count >= D:
                area_list.append(tmp_count)
            tmp_count = 0
    
    if tmp_count >= D:
        area_list.append(tmp_count)

# 縦方向
for j in range(M):
    if N < D:
        break
        
    tmp_count = 0
    for i in range(N):
        if input_list[i][j] == ".":
            tmp_count += 1
        else:
            if tmp_count >= D:
                area_list.append(tmp_count)
            tmp_count = 0
    
    if tmp_count >= D:
        area_list.append(tmp_count)

sa_list = [D-1]*len(area_list)
add_list = [x - y for (x, y) in zip(area_list, sa_list)]
print(sum(add_list))

Submission status: Accepted

Solution code:
n,m,d=map(int,input().split())
field=[]
for i in range(n):
    field.append(input())
ans=0
for i in field:
    ren=0
    j=i.split("#")
    for k in j:
        if len(k)>=d:ans+=len(k)-d+1
field_r = [list(x) for x in zip(*field)]
for i in range(m):
    field_r[i]="".join(map(str,field_r[i]))
for i in field_r:
    ren=0
    j=i.split("#")
    for k in j:
        if len(k)>=d:ans+=len(k)-d+1
print(ans)

Submission status: Accepted

Solution code:
n,m,d=map(int,input().split())
lst=[input()+"#"*d for i in range(n)]
for i in range(d):
    lst.append("#"*m)
ans=0
for i in range(n):
    for j in range(m):
        if not "#" in lst[i][j:j+d]:ans+=1
        if not "#" in [lst[i+x][j] for x in range(d)]:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m, d = map(int, input().split())

floor = []
for _ in range(n):
    floor.append(list(input()))

cnt = 0
for i in range(n):
    for j in range(m):
        if floor[i][j] == ".":
            for k in range(1, d):
                if j+k >= m:
                    break
                elif floor[i][j+k] != ".":
                    break
            else:
                cnt += 1

            for k in range(1, d):
                if i+k >= n:
                    break
                elif floor[i+k][j] != ".":
                    break
            else:
                cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m,d = map(int, input().split())
ans = []
for i in range(n):
    ans.append(list(str(input())))
ams = []
for i in range(m):
    ami = []
    for a in ans:
        ami.append(a[i])
    ams.append(ami)
#print(ans,ams)
num0 = [] 
for an in ans:
    cnt = 0
    for i in range(len(an)):
        if an[i] == ".":
            cnt += 1
            if (i == len(an)-1):
                num0.append(cnt)
        elif an[i] == "#":
            num0.append(cnt)
            cnt = 0
for am in ams:
    cnt = 0
    for i in range(len(am)):
        if am[i] == ".":
            cnt += 1
            if (i == len(am) -1):
                num0.append(cnt)
        elif am[i] == "#":
            num0.append(cnt)
            cnt = 0
#print(num0)
p = 0
for cnt in num0:
    if (cnt >= d):
        p += (cnt - d+1)
            
print(p)