Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Accepted

Solution code:
a=map(int, raw_input().split())
lis=[]
for i in range(a[0]):
    b=list(raw_input())
    lis.append(b)

pro=[]
cou=0
for i in range(a[0]):
    pre=[]
    for j in range(a[1]):
        if lis[i][j]=="#":
            cou+=1
        pre.append(2501)
    pro.append(pre)

while True:
    ch=0
    for i in range(a[0]):
        for j in range(a[1]):
            if lis[i][j]==".":
                if i==0:
                    if j==0:
                        pro[i][j]=1
                    elif j==a[1]-1:
                        u = 2501
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = 2501
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                elif i==a[0]-1:
                    if j==0:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = 2501
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                else:
                    if j==0:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j+ 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
    if ch==0:
        break
if pro[a[0]-1][a[1]-1]==2501:
    print -1
else:
    print a[0]*a[1]-cou-pro[a[0]-1][a[1]-1]

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
List = [input() for i in range(H)]
queue = [(0,0,1)]
shape = sum(row.count("#") for row in List)
used = {(0,0)}

def check(x,y,c):
    if x > W-1 or y > H-1 or x < 0 or y < 0:
        return
    if List[y][x] == '#':
        return
    if (x,y) in used:
        return
    queue.append((x,y,c))
    used.add((x,y))
    
f = -1
while queue:
    x,y,c = queue.pop(0)
    if x == W-1 and y == H-1:
        f = 1
        break
    check(x+1, y, c+1)
    check(x,y+1,c+1)
    check(x-1,y,c+1)
    check(x,y-1,c+1)
print(f if f == -1 else(H*W - c - shape))

Submission status: Accepted

Solution code:
import collections
h,w = map(int,input().split())
s=[list(input()) for _ in range(h)]
deq = collections.deque([[0,0,0]])

while deq:
    i,j,k = deq.popleft()
    if not((i in range(h)) and (j in range(w))):
        continue
    if s[i][j] != '.':
        continue
    s[i][j]=k
    if i==h-1 and j == w-1:
        break
    deq.append([i + 1, j, k + 1])
    deq.append([i - 1, j, k + 1])
    deq.append([i, j + 1, k + 1])
    deq.append([i, j - 1, k + 1])
if s[h-1][w-1] == '#'or s[h-1][w-1] =='.':
    print(-1)
else:
    black = sum([y.count('#') for y in s])
    print(h*w-black-s[h-1][w-1]-1)

Submission status: Accepted

Solution code:
def reach(s,t,G):
    V,E=G
    check=set()
    step=0
    nex={s}
    while nex!=set():
        if t in nex:
            return(step)
        else:
            check|=nex
            nex={v for v in V if v not in check and any([(v,w) in E for w in nex])}
            step+=1
    return(-1)

H,W=map(int,input().split())
S=[input() for i in range(H)]

point=0
sharp=0
V=set()
E=set()
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            point+=1
            V|={(i,j)}
            if i-1>=0:
                if S[i-1][j]=='.':
                    E|={((i,j),(i-1,j))}
            if i+1<=H-1:
                if S[i+1][j]=='.':
                    E|={((i,j),(i+1,j))}
            if j-1>=0:
                if S[i][j-1]=='.':
                    E|={((i,j),(i,j-1))}
            if j+1<=W-1:
                if S[i][j+1]=='.':
                    E|={((i,j),(i,j+1))}
        if S[i][j]=='#':
            sharp+=1
G=(V,E)

if reach((0,0),(H-1,W-1),G)==-1:print(-1)
else:print(point-(reach((0,0),(H-1,W-1),G)+1))

Submission status: Accepted

Solution code:
h,w = map(int, input().split())

smap = [list(input()) for _ in range(h)]
cmap = [[float('inf') for _ in range(w)] for _ in range(h)]
queue = [(0,0)]
l = [(1,0), (-1,0), (0,1), (0,-1)]

smap[0][0] = '#'

initial_whites = 0

for x in smap:
    for y in x:
        if y == '.':
            initial_whites += 1

cmap[0][0] = 0

