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:
# ABC88 D問題
from collections import deque
import sys
import math
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

H,W=na()
f = [input() for i in range(H)]
#print(f)

def bfs():
    Q=deque([(0,0,1)])
    visited = [[False] * W for _ in range(H)]
    while Q:
        h,w,d = Q.popleft()
        if(h==H-1 and w==W-1):
            return d
        #d = [[1,0],[-1,0],[0,1],[0,-1]]
        if visited[h][w]:
            continue
        visited[h][w] = True
        if h > 0 and f[h - 1][w] == '.':
            Q.append((h - 1, w, d + 1))
        if h < H - 1 and f[h + 1][w] == '.':
            Q.append((h + 1, w, d + 1))
        if w > 0 and f[h][w - 1] == '.':
            Q.append((h, w - 1, d + 1))
        if w < W - 1 and f[h][w + 1] == '.':
            Q.append((h, w + 1, d + 1))
    else:
        return -1

#幅優先で迷路を解く
#H*W-(最短経路長)-(黒いマス)が答え
black_sum=0
for i in range(H):
    black_sum+=f[i].count("#")
#print(black_sum)

res=bfs()
if(res==-1):
    print(res)
else:
    print(H*W-res-black_sum)

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
dungeon = []
memo = []
whitecount = 0
for i in range(0, H):
	dlst = []
	nlst = []
	s = raw_input()
	for j in range(0, W):
		if s[j] == '.': whitecount += 1
		dlst.append(s[j]=='.')
		nlst.append(H*W+1)
	dungeon.append(dlst)
	memo.append(nlst)
max = -1
queue = [[0, 0, 1]]
while queue != []:
	now = queue.pop(0)
	if now[2] < memo[now[0]][now[1]] and dungeon[now[0]][now[1]]:
		memo[now[0]][now[1]] = now[2]
		for i in range(0, 2):
			nexth = now[0] - 1 + 2*i
			nextw = now[1] - 1 + 2*i
			if 0 <= nexth and nexth < H:
				queue.append([nexth, now[1], now[2]+1])
			if 0 <= nextw and nextw < W:
				queue.append([now[0], nextw, now[2]+1])
if max < whitecount - memo[H-1][W-1]:
	max = whitecount-memo[H-1][W-1]
print max

Submission status: Accepted

Solution code:
import queue

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

white = 0

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            white += 1

q = queue.Queue()

move = [[0,1],[0,-1],[1,0],[-1,0]]

q.put([0,0])

inf = float('inf')
d = [[inf for i in range(w)] for j in range(h)]
d[0][0] = 0

while not q.empty():
    p = q.get()
    for m in move:
        if 0<=p[0]+m[0]<h and 0<=p[1]+m[1]<w and d[p[0]+m[0]][p[1]+m[1]] == inf and s[p[0]+m[0]][p[1]+m[1]] != '#':
            d[p[0]+m[0]][p[1]+m[1]] = d[p[0]][p[1]]+1
            q.put([p[0]+m[0], p[1]+m[1]])

if d[h-1][w-1] ==inf:
    print(-1)
else:
    print(white-d[h-1][w-1]-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
num = 1
dis = [[10**9]*w for _ in range(h)]
cnt = 0
for i in range(len(s)):
    cnt += s[i].count('.')
def bfs():
    queue = []
    done = []
    queue.insert(0,(0,0))
    dis[0][0] = 1

    while len(queue):
        y,x = queue.pop()
        if (y,x) in done:
            continue
        else:
            done.insert(0,(y,x))
        if x==w-1 and y==h-1:
            break

        for i in range(0,4):
            nx,ny = x+[1,0,-1,0][i], y+[0,1,0,-1][i]
            if 0<=nx<w and 0<=ny<h and s[ny][nx]!='#':
                queue.insert(0,(ny,nx))
                dis[ny][nx] = min(dis[ny][nx],dis[y][x]+1)
    return dis[h-1][w-1]
ret = bfs()
if ret==10**9:
    print(-1)
else:
    print(cnt-ret)

Submission status: Accepted

Solution code:
import queue
H,W=map(int, input().split())
inmap = [input() for _ in range(H)]

q = queue.Queue(2500)
q.put((0,0,1))
cood = [(1,0),(-1,0),(0,1),(0,-1)]
res = 0

visited = set((0,0))

while not q.empty():
    x,y,cnt=q.get(False)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)

