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:
from collections import deque


def bfs(maze, visited, sh, sw, gh, gw, H, W):
    queue = deque([(sh, sw)])
    visited[sh][sw] = 1

    while queue:
        h, w = queue.popleft()
        if (h, w) == (gh, gw):
            return visited[h][w]

        for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + i
            nw = w + j
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    queue.append((nh, nw))

    return -1


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

    cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == ".":
                cnt += 1

    visited = [[-1] * W for _ in range(H)]

    ans = bfs(s, visited, 0, 0, H - 1, W - 1, H, W)
    if ans == -1:
        print(ans)
    else:
        print(cnt - ans)


main()

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

H, W = list(map(int, input().split()))
s_y, s_x = 0, 0
g_y, g_x = H - 1, W - 1

visited = np.full((H, W), False)
board = np.zeros((H, W))
for i in range(H):
    row = input()
    for j, r in enumerate(row):
        if r == '.':
            board[i][j] = 1

direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
queue = deque()
queue.append(((s_y, s_x), 0))  # (pos, dist)

found = False
while len(queue) > 0:
    (y, x), dist = queue.popleft()
    if x == g_x and y == g_y:
        found = True
        break

    for dx, dy in direction:
        new_y, new_x = y + dy, x + dx
        if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
            continue
        if board[new_y][new_x] == 0:
            continue
        if visited[new_y][new_x]:
            continue
        queue.append(((new_y, new_x), dist + 1))
        visited[new_y][new_x] = True
if found:
    print(int(np.sum(board)) - (dist + 1))