while queue:
    v = queue.pop(0)
    for x in l:
        y = (v[0]+x[0], v[1]+x[1])
        if 0 <= y[0] <= h-1 and 0 <= y[1] <= w-1:
            if smap[y[0]][y[1]] == '.':
                smap[y[0]][y[1]] = '#'
                cmap[y[0]][y[1]] = cmap[v[0]][v[1]] + 1
                queue.append(y)
            else:
                pass
        else:
            pass


if cmap[h-1][w-1] == float('inf'):
    print(-1)
else:
    print(initial_whites - cmap[h-1][w-1])

Submission status: Accepted

Solution code:
h,w = map(int, input().split())

smap = []
for _ in range(h):
    s = input()
    ss = []
    for i in range(w):
        ss.append(s[i])
    smap.append(ss)
cmap = [[float('inf') for _ in range(w)] for _ in range(h)]
queue = [(0,0)]
l = [(1,0), (-1,0), (0,1), (0,-1)]

initial_whites = 0

for x in smap:
    for y in x:
        if y == '.':
            initial_whites += 1

cmap[0][0] = 0

while queue:
    v = queue.pop(0)
    smap[v[0]][v[1]] = '#'
    for x in l:
        y = (v[0]+x[0], v[1]+x[1])
        if 0 <= y[0] <= h-1 and 0 <= y[1] <= w-1:
            if smap[y[0]][y[1]] == '.':
                smap[y[0]][y[1]] = '#'
                cmap[y[0]][y[1]] = cmap[v[0]][v[1]] + 1
                queue.append(y)
            else:
                pass
        else:
            pass


if cmap[h-1][w-1] == float('inf'):
    print(-1)
else:
    print(initial_whites - cmap[h-1][w-1] - 1)

Submission status: Accepted

Solution code:
H, W = tuple(map(int, input().split()))
s = [input() for _ in range(H)]
q = [(0, 0, 0)]
h = {(0, 0)}
opt = float('inf')
while q:
    i, j, k = q.pop(0)
    if i == H - 1 and j == W - 1:
        opt = k
        break
    a = [(u, v)
         for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
         if 0 <= u < H and 0 <= v < W and s[u][v] == '.' and (u, v) not in h]
    q += [(u, v, k + 1) for u, v in a]
    h |= set(a)
print(max(-1, sum(t.count('.') for t in s) - opt - 1))

Submission status: Accepted

Solution code:
import sys

H, W = [int(x) for x in input().split()]

grid = [[c for c in input()] for i in range(H)]
visited = [[False for i in range(W)] for j in range(H)]
dist = [[0 for i in range(W)] for j in range(H)]

# 白の数
nw = sum([line.count('.') for line in grid])

# 最短ルートの探索(幅優先探索)
start = (0, 0)
goal = (H - 1, W - 1)

visited[start[0]][start[1]] = True
dist[start[0]][start[1]] = 1
queue = [start]
while len(queue) > 0:
    v = queue[0]
    queue.remove(v)

    if v == goal:
        print(nw - dist[v[0]][v[1]])
        sys.exit()
    else:
        if (v[0] > 0 and not visited[v[0] - 1][v[1]]
                and grid[v[0] - 1][v[1]] == '.'):
            queue.append((v[0] - 1, v[1]))
            visited[v[0] - 1][v[1]] = True
            dist[v[0] - 1][v[1]] = dist[v[0]][v[1]] + 1

        if (v[0] < H - 1 and not visited[v[0] + 1][v[1]]
                and grid[v[0] + 1][v[1]] == '.'):
            queue.append((v[0] + 1, v[1]))
            visited[v[0] + 1][v[1]] = True
            dist[v[0] + 1][v[1]] = dist[v[0]][v[1]] + 1

        if (v[1] > 0 and not visited[v[0]][v[1] - 1]
                and grid[v[0]][v[1] - 1] == '.'):
            queue.append((v[0], v[1] - 1))
            visited[v[0]][v[1] - 1] = True
            dist[v[0]][v[1] - 1] = dist[v[0]][v[1]] + 1

        if (v[1] < W - 1 and not visited[v[0]][v[1] + 1]
                and grid[v[0]][v[1] + 1] == '.'):
            queue.append((v[0], v[1] + 1))
            visited[v[0]][v[1] + 1] = True
            dist[v[0]][v[1] + 1] = dist[v[0]][v[1]] + 1

print(-1)

Submission status: Accepted