Submission status: Accepted

Solution code:
from collections import deque
R,C = map(int,input().split())
sy,sx = 1,1  #スタートの座標
gy,gx = R,C  #ゴールの座標
L = []
for i in range(R):
  L.append(list(input()))   #迷路の情報を受け取る
dy_dx = [[1,0],[-1,0],[0,1],[0,-1]]   #移動
black = 0
for i in range(R):
  for j in range(C):
    if L[i][j] == '#':
      black += 1
que = deque([[sy-1,sx-1]])   #queには次に見るべき座標が入る。括弧が二重になっていることに留意
L[sy-1][sx-1] = 0  #スタートの座標（迷路上）の情報を0に
while len(que) > 0:  #queが空でないときは
  cur = que.popleft()   #queの一番左を見る
  for i in range(4):  #現在見ているマスの上下左右をチェック
    if 0 <= cur[0]+dy_dx[i][0] <= R-1 and 0 <= cur[1]+dy_dx[i][1] <= C-1:  #移動した後も迷路内にあるかの確認
      if L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] == '.':  #まだ見ていない通路であれば
        L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] = L[cur[0]][cur[1]]+1  #現在見ているマスの手数+1を入れる
        que.append([cur[0]+dy_dx[i][0],cur[1]+dy_dx[i][1]])   #queの末尾に今チェックした座標を入れる
if L[gy-1][gx-1] == '#':
  print(-1)
elif L[gy-1][gx-1] == '.':
  print(-1)
else:
  print(R*C-L[gy-1][gx-1]-1-black)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]


first_black = sum([row.count('#') for row in G])
que = deque([(0, 0)])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 0
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        if not ((0 <= nh + dh < H) & (0 <= nw + dw < W)):
            continue
        if G[nh + dh][nw + dw] == '#':
            continue
        if dist[nh + dh][nw + dw] > 0:
            continue

        dist[nh + dh][nw + dw] = dist[nh][nw] + 1
        que.appendleft((nh + dh, nw + dw))


if dist[-1][-1] != -1:
    print(H * W - dist[-1][-1] - first_black - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
#方針 最短経路以外を黒に塗れば良い
#最短経路が複数あってもその時通る白マスの数は不変なので、黒く塗れる白マスの数も不変である。
#したがって最短経路を求め(この時+1が実際に通る白マスの数になる)元々の白マスの数から
#最短経路+1を減算すれば答えは求まることになる。

from collections import deque

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

white_panel_cnt = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            white_panel_cnt += 1
que = deque()

#スタート位置は(1,1)※list的には(0,0)になっている
sx,sy,gx,gy = (0,0,W-1,H-1)
que.append((sx,sy))
distance_from_start = [[-1]*W for _ in range(H)]
distance_from_start[sy][sx] = 0
move = [[1,0],[-1,0],[0,1],[0,-1]]

def minimum_distance():
    while len(que) != 0:
        x,y = que.popleft()
        #for i in range(len(distance_from_start)):
            #print(distance_from_start[i])
        if x == gx and y == gy:
            return distance_from_start[y][x]
        for i in range(4):
            next_x = x + move[i][0]
            next_y = y + move[i][1]
            #print(next_x,next_y)
            if next_x < 0 or next_x >= W or next_y < 0 or next_y >= H or distance_from_start[next_y][next_x] != -1 or maze[next_y][next_x] == '#':
                continue
            #print(distance_from_start[y][x])
            distance_from_start[next_y][next_x] = distance_from_start[y][x] + 1
            que.append((next_x,next_y))
        #for i in range(len(distance_from_start)):
            #print(distance_from_start[i])

distance = minimum_distance()
#print('distance={}'.format(distance))
if distance == None:
    score = -1
else :
    score = white_panel_cnt-(distance+1)

print(score)

Submission status: Accepted

Solution code:

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

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

path = [[[] for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])
M_checked[0][0]=True
while len(Q)>0:
    i,j=Q.pop()
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            M_checked[p[0]][p[1]]=True
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)