else:
    print(-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
M = [list(input()) for _ in range(h)]
M = [[1 if M[i][j]=='.' else 0 for j in range(w)] for i in range(h)]

sy, sx = 0, 0
gy, gx = h-1, w-1

from collections import deque

d = deque()
d.append((sy, sx))

goal = 0
V = [[0]*w for i in range(h)]
V[sy][sx] = 1
D = [[-1]*w for i in range(h)]
D[sy][sx] = 1
while len(d):
  y_cur, x_cur = d.popleft()
  #print(y_cur, x_cur)
  if y_cur == gy and x_cur == gx:
    goal = 1
    break
  for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    y_nxt = y_cur + dy
    x_nxt = x_cur + dx
    if y_nxt>=0 and y_nxt<h and x_nxt>=0 and x_nxt<w:
      if M[y_nxt][x_nxt] == 1 and V[y_nxt][x_nxt]==0:
        V[y_nxt][x_nxt] = 1
        D[y_nxt][x_nxt] = D[y_cur][x_cur] + 1
        d.append((y_nxt, x_nxt))

if goal:
  black = h*w - sum([sum(M[i]) for i in range(h)])
  white = h*w - black
  ans = white - D[gy][gx]
  #print(black, white, D[gy][gx])
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            cnt += 1
dist = [[-1 for _ in range(W)] for _ in range(H)]
que = deque([(0,0,0)])
dist[0][0] = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and dist[i][j+1]<0 and S[i][j+1]==".":
        que.append((i,j+1,d+1))
        dist[i][j+1]=d+1
    if i-1>=0 and dist[i-1][j]<0 and S[i-1][j]==".":
        que.append((i-1,j,d+1))
        dist[i-1][j]=d+1
    if j-1>=0 and dist[i][j-1]<0 and S[i][j-1]==".":
        que.append((i,j-1,d+1))
        dist[i][j-1]=d+1
    if i+1<H and dist[i+1][j]<0 and S[i+1][j]==".":
        que.append((i+1,j,d+1))
        dist[i+1][j]=d+1
x = dist[H-1][W-1]
if x<0:
    print(-1)
else:
    print(cnt-1-x)

Submission status: Accepted

Solution code:
from collections import deque
MAX_VAL = 10 ** 9
H, W = map(int, input().split())
 
 
 
border_row = "#"*(W+2)
field = [border_row]
num_blacks = 0
for i in range(H):
    line = input()
    num_blacks += line.count(".")
    field.append("#"+line+"#")
field.append(border_row)
 
cost = [[MAX_VAL]*(W+2) for _ in range(H+2)]
 
if field[1][1] == ".":
    cost[1][1] = 1
else:
    cost[1][1] = MAX_VAL
 
visited = [[False]*(W+2) for _ in range(H+2)]
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((1, 1))
    visited[1][1] = True
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if field[ny][nx] == "." and not visited[ny][nx]:
                cost[ny][nx] = cost[y][x]+1
                visited[ny][nx] = True
                q.append((nx, ny))
    return 
bfs()
print(num_blacks - cost[H][W]) if cost[H][W] < MAX_VAL else print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    line2 = "#" + line + "#"
    num_blacks += line.count(".")
    field.append(line)

cost = [[-1]*(W) for _ in range(H)]

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    num_blacks += line.count(".")
    field.append(line)

cost = [[-1]*(W) for _ in range(H)]

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
visited_place=[[-1]*W for _ in range(H)]
visited_place[0][0]=1
stack=[[0,0]]
kazu=0
for a in S:
    kazu+=a.count('.')
def bfs(S,visited_place,stack):
    while len(stack)>0:
        h,w=stack.pop()
        for x,y,in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h=h+x
            new_w=w+y
            if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
                continue
            if S[new_h][new_w]=='.' and visited_place[new_h][new_w]==-1:
                visited_place[new_h][new_w]=visited_place[h][w]+1
                stack.insert(0,[new_h,new_w])
    return visited_place[H-1][W-1]
if bfs(S,visited_place,stack)==-1:
    print(-1)
else:
    answer=kazu-bfs(S,visited_place,stack)
    print(answer)

Submission status: Accepted

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

def f(sx, sy, gx, gy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(W)] for h in range(H)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
count = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            count += 1
ans = f(0, 0, W-1, H-1)
if ans == float('inf'):
    print(-1)
else:
    print(H*W-ans-1-count)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
S = [list(input()) for i in range(H)]
dot = 0
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "#" :
        dot += 1
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return dist[H*W-1]

dist = [-1 for _ in range(H*W)]
ans = bfs(0)
if ans == -1 :
    print(-1)
else :
    print(dot - ans - 1)

Submission status: Accepted

Solution code:
import heapq

h,w = (int(x) for x in input().split())
seq = []
white = 0
for i in range(h):
    seq.append(input())
    white += seq[-1].count('.')

MOVES = ((-1, 0), (1, 0), (0, 1), (0, -1))
visited = set()

final = (w-1, h-1)
stack = []
heapq.heappush(stack, ((0,0), 1))
ans = -1
while stack:
    state, cost = heapq.heappop(stack)
    if state == final:
        ans = white - cost
        break
    
    if state not in visited:
        x,y = state
        visited.add(state)
        for dx,dy in MOVES:
            xnew = x + dx
            ynew = y + dy
            
            if xnew >= 0 and ynew >=0 and xnew < w and ynew < h and seq[ynew][xnew] == '.':
                heapq.heappush(stack, ((xnew, ynew),cost+1))

print(ans)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.readline
from itertools import chain

H, W = map(int, input().split())
grid = [input() for _ in range(H)]
initial = sum(row.count("#") for row in grid)
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def out(y, x):
    return y < 0 or y >= H or x < 0 or x >= W

def wall(y, x):
    return grid[y][x] == "#"

def can_go(y, x, explored):
    return not (out(y, x) or wall(y, x) or (y, x) in explored)

def succs(explored):
    def succs_(point):
        y = point[0]
        x = point[1]
        return [(y+h, x+w) for h, w in dire if can_go(y+h, x+w, explored)]
    return succs_

def bfs(frontier, explored, count):
    if not frontier:
        return -1
    elif any(map(lambda point: point == (H-1, W-1), frontier)):
        return count
    else:
        frontier_ = set(chain(*map(succs(explored), frontier)))
        return bfs(frontier_, explored | frontier_, count+1)
    
def main():
    path_count = bfs([(0, 0)], set([(0, 0)]), 1)
    if path_count == -1:
        print(-1)
    else:
        print(H*W - path_count - initial)

main()

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.readline
from itertools import chain

H, W = map(int, input().split())
grid = [input() for _ in range(H)]
initial = sum(row.count("#") for row in grid)
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def out(y, x):
    return y < 0 or y >= H or x < 0 or x >= W

def wall(y, x):
    return grid[y][x] == "#"

def succs(explored):
    def succs_(point):
        y = point[0]
        x = point[1]
        return [(y+h, x+w) for h, w in dire if not (out(y+h, x+w) or wall(y+h, x+w) or (y+h, x+w) in explored)]
    return succs_

def bfs(frontier, explored, count):
    if not frontier:
        return -1

    if any(map(lambda point: point == (H-1, W-1), frontier)):
        return count
    
    frontier_ = set(chain(*map(succs(explored), frontier)))
    return bfs(frontier_, explored | frontier_, count+1)
    
def main():
    path_count = bfs([(0, 0)], set([(0, 0)]), 1)
    if path_count == -1:
        print(-1)
    else:
        print(H*W - path_count - initial)

main()

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.readline
from collections import deque

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

initial = 0
grid = []
for _ in range(H):
    row = input()
    initial += row.count("#")
    grid.append(row)

def bfs():
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    q = deque()
    q.append((0, 0, 1))
    explored = set()
    explored.add((0, 0))
    while q:
        y, x, count = q.popleft()
        for h, w in dire:
            yh = y + h
            xw = x + w
            if yh < 0 or yh >= H or xw < 0 or xw >= W or grid[yh][xw] == "#" or (yh, xw) in explored:
                continue
            
            if (yh, xw) == (H-1, W-1):
                return count+1

            explored.add((yh, xw))
            q.append((yh, xw, count+1))

    return -1

path_count = bfs()

if path_count == -1:
    print(-1)
else:
    print(H*W - path_count - initial)

Submission status: Accepted

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

    sy = 0
    sx = 0
    blk_cnt = 0

    for i in range(H):
        for j in range(W):
            if field[i][j] == '#':
                blk_cnt += 1

    
    shortest_step = bfs(H,W,field,sy,sx,H-1,W-1)
    if shortest_step == -1:
        print(-1)
    else: 
        print(H*W - blk_cnt - shortest_step)

def bfs(H,W,field,sy,sx,ty,tx):
    n_step = [[-1]*W for i in range(H)]
    n_step[sy][sx] = 1
    deq = deque()
    deq.appendleft((sy,sx))
    
    d_x_y = ((1,0),(-1,0),(0,1),(0,-1))
    while len(deq) > 0:
        cy, cx = deq.pop()
        if cy == ty and cx == tx:
            return n_step[cy][cx]

        for dy, dx in d_x_y:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and field[ny][nx] != '#' and n_step[ny][nx] == -1:
                n_step[ny][nx] = n_step[cy][cx] + 1
                deq.appendleft((ny,nx)) 
    
    return -1

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''
#import copy
h,w = map(int, input().split())
s = []
cnt=0
for i in range(h):
    t = list(input().strip())
    cnt+=t.count('.')
    s.append(t)
#print(h,w,s)
def sol(h,w,s,start):
    import queue
    #import numpy as np
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    px=start[0]
    py=start[1]
    #sco=np.array([[-1 for _ in range(w)] for x in range(h)])
    sco = [[-1 for _ in range(w)] for x in range(h)]
    sco[py][px]=0
    a=queue.Queue()
    a.put([px, py])
    #print(sco)
    while not a.empty():
        px, py = a.get()
        if px==w-1 and py==h-1:
            #print(sco)
            #print(cnt,sco[py][px])
            return cnt-sco[h-1][w-1]-1
        for i in range(4):
            nx=px+dx[i]
            ny=py+dy[i]
            #print(nx,ny)
            if 0<=nx<w and 0<=ny<h and s[ny][nx]!="#" and sco[ny][nx]==-1:
                sco[ny][nx]=sco[py][px]+1
                a.put([nx,ny])
    return -1

print(sol(h,w,s,[0,0]))

Submission status: Accepted

Solution code:
h,w = [int(i) for i in input().split()]
s = []
for i in range(h):
  array = list(input())
  s.append(array)

from collections import deque
e = [i for row in s for i in row]
chk =[]
def f():
  d = [[float('inf')]*w for i in range(h)]
  d[0][0]=1
  n = [0,0,1,-1]
  m = [1,-1,0,0]
  que = deque([])
  que.append((0,0))
  while que:
    p = que.popleft()
    if p[0]==h-1 and p[1]==w-1:
      break
    for i in range(4):
      nh = p[0]+n[i]
      nw = p[1]+m[i]
      if 0<=nh<h and 0<=nw<w and d[nh][nw]==float('inf') and s[nh][nw]!='#':
        d[nh][nw] = d[p[0]][p[1]]+1
        #print('chk')
        que.append((nh,nw))
  return  d[h-1][w-1]

res = f()
#print(res)
if res != float("inf"):
  print(h*w-res-e.count('#'))
else:
  print('-1')

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    d = [[float("INF")] * w for i in range(h)]
    d[0][0] = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    que = deque([])
    que.append((0, 0))
    
    while que:
        p = que.popleft()
        if p[0] == h - 1 and p[1] == w - 1:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("INF"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[h - 1][w - 1]
    
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            cnt += 1
if bfs() == float("INF"):
    print("-1")
else:
    print(h * w - cnt - bfs() - 1)

Submission status: Accepted

Solution code:
from collections import deque
white, black = '.', '#'
H, W = map(int, input().split())
S = [[j for j in input()] for i in range(H)]
mvv, mvh = [0, 0, -1, 1], [-1, 1, 0, 0]
q = deque([(0, 0)])
S[0][0] = 0
while q:
  y, x = q.popleft()
  for i in range(4):
    if 0 <= y + mvv[i] <= H-1 and S[y + mvv[i]][x] == white:
      S[y + mvv[i]][x] = S[y][x] + 1
      q.append((y + mvv[i], x))
    if 0 <= x + mvh[i] <= W-1 and S[y][x + mvh[i]] == white:
      S[y][x + mvh[i]] = S[y][x] + 1
      q.append((y, x + mvh[i]))
if S[H-1][W-1] == white:
  print(-1)
else:
  r = 0
  c = set()
  for y in range(H):
    for x in range(W):
      if S[y][x] == black:
        continue
      if S[y][x] == white or S[y][x] in c or S[y][x] > S[H-1][W-1]:
        r += 1
      else:
        c.add(S[y][x])
  print(r)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
count_wall = 0
for i in range(h):
    maze[i] = input()
    count_wall += maze[i].count('#')

INF = h*w
visited = [[0 for i in range(w)] for j in range(h)]
distance = [[INF for i in range(w)] for j in range(h)]

if maze[0][0]=='#':
    print(-1)
    exit()

sx=0
sy=0
queue = deque()
queue.append((sy,sx))
distance[sy][sx] = 0

while queue:
    y, x = queue.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        ny, nx = y+i, x+j
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x]+1:
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x]+1