Solution code:
H , W= map(int, input().split())
que = [(0, 0)]
S = [input() for i in range(H)]
flag = [[1<<30 for i in range(W)] for j in range(H)]
flag[0][0] = 1
cnt = sum(row.count('.') for row in S)
while que:
	y, x = que.pop(0)
	for ny, nx in [1, 0], [-1, 0], [0, 1], [0, -1]:
		nx += x
		ny += y
		if ny >= 0 and nx >= 0 and ny < H and nx < W and S[ny][nx] != '#' and flag[ny][nx] > flag[y][x] + 1:
			que.append((ny, nx))
			flag[ny][nx] = flag[y][x] + 1
			if (ny, nx) == (H - 1, W - 1):
				print(cnt - flag[ny][nx])
				exit()
print(-1)

Submission status: Accepted

Solution code:
import queue
INF = 1 << 30
H , W= map(int, input().split())
que = [(0, 0)]
S = [input() for i in range(H)]
flag = [[INF for i in range(W)] for j in range(H)]
flag[0][0] = 1
cnt = sum(row.count('.') for row in S)
while que:
	y, x = que[0]
	que.pop(0)
	for ny, nx in [1, 0], [-1, 0], [0, 1], [0, -1]:
		nx += x
		ny += y
		if ny >= 0 and nx >= 0 and ny < H and nx < W and S[ny][nx] != '#' and flag[ny][nx] > flag[y][x] + 1:
			que.append((ny, nx))
			flag[ny][nx] = flag[y][x] + 1
			if (ny, nx) == (H - 1, W - 1):
				print(cnt - flag[ny][nx])
				exit()