Submission status: Accepted

Solution code:
import Queue
def main():
    H,W=map(int,raw_input().split())
    s=[raw_input() for i in range(H)]
    q=Queue.Queue()
    visited=[[False]*W for _ in range(H)]
    dist=[[1145141919810]*W for _ in range(H)]
    visited[0][0]=True
    dist[0][0]=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    q.put((0,0))

    while not q.empty():
        x,y=q.get()
        for i in range(4):  
            xx=x+dx[i]
            yy=y+dy[i]
            if (not 0<=xx<H) or (not 0<=yy<W): continue
            if s[xx][yy] == "#" :continue
            if visited[xx][yy]:continue
            visited[xx][yy]=True
            dist[xx][yy]=dist[x][y]+1
            q.put((xx,yy))
    if not visited[H-1][W-1]:
        print(-1)
        return
    use=[[False]*W for _ in range(H)]
    use[H-1][W-1]=True
    use[0][0]=True
    (x,y)=(H-1, W-1)
    while (x,y) != (0,0):
        use[x][y]=True
        mpos=(-1,-1)
        mval=1145141919
        for i in range(4):
            xx=x+dx[i]
            yy=y+dy[i]
            if (not 0<=xx<H) or (not 0<=yy<W): continue     
            if dist[xx][yy] < mval:
                mpos=(xx,yy)
                mval=dist[xx][yy]
        x,y=mpos
    cnt=0
    for x in range(H):
        for y in range(W):
            if s[x][y] == "." and not use[x][y]: cnt+=1
    print(cnt)
main()

Submission status: Accepted

Solution code:
from collections import deque, Counter
from functools import reduce


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

is_visit = [[False for _ in range(W)] for _ in range(H)]

next_search = deque([[0, 0, 0], ])


def get_shortest_step():
    shortest_step = -1
    while len(next_search) > 0:
        nowx, nowy, now_step = next_search.pop()
        if is_visit[nowx][nowy]:
            continue
        is_visit[nowx][nowy] = True

        for stepx, stepy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nextx = nowx + stepx
            nexty = nowy + stepy
            if nextx == H-1 and nexty == W-1:
                shortest_step = now_step + 1
                return shortest_step
            if 0 <= nextx < H and 0 <= nexty < W:
                if is_visit[nextx][nexty] or area_info[nextx][nexty] == "#":
                    continue
                next_search.appendleft([nextx, nexty, now_step+1])
    return shortest_step


shortest_step = get_shortest_step()
c = Counter("".join(area_info))
if shortest_step == -1:
    print("-1")