if distance[h-1][w-1] <INF:
    ans = h*w-count_wall- (distance[h-1][w-1]+1)
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def judge(y, x, dis):
    if info[y][x] == ".":
        info[y][x] = "#"
        stack.append([y, x, dis + 1])


H, W = map(int, input().split())
info = [["#"] * (W + 2)]
for _ in range(H):
    info.append(["#"] + list(input()) + ["#"])
info.append(["#"] * (W + 2))
white = 0
for i in range(H + 2):
    for j in range(W + 2):
        if info[i][j] == ".":
            white += 1

stack = deque([[1, 1, 0]])
while len(stack) > 0:
    y, x, dis = stack.popleft()
    if y == H and x == W:
        ans = dis
        break
    judge(y + 1, x, dis)
    judge(y, x + 1, dis)
    judge(y - 1, x, dis)
    judge(y, x - 1, dis)
    if len(stack) == 0:
        print(-1)
        sys.exit()
print(white - dis - 1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
maze = ['#'*(W+2)]
for _ in range(H):
  maze.append('#'+input()+'#')
maze.append('#'*(W+2))

cost = [[-1]*(W+2) for _ in range(H+2)]
cost[1][1] = 0

que = [(1,1)]
while que:
  i,j = que.pop(0)
  if (i,j) == (H,W):
    break
  for k,l in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
    #print(maze[k][l], cost[k][l])
    if maze[k][l] == '.' and cost[k][l] == -1:
      cost[k][l] = cost[i][j] + 1
      que.append((k,l))

if cost[H][W] == -1:
  print(-1)
else:
  n = -2 # .の数数
  for i in range(1,H+1):
    for j in range(1,W+1):
      if maze[i][j] == '.':
        n += 1
  print(n - cost[H][W] + 1)

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc088/tasks/abc088_d
'''
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    h,w = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(h)]
    kuro = 0
    for i in a:
        kuro += i.count('#')
    d = deque([[0,0]])
    dxy = [[0,1],[0,-1],[1,0],[-1,0]]
    a[0][0] = 1
    while d:
        x,y = d.popleft()
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<=h-1 and 0<=ny<=w-1:
                if a[nx][ny] == '.':
                    a[nx][ny] = a[x][y] + 1
                    d.append([nx, ny])
    if a[h-1][w-1] == '.':
        print(-1)
    else:
        print(h*w - a[h-1][w-1]-kuro)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
参考にさせていただきました.ありがとうございました.(https://atcoder.jp/contests/abc088/submissions/10819295)
"""

from collections import deque

def dfs(H,W,s):
    que = deque()
    que.append([0,0])##初期地点
    distance = [[-1 for i in range(W)] for j in range(H)]##距離を記録する配列
    dxdy = [[1,0],[0,1],[-1,0],[0,-1]]##縦横の4方向

    distance[0][0] = 1##今回は進んだ歩数が欲しいので1から始める

    flag = False ##ゴール(右下)についたかどうかのフラグ

    while que:##取り出せなくなるまでループ

        x,y = que.popleft()##現在地点

        if x == H-1 and y == W-1:##ゴールに到着
            flag = True
            break

        for i,j in dxdy:##4方向を走査
            dx = x + i
            dy = y + j
            if dx >= 0 and dx < H and dy >= 0 and dy < W and distance[dx][dy] == -1 and s[dx][dy] == ".":
                distance[dx][dy] = distance[x][y] + 1 ##値の更新(+1)
                que.append([dx,dy])##forループ後に移動した点を調べる

    if not flag:
        return -1
    else:
        ans = 0
        for i in range(H):
            ans += s[i].count("#")
        ##print("#",ans)
        ##print("dist",distance[-1][-1])
        return H*W - ans - distance[-1][-1]

def main():
    H,W = map(int,input().split())
    s = []
    for i in range(H):
        s.append(input())
    print(dfs(H,W,s))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
import numpy as np

num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
seen = np.zeros((num[0],num[1]))

step_r = [1,0,-1,0]
step_c = [0,1,0,-1]
q_r = queue.Queue()
q_c = queue.Queue()
sign = 0
white = 0
q_r.put(0)
q_c.put(0)

for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == ".":
      white = white + 1

while not q_r.empty():
  r = q_r.get()
  c = q_c.get()
  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "#"):
      continue
      
    if seen[next_r][next_c] == 0:
      q_r.put(next_r)
      q_c.put(next_c)
      seen[next_r][next_c] = seen[r][c] + 1
      if (next_r == num[0]-1) and (next_c == num[1]-1):
        g_r = next_r
        g_c = next_c
        sign = 1
        break
 
  if sign == 1:
    break

if sign == 1:
  ans = white - (seen[g_r][g_c] + 1)
elif sign == 0:
  ans = -1

print(int(ans))

Submission status: Accepted

Solution code:
from collections import deque
import sys
h,w = map(lambda x: int(x),input().split())
map = []
white_count = 0
map_count = [[float('inf') for i in range(w)] for j in range(h) ]
seen = [[False for i in range(w)] for j in range(h) ]
for _ in range(h) :
    a = list(input())
    white_count += a.count('.')
    map.append(a)

map_count[0][0] = 1

q = deque()
q.append([0,0,0,0])
while q :
    v = q.popleft()
    x = v[0]
    y = v[1]
    pre_x = v[2]
    pre_y = v[3]


    if x < 0 or x >= h or y < 0 or y >= w :
        continue
    if seen[x][y] :
        continue
    if map[x][y] == '#' :
        continue
    if map_count[x][y] > map_count[pre_x][pre_y] + 1 :
        map_count[x][y] = map_count[pre_x][pre_y] + 1

    if x == h-1 and y == w-1 :
        print(white_count - map_count[x][y])
        sys.exit()

    pre_x = x
    pre_y = y
    seen[x][y] = True
    q.append([x+1,y,pre_x,pre_y])
    q.append([x-1,y,pre_x,pre_y])
    q.append([x,y+1,pre_x,pre_y])
    q.append([x,y-1,pre_x,pre_y])




print(-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '#'*(W+2)
S[H+1] = '#'*(W+2)
path_c = 0
for i in range(1,H+1):
  S[i] = '#'+input()+'#'
  path_c += S[i].count('.')
#print(S)
visited = [[False]*(W+2) for _ in range(H+2)]
import queue
q = queue.Queue()
q.put((1,1,1))
visited[1][1]=True
dh = [1,0,-1,0]
dw = [0,1,0,-1]
ans = -1
while not q.empty():
  h,w,c = q.get()
  for i in range(4):
    y,x = h+dh[i],w+dw[i]
    #print(y,x)
    if y == H and x == W:
      c += 1
      ans = path_c-c
      break
    if S[y][x]=='.' and visited[y][x]==False:
      #print(y,x,c)
      q.put((y,x,c+1))
      visited[y][x]=True
  else:
      continue
  break
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '))
table = [input() for _ in range(H)]

# BFS
dists = [[float('inf') for _ in range(W)] for _ in range(H)]
dists[0][0] = 0
nexts = [(1,0), (-1,0), (0,1), (0,-1)]

buf = [(0, 0)]
while buf:
    h, w = buf.pop(0)

    for dh, dw in nexts:
        next_h, next_w = h+dh, w+dw
        if 0 <= next_h < H and 0 <= next_w < W:
            if table[next_h][next_w] == '.':
                if dists[next_h][next_w] == float('inf'):
                    dists[next_h][next_w] = dists[h][w] + 1
                    buf.append((next_h, next_w))

num_white = 0
for row in table:
    for r in row:
        if r == '.':
            num_white += 1

# print(num_white)
if dists[H-1][W-1] == float('inf'):
        print(-1)

else:
    print(num_white - dists[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
maze = [input() for _ in range(h)]

from collections import deque

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

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

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
d[0][0] = 1

flag = False
while que:
    x, y = que.popleft()

    if x == h-1 and y == w-1:
        flag = True
        break

    for i, j in direction:
        dx, dy = x + i, y + j
        if 0<=dx<h and 0<=dy<w and d[dx][dy] == 0 and maze[dx][dy] != '#':
            d[dx][dy] = d[x][y] + 1
            que.append((dx, dy))

if flag == False:
    print(-1)
    exit()

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

res += d[-1][-1]


print(h*w - res)

Submission status: Accepted

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

M = [str(input()) for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if M[i][j] == '.':
            ans += 1

M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

from collections import deque
q = deque()
q.append((1, 1))
visit = [[-1]*(w+2) for _ in range(h+2)]
visit[1][1] = 0

while q:
    y, x = q.popleft()
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y+dy, x+dx
        if visit[ny][nx] == -1 and M[ny][nx] != '#':
            visit[ny][nx] = visit[y][x]+1
            q.append((ny, nx))

if visit[h][w] == -1:
    print(-1)
else:
    ans = ans -visit[h][w]-1
    print(ans)

Submission status: Accepted

Solution code:
import collections
H, W = map(int, input().split())
l = [input() for _ in range(H)]
check = [([0] * (W)) for _ in range(H)]
white = 0
for i in range(H):
    white += l[i].count(".")
q = collections.deque()
check[0][0] = 1
q.append([0, 0])
g = False
while q:
    h, w = q.popleft()
    for i, j in ([0, 1], [0, -1], [1, 0], [-1, 0]):
        new_h = h + i
        new_w = w + j
        if new_w < 0 or new_h < 0 or new_w > W-1 or new_h > H-1 or l[new_h][new_w] == "#":
            continue
        elif check[new_h][new_w] == 0:
            check[new_h][new_w] = check[h][w] + 1
            q.append([new_h, new_w])
print(white - check[H-1][W-1] if check[H-1][W-1] != 0 else -1)