print(-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

visited = [(0, 0)]
queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop(0)
    for dy, dx in directions:
        y2, x2 = y + dy, x + dx
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        if (y2, x2) in visited:
            continue
        if maze[y2][x2] == '.':
            distances[y2][x2] = distances[y][x] + 1
            visited.append((y2, x2))
            queue.append((y2, x2))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
List = [input() for i in range(H)]
queue = [(0,0,1)]
shape = sum(row.count("#") for row in List)
used ={(0,0)}

def check(x,y,c):
    if(x>W-1 or y>H-1 or x<0 or y<0):
        return
    if(List[y][x] == '#'):
        return
    if(x,y) in used:
        return
    queue.append((x,y,c+1))
    used.add((x,y))

f= -1
while queue:
    x,y,c = queue[0]
    if x==W-1 and y==H-1:
        f=1
        break
    queue.pop(0)
    check(x+1,y,c)
    check(x, y+1,c)
    check(x-1,y,c)
    check(x, y-1,c)
print(f if f == -1 else(H*W-c-shape))

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
List = []
queue = [(0,0,1)]
shape = 0
used ={(0,0)}
for i in range(H):
    x = input()
    shape += x.count('#')
    List.append(x)

def check(x,y,c):
    if(x>W-1 or y>H-1 or x<0 or y<0):
        return
    if(List[y][x] == '#'):
        return
    if(x,y) in used:
        return
    queue.append((x,y,c+1))
    used.add((x,y))

flag = -1
while(len(queue) != 0):
    x,y,c = queue[0]
    if x==W-1 and y==H-1:
        flag = 1
        break
    queue.pop(0)
    check(x+1,y,c)
    check(x, y+1,c)
    check(x-1,y,c)
    check(x, y-1,c)
if(flag == 1):
    print(H*W - c - shape)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Accepted

Solution code:
import numpy as np

def iterate2(mapdata, passed, start):
    queue = [(start, 0)]

    while len(queue) > 0:
        curr, count = queue[0]
        del queue[0]
        if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
            return count
        if mapdata[curr[0]][curr[1]] == '#':
            continue
        if passed[curr] > 0:
            continue
        passed[curr] = 1

        if curr[0] < passed.shape[0] - 1:
            queue.append(((curr[0] + 1, curr[1]), count + 1))
        if curr[1] < passed.shape[1] - 1:
            queue.append(((curr[0], curr[1] + 1), count + 1))
        if curr[0] > 0:
            queue.append(((curr[0] - 1, curr[1]), count + 1))
        if curr[1] > 0:
            queue.append(((curr[0], curr[1] - 1), count + 1))
    
    return -1

h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int8)
count = iterate2(mapdata, passed, (0, 0))
#print(dotsum)
#print(count)
if count > 0:
    print(dotsum - count - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

# 入力
H,W = map(int, input().split())
S = [input() for i in range(H)]
C = sum(s.count('.') for s in S)

dd = ((-1,0), (0, -1), (1,0), (0,1))
que = deque([(0,0,0)])
used = {(0,0)}

res = None
while que :
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        ni = s + di; nj = t + dj
        if(not 0 <= ni < H) or (not 0 <= nj < W) or S[ni][nj] == '#' or (ni,nj) in used:
            continue
        used.add((ni,nj))
        que.append((ni,nj,cost+1))

# 結果出力
if res:
    print(C - 1 - res)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math

H, W = map(int, input().split(' '))
S = [input() for i in range(H)]
M = [[10000]*W for i in range(H)]
M[0][0] = 0
for k in range(H*W):
    for i in range(H):
        for j in range(W):
            if M[i][j] == k:
                if i > 0 and M[i-1][j] > k+1 and S[i-1][j] == '.':
                    M[i-1][j] = k+1
                if i < H-1 and M[i+1][j] > k+1 and S[i+1][j] == '.':
                    M[i+1][j] = k+1
                if j > 0 and M[i][j-1] > k+1 and S[i][j-1] == '.':
                    M[i][j-1] = k+1
                if j < W-1 and M[i][j+1] > k+1 and S[i][j+1] == '.':
                    M[i][j+1] = k+1
if M[-1][-1] == 10000:
    print(-1)
    sys.exit()
minDis = M[-1][-1] + 1
numWhite = 0
for line in S:
    numWhite += line.count('.')
print(numWhite-minDis)

Submission status: Accepted

Solution code:
import copy
import sys
def advance(visited,now):
    result=W*H+1
    if now==W*H-1:
        result=min( len(visited),result)
    else:
        for i in range(W*H):
            if i in visited:
                continue
            elif G[i][now]==1:
                _visited=copy.copy(visited)
                _visited.append(now)
                result=advance(_visited,i)
    return result

H,W=[int(i) for i in input().split(" ")]
Map=[]
white=0
for i in range(H):
    l=[]
    s=input()
    for j in s:
        if j==".":
            l.append(0)
            white+=1
        else:
            l.append(-1)

    Map.append(l)
Map[0][0]=1
G=[[0 for i in range(H*W)] for j in range(H*W)]

for i in range(H):
    for j in range(W):
        if Map[i][j]==-1 :
            continue
        else:
            try:
                if Map[i+1][j]==0:
                    G[W*i+j][W*(i+1)+j]=1
                    G[W*(i+1)+j][W*i+j]=1
            except IndexError:
                pass
            try:
                if Map[i][j+1]==0:
                    G[W*i+j][W*i+j+1]=1
                    G[W*i+j+1][W*i+j]=1
            except IndexError:
                pass

advanced=[[0,0]]
step=2
while Map[-1][-1]==0:
    _advanced=[]
    for i in advanced:
        try:
            if Map[i[0]+1][i[1]]==0:
                Map[i[0]+1][i[1]]=step
                _advanced.append([i[0]+1,i[1]])
        except IndexError:
            pass
        try:
            if Map[i[0]][i[1]+1]==0:
                Map[i[0]][i[1]+1]=step
                _advanced.append([i[0],i[1]+1])
        except IndexError:
            pass
        try:
                if Map[i[0]-1][i[1]]==0 and i[0]!=0:
                    Map[i[0]-1][i[1]]=step
                    _advanced.append([i[0]-1,i[1]])
        except IndexError:
                pass
        try:
                if Map[i[0]][i[1]-1]==0 and i[1]!=0:
                    Map[i[0]][i[1]-1]=step
                    _advanced.append([i[0],i[1]-1])
        except IndexError:
                pass
    step+=1
    advanced=copy.deepcopy(_advanced)
    if len(advanced)==0:
        print(-1)
        sys.exit()
print(white-Map[-1][-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
M = [["." for i in range(W)] for j in range(H)]
S = [input() for i in range(H)]

start = (0, 0, 0)
queue = [start]
white = 0
isGoal = False
depth = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            white+=1

while(len(queue)):
    i, j, d = queue.pop(0)
    if i < 0 or i >= H or j < 0 or j >= W or S[i][j] == "#" or M[i][j] == "#":
        continue
    elif i == H - 1 and j == W - 1:
        isGoal = True
        depth = d
        break
    M[i][j] = "#"
    for ni, nj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        queue.append((i+ni, j+nj, d+1))

print(white-d-1 if isGoal else -1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = [list(input()) for x in range(H)]
d = [[None for y in range(W)] for x in range(H)]
q = []
white = 0
for x in range(H):
  for y in range(W):
    if s[x][y] == '.':
      white += 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append([0, 0, 0])

def Haba(x_now, y_now, d_now, s, d, q):
  for i in range(4):
    if 0 <= x_now + dx[i] and x_now + dx[i] < H and 0 <= y_now + dy[i] and y_now + dy[i] < W:
      if s[x_now + dx[i]][y_now + dy[i]] == '.':
        s[x_now + dx[i]][y_now + dy[i]] = '#'
        d[x_now + dx[i]][y_now + dy[i]] = d_now + 1
        q.append([x_now+dx[i], y_now+dy[i], d_now + 1])

while(len(q) > 0):
  x_now, y_now, d_now = q.pop(0)
  Haba(x_now, y_now, d_now, s, d, q)
if d[H - 1][W - 1] is not None:
  ans = white - d[H - 1][W - 1]  - 1
else:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

temp = input()
H,W = temp.split()
H = int(H)
W = int(W)
pref = np.zeros((H,W))
for i in range(H):
    row = input()
    for j in range(W):
        if row[j] == ".":
            pref[i][j] = 1
        else:
            pref[i][j] = 0
totalw = np.count_nonzero(pref)

a = np.zeros((H,W))     

quere = []
quere.append(0)
while quere != []:
    locas = quere[0]
    tempscore = (H+1)*(W+1)
    if locas % W > 0 :
        left = locas - 1
        if a[(left // W)][(left % W)] == 0 and pref[(left // W)][(left % W)] == 1:
            if left not in quere:
                quere.append(left)
        elif a[(left // W)][(left % W)] > 0:
            tempscore = min(tempscore,a[(left // W)][(left % W)])
    if locas % W < W-1:
        right = locas + 1
        if a[(right // W)][(right % W)] == 0 and pref[(right // W)][(right % W)] == 1:
            if right not in quere:
                quere.append(right)
        elif a[(right // W)][(right % W)] > 0:
            tempscore = min(tempscore,a[(right // W)][(right % W)])
    if locas // W > 0 :
        up = locas - W
        if a[(up // W)][(up % W)] == 0 and pref[(up // W)][(up % W)] == 1:
            if up not in quere:
                quere.append(up)
        elif a[(up // W)][(up % W)] > 0:
            tempscore = min(tempscore,a[(up // W)][(up % W)])
    if (locas // W) < (H - 1):
        down = locas + W
        if a[(down // W)][(down % W)] == 0 and pref[(down // W)][(down % W)] == 1:
            if down not in quere:
                quere.append(down)
        elif a[(down // W)][(down % W)] > 0:
            tempscore = min(tempscore,a[(down // W)][(down % W)])
    
    if locas == 0:tempscore=0
    
    a[(locas // W)][(locas % W)] = tempscore + 1
    quere.pop(0)
    

leng = a[H-1][W-1]
if leng > 0 and leng < (H+1)*(W+1):
    score = totalw-leng
    print(int(score))
else:print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
h, w = map(int, raw_input().split())
# 文字列の入力
s = [raw_input() for i in range(h)]

accessible = [(0,0)]
accessible_now = [(0,0)]
n_black = sum([ss.count('#') for ss in s]) 

stroke = 1
while True:
  stroke += 1
  accessible_next = [] 
  for loc in accessible_now:
    for step in [(1,0),(0,1),(-1,0),(0,-1)]:
      loc_next = (loc[0]+step[0],loc[1]+step[1])
      if loc_next == (h-1,w-1):
        print h*w-n_black-stroke 
        exit(0)
      if ((-1 in loc_next) or (loc_next[0]==h) or (loc_next[1]==w)):
        continue
      if loc_next in accessible:
        continue
      if s[loc_next[0]][loc_next[1]] == '#':
        continue
      accessible.append(loc_next)
      accessible_next.append(loc_next)
  accessible_now = accessible_next
  if(len(accessible_next)==0):
    print -1
    exit(0)

Submission status: Accepted

Solution code:
from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x + dx, y + dy) for dx, dy in ((0, -1), (1, 0), (0, 1), (-1, 0))]
    return list(filter(lambda a: 0 <= a[0] < max_x and
                                 0 <= a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


H, W = tuple(map(int, input().split()))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

grid[0][0] = False
p_grid = {(0, 0): 0}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        grid[a[0]][a[1]] = False
        p_grid[a] = p_grid[here] + 1
    if not arounds:
        continue
    queue.extend(arounds)

if (H-1, W-1) in p_grid:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
 
 
def dfs(field):
    q = deque([(0, 0, 1)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return -1
 
 
h, w = map(int, input().split())
field = [input() for _ in range(h)]
init_black = sum(r.count('#') for r in field)
res = dfs(field)
if res == -1:
    print(-1)
else:
    print(h * w - res - init_black)

Submission status: Accepted

Solution code:
def next(s,x,y):
	ans = []
	if s[x][y+1] == '.':
		ans.append([x,y+1])
	if s[x][y-1] == '.':
		ans.append([x,y-1])
	if s[x+1][y] == '.':
		ans.append([x+1,y])
	if s[x-1][y] == '.':
		ans.append([x-1,y])
	return ans

h,w = map(int,input().split())
s = []
add = ['#' for i in range(w+2)]
s.append(add)
counter = 0
for i in range(h):
	sinput = str(input())
	stemp = []
	for i in range(w):
		stemp.append(sinput[i])
	for i in range(w):
		if stemp[i] == '.':
			counter += 1
	stemp.insert(0,'#')
	stemp.append('#')
	s.append(stemp)
s.append(add)

arrival = [[0 for i in range(w+1)] for k in range(h+1)]
q = [[1,1]]
arrival[1][1] = 1
while len(q) > 0:
	nextcell = next(s,q[0][0],q[0][1])
	for i in range(len(nextcell)):
		if arrival[nextcell[i][0]][nextcell[i][1]] == 0:
			q.append(nextcell[i])
			arrival[nextcell[i][0]][nextcell[i][1]] = arrival[q[0][0]][q[0][1]] + 1
	q.pop(0)

if arrival[h][w] == 0:
	print(-1)
else:
	print(counter - arrival[h][w])

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]
def bfs():
    dist = {(0,0): 0}
    que = deque([(0,0)])
    while que:
        i, j = que.popleft()
        for k,l in ((0,1),(1,0),(0,-1),(-1,0)):
            k += i
            l += j
            if 0<=k<h and 0<=l<w and s[k][l]=='.' and (k,l) not in dist:
                dist[k,l] = dist[i,j] + 1
                que.append((k,l))
    return dist
dist = bfs()
if (h-1,w-1) in dist:
    black = sum(line.count('#') for line in s)
    print(h*w - black - (dist[h-1,w-1]+1))
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    H, W = [int(x) for x in input().strip().split()]
    tables = []
    white_count = 0
    for i in range(H):
        rows = [str(x) for x in list(input().strip())]
        white_count += rows.count(".")
        tables.append(rows)

    next_cells = [(0, 0, 1)]
    while(next_cells):
        _next_cells = []
        for next_cell in next_cells:
            y, x, step = next_cell
            if y == H-1 and x == W-1: #Goal
                tables[y][x] = str(min(step+1, int(tables[y][x])))
                continue

            for cond, ys, xs in [(y != 0,y-1,x),(y != H-1,y+1,x),(x != 0,y,x-1),(x != W-1,y,x+1)]:
                if cond: # up OK
                    if tables[ys][xs] != "#": # move OK
                        if tables[ys][xs] != ".": # 既に通った
                            if step+1 < int(tables[ys][xs]):
                                tables[ys][xs] = str(step+1)
                                _next_cells.append((ys, xs, step+1))
                        else: # 初めて通る
                            tables[ys][xs] = str(step+1)
                            _next_cells.append((ys, xs, step+1))
            # end for
        # end for
        next_cells = list(set(_next_cells)) # 重複カット
    # end while
    if tables[H-1][W-1] == ".":
        return -1
    return white_count - int(tables[H-1][W-1])
    
if __name__ == '__main__':
    print(main())