else:
    print(c['.'] - shortest_step - 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from queue import Queue

h,w = map(int,input().split())
black, white = 0,0
s = [[0] * w for _ in range(h)]
for i in range(h):
    s[i] = list(input())
    for j in range(w):
        if s[i][j] == ".":
            white += 1
        else:
            black += 1

def bfs():
    global ans,checked
    while not que.empty():
        xy = que.get()
        if xy[0] == w - 1 and xy[1] == h - 1:
            ans = checked[xy[1]][xy[0]]
            return
        for i in range(-1,2):
            for j in range(-1,2):
                if i == j or i == -j:
                    continue
                if 0 <= xy[0] + i < w and 0 <= xy[1] + j < h:
                    if checked[xy[1] + j][xy[0] + i] == -1 and s[xy[1] + j][xy[0] + i] == ".":
                        checked[xy[1] + j][xy[0] + i] = checked[xy[1]][xy[0]] + 1
                        que.put([xy[0] + i,xy[1] + j])

que = Queue()
ans = -1
checked = [[-1] * w for _ in range(h)]
checked[0][0] = 0
que.put([0,0])

bfs()
if ans != -1:
    print(white - ans - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
xy=[(1,0),(-1,0),(0,1),(0,-1)]
ans=chk=0
h,w=map(int,input().split())
d=[[0]*w for i in range(h)]
l=[]
for i in range(h):
    a=input()
    chk+=a.count("#")
    l.append(a)
p=set([(0,0)])
while len(p):
    a,b=p.pop()
    for y,x in xy:
        y+=a
        x+=b
        if 0<=y<h and 0<=x<w and l[y][x]!="#":
            if d[y][x]==0 or d[y][x]>d[a][b]+1:
                d[y][x]=d[a][b]+1
                p.add((y,x))

print(-1 if d[h-1][w-1]==0 else h*w-1-chk-d[h-1][w-1])

Submission status: Accepted

Solution code:
import queue

h, w = [int(i) for i in input().split(" ")]
s = ["" for i in range(0, h)]

for i in range(0, h):
    s[i] = input()

b = [[False for j in range(0, w)] for i in range(0, h)]

c = 0
for i in range(0, h):
    for j in range(0, w):
        if s[i][j] == ".":
            c += 1

q = queue.Queue()
q.put([0, 0, 0])
b[0][0] = True

def addq(i, j, d):
    global b
    global q
    if 0 <= i and i < h and 0 <= j and j < w and not b[i][j] and s[i][j] == ".":
        b[i][j] = True
        q.put([i, j, d])

f = False
while not q.empty():
    qi = q.get()
    if qi[0] == h - 1 and qi[1] == w - 1:
        f = True
        print(c - qi[2] - 1)
        break
    i = qi[0]
    j = qi[1]
    addq(i + 1, j, qi[2] + 1)
    addq(i, j + 1, qi[2] + 1)
    addq(i - 1, j, qi[2] + 1)
    addq(i, j - 1, qi[2] + 1)

if not f:
    print(-1)

Submission status: Accepted

Solution code:
import queue
h, w = map(int, input().split())
d=[(0, 1), (1, 0), (0, -1), (-1, 0)]
s=[list(input()) for i in range(h)]
m=[[-1]*w for i in range(h)]
m[0][0]=1
q = queue.Queue()
q.put((0, 0))
while not q.empty():
    p=q.get()
    for i in range(4):
        x=p[0]+d[i][0]
        y=p[1]+d[i][1]
        if 0<=x<h and 0<=y<w and m[x][y]<0 and s[x][y]=='.':
            q.put((x, y))
            m[x][y]=m[p[0]][p[1]]+1
dis=m[h-1][w-1]
c=sum(si.count('.') for si in s)
print(c-dis if dis>0 else -1)

Submission status: Accepted

Solution code:
import queue

H, W = list(map(int, input().split()))
ans = H * W
L = []
for i in range(H):
	s = list(input())
	ans -= s.count("#")
	L.append(s)

length = [[float("inf") for i in range(W)] for j in range(H)]
length[0][0] = 0

def breadth(H, W, q, L, length, goal):
	while not q.empty():
		m = q.get()
		x = m[0]
		y = m[1]
		if [x, y] == goal:
			break

		if y - 1 >= 0:
			if length[y - 1][x] > length[y][x] + 1:
				if L[y - 1][x] == ".":
					length[y - 1][x] = length[y][x] + 1
					q.put([x, y - 1])
		if y + 1 <= H - 1:
			if length[y + 1][x] > length[y][x] + 1:
				if L[y + 1][x] == ".":
					length[y + 1][x] = length[y][x] + 1
					q.put([x, y + 1])
		if x - 1 >= 0:
			if length[y][x - 1] > length[y][x] + 1:
				if L[y][x - 1] == ".":
					length[y][x - 1] = length[y][x] + 1
					q.put([x - 1, y])
		if x + 1 <= W - 1:
			if length[y][x + 1] > length[y][x] + 1:
				if L[y][x + 1] == ".":
					length[y][x + 1] = length[y][x] + 1
					q.put([x + 1, y])
	return length[-1][-1]

q = queue.Queue()
q.put([0, 0])
goal = [W - 1, H - 1]
goal_len = breadth(H, W, q, L, length, goal)

if length[H - 1][W - 1] == float("inf"):
	print(-1)
else:
	print(ans - goal_len - 1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = [int(item) for item in input().split()]
s = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]

black = 0
for line in s:
  black += line.count("#")

que = deque()
que.append([0,0])
dist[0][0] = 1
while que:
  x, y = que.popleft()
  for i, j in [(1,0), (-1,0), (0,1), (0,-1)]:
    nx = x + i
    ny = y + j
    if nx < 0 or nx >= h or ny < 0 or ny >= w:
      continue
    if s[nx][ny] == "#":
      continue
    if dist[nx][ny] == -1:
      dist[nx][ny] = dist[x][y] + 1
      que.append([nx, ny])

if dist[h-1][w-1] == -1:
  print(-1)
else:
  print(h*w - dist[h-1][w-1] - black)

Submission status: Accepted

Solution code:
def serch(x,y,p):
    if x<0 or W<=y or y<0 or H<=x or meiro[x][y] =="#":
        return
    if memo[x][y]:
        p = [x,y]
        return
    memo[x][y] = 1
    kyo[x][y] = kyo[p[0]][p[1]] + 1
    p = [x,y]
    serch(x+1,y,p)
    serch(x-1,y,p)
    serch(x,y+1,p)
    serch(x,y-1,p)
H,W = list(map(int,input().split()))
sx,sy = 0,0
gx,gy = H-1,W-1
meiro = [list(input()) for l in range(H)]
counter = 0
for a in range(H):
    for b in range(W):
        n = 1 if meiro[a][b] =="." else 0
        counter += n
dx = [1,0,-1,0]
dy = [0,1,0,-1]
stk = [(sx,sy)]

memo =[[0 for i in range(W)] for l in range(H)]
memo[sx][sy]=1
dis =[[0 for i in range(W)] for l in range(H)]
while stk:
    x,y = stk.pop(0)
    for i in range(4):
        xx,yy = x+dx[i],y+dy[i]
        if xx<0 or W<=yy or yy<0 or H<=xx or meiro[xx][yy] =="#" or memo[xx][yy]==True:
            continue
        dis[xx][yy] = dis[x][y]+1
        stk.append((xx,yy))
        memo[xx][yy] = 1
if dis[gx][gy]==0:
    print(-1)
else:
    print(counter-dis[gx][gy]-1)

Submission status: Accepted

Solution code:
from queue import Queue

H, W =  list(map(int, input().split()))
s = [input() for _ in range(H)]
 
y = "."
n = "#"

D = [[0] * W for _ in range(H)]
num = 0
for i in range(H):
  for j in range(W):
    if s[i][j] == y:
      num += 1
    else:
      D[i][j] = -1

def setWall(D, x):
  H = len(D)
  W = len(D[0]) + 2
  D = [[x] * W] + [[x] + [i for i in j] + [x] for j in D] + [[x] * W] 
  return D

D = setWall(D, -1)

D[1][1] = 1
Q = Queue()
Q.put([1, 1])
while Q.empty() != True:
  x, y = Q.get()
  t = D[x][y]
  for i in (-1, 1):
    for j in (0, 1):
      a = j * i
      b = (1 - j) * i
      if D[x + a][y + b] > t + 1 or D[x + a][y + b] == 0:
        D[x + a][y + b] = t + 1
        Q.put([x + a, y + b])

if D[H][W] == 0:
  print(-1)
else:
  print(num - D[H][W])

Submission status: Accepted

Solution code:
import queue
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
q = queue.Queue()
ma = [[0]*w for i in range(h)]
dyx = [[0,1],[0,-1],[1,0],[-1,0]]
white = 0
black = 0
for i in range(h):
    white += s[i].count(".")
black = h*w - white
q.put([0,0])
s[0][0] = "#"
flag = True
while flag:
    newq = queue.Queue()
    while not q.empty():
        y,x = q.get()
        for dy,dx in dyx:
            if 0 <= y + dy< h and 0 <= x +dx <w and s[y+dy][x+dx] != "#":
                s[y+dy][x+dx] = "#"
                newq.put([y+dy,x+dx])
                ma[y+dy][x+dx] = ma[y][x] +1
            if y+dy == h-1 and x+dx == w-1:
                flag = False
    q = newq
    if q.empty():
        break
if ma[h-1][w-1] == 0:
    print(-1)
else:print(white - ma[h-1][w-1]-1)

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  for j in range(W):
    if h[j] == ".":
      srch.append([i+1,j+1])
      num_w += 1

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
for _ in range(num_w):
  for i,j in srch[1:]:
    Cn[i][j] = min(Cn[i-1][j],Cn[i][j-1],Cn[i+1][j],Cn[i][j+1])+1

if Cn[H][W] < sys.maxsize:
  print(num_w - Cn[H][W])
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
INF = float("inf")

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

dist = [[INF]*W for i in range(H)]
dist[0][0] = 0

dxy = [(0,1),(1,0),(0,-1),(-1,0)]

q = deque([(0,0)])

while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx ,y+dy
        if nx < 0 or ny <0 or nx >=W or ny >= H:
            continue
        if grid[ny][nx] == "#":
            continue
        if dist[ny][nx] < INF:
            continue
        q.append((nx,ny))
        dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
    ans += grid[i].count(".")
if dist[H-1][W-1] == INF:
    print(-1)
else:
    print(ans-dist[H-1][W-1]-1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[0] * W for i in range(H)]
score = -1
count = 0

for i in range(H):
    count += maze[i].count('#')

que = deque([])
que.append([0, 0])

flag = False
while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for j, i in zip(dy, dx):
        ny = py + j
        nx = px + i
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if maze[ny][nx] == '#':
            continue
        if reached[ny][nx]:
            continue

        que.append([ny, nx])
        reached[ny][nx] += reached[py][px] + 1
        if ny == H-1 and nx == W-1:
            score = reached[ny][nx]
            flag = True
            break
    if flag:
        break

if flag:
    score = H * W - score - count - 1
    print(score)
else:
    print(score)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[["#"]*(w+2)]+[["#"]+list(input())+["#"]for i in range(h)]+[["#"]*(w+2)]
p=[[1,1]]
d=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]==".":
            d+=1
s[1][1]="#"
k=0
while [h,w] not in p:
    k+=1
    g=[]
    for i in range(len(p)):
        x,y=p[i][0],p[i][1]
        if s[x-1][y]==".":
            s[x-1][y]="Q"
            g.append([x-1,y])
        if s[x+1][y]==".":
            s[x+1][y]="Q"
            g.append([x+1,y])
        if s[x][y+1]==".":
            s[x][y+1]="Q"
            g.append([x,y+1])
        if s[x][y-1]==".":
            s[x][y-1]="Q"
            g.append([x,y-1])
    else:
        p=g
        if len(p)==0:
            print(-1)
            break
else:
    print(d-k-1)

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
s = [['#'] * (W+2) for i in range(H+2)]
black = 0
for h in range(H):
    S = input()
    for w in range(W):
        s[h+1][w+1] = S[w]
        if S[w] == '#':
            black += 1

dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def bfs(gh,gw):
    st = deque()
    sts = deque()
    push,pop = st.append, st.pop
    pushs,pops = sts.append, sts.pop
    cnt = 1
    push([-1,-1])
    pushs([-1,-1])
    push([1,1])
    g = 0
    while g < 1:
        t = 0
        for i in range(999999):
            now = pop()
            if now == [-1,-1]:
                push([-1,-1])
                break
            pushs(now)
        cnt += 1
        c = 0
        while t < 1:
            now = pops()
            #print(now,c)
            if now == [-1,-1]:
                if c == 0:
                    return -1
                    break
                pushs([-1,-1])
                t = 1
                break
            c = 1

            
            for dx,dy in dxy:
                if s[now[0]+dx][now[1]+dy] == '#':
                    continue
                if [now[0]+dx,now[1]+dy] == [gh,gw]:
                    g = 1
                    #print(cnt,black)
                    return H*W-black-cnt
                if s[now[0]+dx][now[1]+dy] == '.':
                    push([now[0]+dx,now[1]+dy])
                    s[now[0]+dx][now[1]+dy] = '#'

print(bfs(H,W))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from queue import Queue
h,w = map(int, input().split())
d = []
for _ in range(h):
    d.append(input())
cost = [[0]*w for _ in range(h)]

q = Queue()
q.put((0,0))
while not q.empty():
    hi,wi = q.get()
    if hi==h-1 and wi==w-1:
        break

    for dh,dw in [[0,1],[1,0],[0,-1],[-1,0]]:
        if h>dh+hi>=0 and w>dw+wi>=0 and d[dh+hi][dw+wi]==".":
            if cost[dh+hi][dw+wi]==0 or cost[dh+hi][dw+wi]>cost[hi][wi]+1:
                cost[dh+hi][dw+wi] = cost[hi][wi]+1
                q.put((dh+hi, dw+wi))

if cost[h-1][w-1]==0:
    print(-1)
    exit()

res = 0
for hi in range(h):
    for wi in range(w):
        if (hi==0 and wi==0) or (hi==h-1 and wi==-1):
            continue
        if d[hi][wi]==".":
            res += 1

print(res - cost[h-1][w-1])

Submission status: Accepted

Solution code:
import collections

H,W=map(int,input().split())
s=[]
for i in range(H):
    s.append(input())
ans=0
for i in range(H):
    ans+=s[i].count('.')

inf=1<<60
c=[[inf for j in range(W)] for i in range(H)]
c[0][0]=1

q=collections.deque()
q.append((0,0))
try:
    while True:
        y,x=q.popleft()
        if x>0 and s[y][x-1]=='.' and c[y][x-1]>c[y][x]+1:
            c[y][x-1]=c[y][x]+1
            q.append((y,x-1))
        if x<W-1 and s[y][x+1]=='.' and c[y][x+1]>c[y][x]+1:
            c[y][x+1]=c[y][x]+1
            q.append((y,x+1))
        if y>0 and s[y-1][x]=='.' and c[y-1][x]>c[y][x]+1:
            c[y-1][x]=c[y][x]+1
            q.append((y-1,x))
        if y<H-1 and s[y+1][x]=='.' and c[y+1][x]>c[y][x]+1:
            c[y+1][x]=c[y][x]+1
            q.append((y+1,x))
except IndexError:
    pass
if c[H-1][W-1]==inf:
    print(-1)
else:
    print(ans-c[H-1][W-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
##計算の都合、 通路(.)を正の整数、壁(#)を-1に変換する
LARGE_VALUE = 100000
Mij = [[0] * W for _ in range(H)]
space_count = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            space_count += 1
            Mij[i][j] = LARGE_VALUE
        else:
            Mij[i][j] = -1

dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

queue = [[0, 0]]

def search():
    while len(queue):
        p = queue[0]
        del queue[0]
        i = p[0]
        j = p[1]
        step = Mij[i][j]

        for d in dirs:
            i2 = i + d[0]
            j2 = j + d[1]
            if 0 <= i2 < H and 0 <= j2 < W:
                if step + 1 < Mij[i2][j2]:
                    Mij[i2][j2] = step + 1
                    queue.append([i2, j2])

Mij[0][0] = 1
search()
total_steps = Mij[H - 1][W - 1]
if total_steps == LARGE_VALUE:
    print(-1)
else:
    print(space_count - total_steps)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    h,w = LI()
    s = SR(h)
    white = 0
    for i in range(h):
        white += s[i].count(".")
    bfs_map = [[-1 for i in range(w)] for j in range(h)]
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    bfs_map[0][0] = 0
    q = deque()
    q.append([0,0])
    while q:
        y,x = q.popleft()
        for dy,dx in d:
            y_ = y+dy
            x_ = x+dx
            if 0 <= y_ < h and 0 <= x_ < w:
                if s[y_][x_] == "." and bfs_map[y_][x_] < 0:
                    bfs_map[y_][x_] = bfs_map[y][x]+1
                    q.append([y_,x_])
    if bfs_map[h-1][w-1] < 0:
        print(-1)
        quit()
    print(white-1-bfs_map[h-1][w-1])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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


def bfs():
    q = [(0, 0, 1)]
    m = [[0 for _ in range(W)] for _ in range(H)]
    while len(q) > 0:
        x, y, c = q.pop(0)
        for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
            if (H, W) == (yy + 1, xx + 1):
                return c + 1
            if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                    m[yy][xx] == 0:
                q.append((xx, yy, c + 1))
                m[yy][xx] = 1
    return -1


def main():
    dc = 0
    for i in range(H):
        dc += S[i].count('.')
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(dc - c)


main()