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
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
black_cells = 0
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            black_cells += 1

dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
que = deque()
que.append((0, 0))
flag = False

while len(que) > 0:
    now_y, now_x = que.popleft()
    now_dist = dist[now_y][now_x]
    for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1 and C[next_y][next_x] != '#':
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_dist + 1
        if dist[h - 1][w - 1] != -1:
            flag = True
            break
    if flag:
        break

if flag:
    print(h * w - black_cells - dist[h - 1][w - 1] - 1)  # 全体のマス - 最初から黒い地点 - 最短経路 - スタート地点（ゴールは最短経路に含まれている）
else:
    print('-1')

Submission status: Accepted

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

Ss = []
white_count = 0
for i in range(H):
    s = list(input())
    for masu in s:
        if masu == '.':
            white_count += 1
    Ss.append(s)

# print('white_count', white_count)


def search():
    global Ss_hosu
    #global min_hosu
    Ss_hosu[0][0] = 1
    que = [[0, 0]]
    while len(que) > 0:
        x, y = que.pop(0)
        my_value = Ss_hosu[y][x]
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            if 0 <= x + dx <= W - 1 and 0 <= y + dy <= H - 1:
                if Ss[y + dy][x + dx] == '.' and Ss_hosu[y + dy][x + dx] is None:
                    Ss_hosu[y+dy][x+dx] = my_value + 1
                    que.append([x + dx, y + dy])

  
Ss_hosu = [[None for _ in range(W)] for _ in range(H)]
search()
min_hosu = Ss_hosu[H-1][W-1]

# for s in Ss_hosu:
#     print(s)

# print('min_hosu', min_hosu)

if min_hosu is None:
    print(-1)
else:
    print(white_count - min_hosu)

Submission status: Accepted

Solution code:
from collections import deque
def bfs():
  d=[[float("inf")]*m for _ in range(n)]
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  
  que=deque([])
  que.append((0,0))
  d[0][0]=0

  while que:
    p = que.popleft()
    if p[0]==n-1 and p[1]==m-1:
      break
    for i in range(4):
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
      if 0 <= nx < n and 0 <= ny < m and c[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
  return d[n-1][m-1]

n, m = map(int, input().split())
c = [list(input()) for i in range(n)]

count=0
for i in range(n):
  for j in range(m):
    if c[i][j]=="#":
      count+=1
g=bfs()
if 0<g<float("inf"):
  print(n*m-g-1-count)
else:
  print(-1)

Submission status: Accepted

Solution code:
import queue
h, w = list(map(int, input().split()))
s = [[' ']*(w+1) for i in range(h+1)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            cnt += 1
def bfs():
    d =[[10**10]*(w) for i in range(h)]

    que = queue.Queue()

    que.put([0, 0])
    d[0][0] = 0

    while not que.empty():
        p = que.get()
        if p[0] == h and p[1] == w:
            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 s[nx][ny] != '#' and d[nx][ny] == 10**10:
                que.put([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[h-1][w-1]

print(cnt - bfs() - 1) if bfs() != 10**10 else print(-1)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

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

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def distance(i,j):
    not_visit = [[-1]*W for i in range(H)]
    not_visit[i][j] = 0
    stack = [(i,j)]

    while stack != []:
        y,x = stack.pop(0)
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and S[y+dy[i]][x+dx[i]] != "#" and not_visit[y+dy[i]][x+dx[i]] == -1:
                not_visit[y+dy[i]][x+dx[i]] =  not_visit[y][x] + 1
                stack.append((y+dy[i],x+dx[i]))
                if x+dx[i] == W-1 and y+dy[i] ==H-1:
                    break

    return not_visit[H-1][W-1]+1

if distance(0,0) != 0:
    print(c - distance(0,0))
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

H, W = map(int, input().split())
grid = [[s for s in input()] for _ in range(H)]
done =[[True] * W for _ in range(H)]
done[0][0] = 0
d = [[-1] * W for _ in range(H)]
d[0][0] = 0
q = deque([(0, 0)])

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

while q:
    x, y = q.popleft()
    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        x_n, y_n = x + i, y + j
        if (0 <= x_n and x_n <= H - 1 and 0 <= y_n and y_n <= W - 1
        and grid[x_n][y_n] == "." and done[x_n][y_n] is True):
            d[x_n][y_n] = d[x][y] + 1
            done[x_n][y_n] = 0
            q.append((x_n, y_n))

if d[H - 1][W - 1] != -1:
    print(cnt - d[H - 1][W - 1] - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

class Pos:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return 'Pos(' + str(self.x) + ', ' + str(self.y) + ')'
    
    def __add__(self, other):
        return Pos(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Pos(self.x - other.x, self.y - other.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __ne__(self, other):
        return not(self.x == other.x and self.y == other.y)

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

# もともとの黒マスの数を調べる
count = 0
for y in range(H):
    for x in range(W):
        count += 1 if s[y][x] == '#' else 0

# 訪問済みリスト
visited = [[-1 for _ in range(W)] for _ in range(H)]

# 訪問予定リスト
d = deque()

visited[0][0] = 0
d.appendleft(Pos(0, 0))

while d:
    now = d.pop()
    nexts = [now+Pos(0, 1), now+Pos(0, -1), now+Pos(1, 0), now+Pos(-1, 0)]
    for next in nexts:
        x, y = next.x, next.y
        if 0 <= x < W and 0 <= y < H:
            if s[y][x] == '.' and visited[y][x] == -1:
                visited[y][x] = visited[now.y][now.x] + 1
                d.appendleft(next)

if visited[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W-(visited[H-1][W-1]+1)-count)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
G = []
for i in range(h):
  g = list(input())
  G.append(g)
  
que = deque()
dist = [[-1]*w for _ in range(h)]

sx, sy = 0, 0
gx, gy = w-1, h-1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

dist[0][0] = 0
que.append([sx,sy])

while que:
  x, y = que.popleft()
  
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    
    if nx<0 or nx>=w or ny<0 or ny>=h or G[ny][nx]=='#':
      continue

    if dist[ny][nx]==-1:
      que.append([nx, ny])
      dist[ny][nx] = dist[y][x] +1
      
bk = 0
for i in range(h):
  for j in range(w):
    if G[i][j] == '#':
      bk += 1
      

if dist[gy][gx]==-1:
  print(-1)
else:
  print(h*w - bk - dist[gy][gx]-1)

Submission status: Accepted

Solution code:
from collections import deque

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

#右上左下
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

n_black = 0

for i in range(H):
    n_black += field[i].count("#")


dist = [[-1 for x in range(W)] for y in range(H)]
dist[0][0] = 1

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



while len(que):
    n = que.popleft()
    ny = n[0]
    nx = n[1]

    for i in range(4):
        nny = ny + dy[i]
        nnx = nx + dx[i]

        if nny >= 0 and nny < H and nnx >= 0 and nnx < W and field[nny][nnx] == "." and dist[nny][nnx] == -1:
            dist[nny][nnx] = dist[ny][nx] + 1
            que.append((nny, nnx))

min = dist[H-1][W-1]

if min == -1:
    print(-1)

else:
    print(H * W - min - n_black)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(maze, H, W, sh, sw, gh, gw):
    visited = [[-1] * W for _ in range(H)]
    visited[sh][sw] = 0

    q = deque([(sh, sw)])

    while q:
        h, w = q.popleft()

        if h == gh and w == gw:
            return visited[gh][gw]

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

    return -1


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    white = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                white += 1

    dist = bfs(S, H, W, 0, 0, H - 1, W - 1)
    if dist == -1:
        print(-1)
        return

    ans = white - (dist + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict
import heapq


def resolve():
    n_rows, n_cols = map(int, sys.stdin.readline().strip().split())
    matrix = [[]] * n_rows
    n_whites = 0
    for i in range(n_rows):
        row = list(sys.stdin.readline().strip())
        for c in row:
            if c == '.':
                n_whites += 1
        matrix[i] = row

    shortest_path = 1
    queue = deque()
    queue.append((0, 0))
    found = True
    while queue:
        shortest_path += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            nexts = (
                (x+1, y),
                (x-1, y),
                (x, y+1),
                (x, y-1),
            )
            for nx, ny in nexts:
                if (nx, ny) == (n_rows-1, n_cols-1):
                    break
                if 0 <= nx < n_rows and 0 <= ny < n_cols and matrix[nx][ny] == '.':
                    matrix[nx][ny] = '#'
                    queue.append((nx, ny))
            else:
                continue
            break
        else:
            continue
        break
    else:
        found = False

    if found:
        print(n_whites - shortest_path)
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
dirc = ((1, 0), (0, 1), (-1, 0), (0, -1))
H, W = map(int, input().split())
maze = [list(str(input())) for _ in range(H)]
white = 0
for h in range(H):
    for w in range(W):
        if maze[h][w]=='.':
            white += 1
queue = deque()
queue.appendleft((0, (0, 0)))
checked = [[0]*W for _ in range(H)]
ans = 0
while queue:
    c, (y, x) = queue.pop()
    c += 1
    if checked[y][x]:
        continue
    checked[y][x] = 1
    if (y, x)==(H-1, W-1):
        ans = c
        break
    for i, (dy, dx) in enumerate(dirc):
        ny, nx = y+dy, x+dx
        if nx<0 or nx>=W or ny<0 or ny>=H:
            continue
        if maze[ny][nx]=='#':
            continue
        if not checked[ny][nx]:
            queue.appendleft((c, (ny, nx)))
if ans==0:
    print(-1)
else:
    print(white-ans)

Submission status: Accepted

Solution code:
from collections import deque

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

s = ['1'*(W+2)]
cntw = 0

for i in range(H):
    a = input()
    a = a.replace('.', '0').replace('#', '1')
    cntw += a.count('0')
    s.append('1'+a+'1')
s.append('1'*(W+2))

visited = [[0] * (W+2) for _ in range(H+2)]
visited[1][1] = 1
temp = deque([[1, 1, 0]])
ans = 0

while temp:
    p = temp.popleft()
    if p[0:2] == [H, W]:
        ans= p[2]
        break
    else:
        for k in [[1, 0], [-1, 0], [0, 1],[0, -1]]:
            if s[p[0]+k[0]][p[1]+k[1]] == '0' and visited[p[0]+k[0]][p[1]+k[1]] == 0:
                temp.append([p[0]+k[0], p[1]+k[1], p[2]+1])
                visited[p[0]+k[0]][p[1]+k[1]] = 1
    
print(cntw- (ans + 1) if ans!=0 else -1)

Submission status: Accepted

Solution code:
from collections import  deque

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

def bfs():
    d =  [[float('inf')] * W for _ in range(H)]
    dx = [1,0,-1,0]
    dy= [0,1,0,-1]
    que=deque([])
    que.append((sx,sy))
    d[sx][sy] =  0
    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            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'):
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.append((nx, ny))
    return d[gx][gy]
    

sx, sy = 0, 0
gx, gy = H - 1,  W - 1

white = 0
for t in maze:
    for s in t:
        if  s == '.':
            white += 1
            
res = bfs()
if 0 < res < float('inf'):
    print(white - res - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
G=[]
white=0
for _ in range(h):
    s=input()
    white+=s.count('.')
    G.append(s)

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

from collections import  deque
que=deque([(0,0,1)])

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

while len(que)>0:
    ni,nj,c=que.popleft()
    for di,dj in move:
        mi,mj=ni+di,nj+dj
        if 0<=mi<h and 0<=mj<w and G[mi][mj]=='.' and vis[mi][mj]==0:
            vis[mi][mj]=c+1
            que.append((mi,mj,c+1))

print(white-vis[-1][-1]) if vis[-1][-1]!=0 else print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000)
a,b=map(int,input().split())
List=[]
sumup=0
for i in range(a):
  l=list(input())
  p=l.count(".")
  sumup+=p
  List.append(l)
List[0][0]=1
q=deque([[0,0]])
while q:
  h,w=q.popleft()
  aaa=[[0,1],[0,-1],[1,0],[-1,0]]
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
if List[a-1][b-1]==".":
  print(-1)
else:  
  print(sumup-List[a-1][b-1])

Submission status: Accepted

Solution code:
from collections import deque
import pprint
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
d=deque()
dp=[[float("inf") for _ in range(W)] for _ in range(H)]
dp[0][0]=1
d.append([0,0])
seen=[[0 for _ in range(W)] for _ in range(H)]
seen[0][0]=1
blnum=0
for i in range(H):
    for j in range(W):
        if table[i][j]=="#":
            blnum=blnum+1
while len(d)!=0:
    v=d.popleft()
    x=v[0]
    y=v[1]
    if x!=0:
        if (table[x-1][y]==".")and(seen[x-1][y]==0):
            d.append([x-1,y])
            seen[x-1][y]=1
            dp[x-1][y]=min(dp[x-1][y],dp[x][y]+1)
    if x!=H-1:
        if (table[x+1][y]==".")and(seen[x+1][y]==0):
            d.append([x+1,y])
            seen[x+1][y]=1
            dp[x + 1][y] = min(dp[x + 1][y], dp[x][y] + 1)
    if y!=0:
        if (table[x][y-1]==".")and(seen[x][y-1]==0):
            d.append([x,y-1])
            seen[x][y-1]=1
            dp[x][y-1]=min(dp[x][y-1],dp[x][y]+1)
    if y!=W-1:
        if (table[x][y+1]==".")and(seen[x][y+1]==0):
            d.append([x,y+1])
            seen[x][y+1]=1
            dp[x][y+1]=min(dp[x][y+1],dp[x][y]+1)
    #pprint.pprint(dp)
    #print(d)
    #input()
if dp[H-1][W-1]==float("inf"):
    print("-1")
else:
    print(H*W-dp[H-1][W-1]-blnum)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  # row = list(input())
  row = readline().rstrip()
  blocks += row.count("#")
  matrix.append(row)

q = deque([(0,0,0)])
min_step = -1
# visited = []
visited = [ [False]*W for _ in range(H) ]
visited[0][0] = True

while q:
  r,c,step = q.popleft()
  # visited.append((r,c))
  # visited[r][c] = True

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc] or (nr,nc,step+1) in q: continue
    # if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    visited[r][c] = True
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
from collections import deque

H,W = list(map(int, input().rstrip().split()))
S_list = [list(input().rstrip()) for i in range(H)]
#-----

def checkRoute(matrix):
    # queue = [ ( (row, column),step ) ]
    # deque = [ ( (int, int   ),int ) ]
    queue = deque([  ( (1,1),1 )  ])

    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = set()
    
    while queue:
        (r,c),step = queue.popleft()
        
        for d in delta:
            next_r = r + d[0]
            next_c = c + d[1]
            
            if (next_r == H) and (next_c == W):
                return step+1
            
            if (1 <= next_r <= H) and (1 <= next_c <= W) and \
               (next_r, next_c) not in visited  and \
               matrix[next_r][next_c] == ".":
            
                queue.append( ( (next_r, next_c), step+1 ) )
                visited.add( (next_r, next_c) )

    return -1

#-----
# add dummy node(Black area) around the original data
for i in range(len(S_list)):
    S_list[i] = ["#"] + S_list[i][:] + ["#"]
    
S_list = [["#"]*(W+2)] + S_list[:] + [["#"]*(W+2)]
#-----

cnt_dic = Counter( sum(S_list,[]) )
min_step = checkRoute(S_list)

if min_step != -1:
    print( cnt_dic["."] - min_step )
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def abc088_d():
    # 入力受け取り、周辺埋めパディング
    H, W = map(int, readline().split())
    grid = [['#'] * (W+2)]
    for ln in read().split():
        grid.append(['#'] + [c for c in ln.decode('UTF-8')] + ['#'])
    else:
        grid.append(['#'] * (W+2))

    # BFSで最短距離を求める
    from collections import deque
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[1][1] = 0  # 初期化：パディングあるので(1,1)スタート
    que = deque([(1,1)])
    while que:
        # キューから取り出す
        r, c = que.popleft()
        # 上下左右を処理する
        for i, j in ((r-1, c), (r, c-1), (r, c+1), (r+1, c)):
            if grid[i][j] == '#': continue  # 壁
            if dist[i][j] != -1: continue  # 到達済み
            dist[i][j] = dist[r][c] + 1
            que.append((i,j))

    # 最短経路(距離+1)の個数分は残す、それ以外は黒マスに変えてよい
    if dist[H][W] == -1:
        ans = -1  # ゴールに到達できていない
    else:
        ans = sum([row.count('.') for row in grid])
        ans -= 1 + dist[H][W]
    print(ans)

abc088_d()

Submission status: Accepted

Solution code:
from _collections import deque
H, W = map(int, input().split())
maze = []
wall = 0
for i in range(H):
    s = input()
    maze.append(s)
    wall += s.count('#')

queue = deque()
queue.append([0,0])
steps = [[-1]*W for _ in range(H)]
steps[0][0] = 0
while queue:
    now = queue.popleft()
    #print("now=" + str(now))

    UDLR = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    for direction in UDLR:
        goto_y = now[0] + direction[0]
        goto_x = now[1] + direction[1]
        if (goto_x - 0)*(W-1 - goto_x) < 0 or (goto_y - 0)*(H-1 - goto_y) < 0:
            continue
        if maze[goto_y][goto_x] == '#' or steps[goto_y][goto_x] >= 0:
            continue

        queue.append([goto_y, goto_x])
        steps[goto_y][goto_x] = steps[now[0]][now[1]] + 1

#print("\n".join(map(str, steps)))
if steps[H-1][W-1] == -1:
    print(-1)
    exit()

print(H*W - wall - steps[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())

grid = [list(input()) for _ in range(h)]
visited = [[False] * w for _ in range(h)]

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

que = deque()
que.append((sx, sy))
visited[sy][sx] = 1
while que:
    cx, cy = que.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = cx + dx, cy + dy
        if (0 <= nx < w) and (0 <= ny < h) and (visited[ny][nx] is False) and (grid[ny][nx] == '.'):
            if ny == gy and nx == gy:
                visited[ny][nx] = visited[cy][cx] + 1
                break
            else:
                visited[ny][nx] = visited[cy][cx] + 1
                que.append((nx, ny))

if visited[gy][gx] is False:
    print(-1)
else:
    cnt = 0
    for y in range(h):
        for x in range(w):
            if grid[y][x] == "#":
                cnt += 1
    print(h * w - visited[gy][gx] - cnt)

Submission status: Accepted

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

K = [[0,0,0]]
P = deque(K)
dp = [[10**6]*W for _ in range(H)]
used = [[0]*W for _ in range(H)]
move = [(-1,0),(0,-1),(1,0),(0,1)]

while(len(P)>0):
    b = P.popleft()
    h = b[0]
    w = b[1]
    c = b[2]
    if c < dp[H-1][W-1]:
        for i,j in move:
            if h+i >= 0 and h+i <= H-1:
                if w+j >= 0 and w+j <= W-1:
                    if T[h+i][w+j] == ".":
                        dp[h+i][w+j] = min(c+1,dp[h+i][w+j])
                        if used[h+i][w+j] == 0:
                            used[h+i][w+j] = 1
                            P.append([h+i,w+j,c+1])

ans = 0
for i in range(H):
    for j in range(W):
        if T[i][j] == ".":
            ans += 1
if dp[H-1][W-1] == 10**6:
    print(-1)
else:
    print(ans-dp[H-1][W-1]-1)

Submission status: Accepted

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

def solve():
    import sys
    from collections import deque

    H, W = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        grid.append(list(sys.stdin.readline().rstrip()))

    # 白いマスを数える
    ans = 0
    for h in range(H):
        for w in range(W):
            ans += 1 if grid[h][w]=="." else 0

    # BFSで最短路を求める
    dist = [[float("inf") for _ in range(W)] for __ in range(H)]
    dist[0][0] = 1
    que = deque([(0,0)])
    while que:
        h, w = que.popleft()
        if grid[h][w] == "x": continue
        grid[h][w] = "x"

        for nh, nw in ((h-1,w), (h+1,w), (h,w-1), (h,w+1)):
            if nh==-1 or nh==H or nw==-1 or nw==W: continue
            if grid[nh][nw] != ".": continue
            dist[nh][nw] = dist[h][w] + 1
            que.append((nh, nw))

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from pprint import pprint
from collections import deque

def bfs(sy,sx):
    que = deque()
    que.append([sy,sx])
    checked_map = [[-1]*w for _ in range(h)]
    checked_map[sy][sx] = 0

    dyx = [[1,0],[-1,0],[0,1],[0,-1]]

    while que:
        y,x = que.popleft()
        if y == gy and x == gx:
            return checked_map[gy][gx]
        for d in dyx:
            ny = y + d[0]
            nx = x + d[1]
            #正常に進むパターン
            if 0 <= ny <= h-1 and 0 <= nx <= w-1 and s[ny][nx] == "." and (checked_map[ny][nx] == -1 or checked_map[ny][nx] -1 > checked_map[y][x]):
                checked_map[ny][nx] = checked_map[y][x] + 1
                que.append([ny,nx])
            else:
                continue
    #gy,gxにたどり着けない場合は、queが空になってwhile queが終了する。
    else:
        return -1





h,w = map(int,input ().split())

s = [list(input()) for _ in range(h)]


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

flg = bfs(sy,sx)

if flg == -1:
    print(-1)
    exit()
else:
    counter = 0
    for line in s:
        counter += line.count(".")
    #全部の白の数から最短経路を引いた値が黒に変更できる数である。ただしスタート地点の分もカウントするためマイナス１する。
    result = counter - flg - 1
    #print(counter)
    #print(flg)
    print(result)

Submission status: Accepted

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

dist = [[0 for _ in range(W)] for _ in range(H)]

que = [[0, 0]]
distance = 0
while len(que) > 0:
    h, w = que.pop(0)
    if h == H - 1 and w == W - 1:
        distance = dist[h][w]
        break
    for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        ht, wt = h + a, w + b
        if 0 <= ht < H and 0 <= wt < W and graph[ht][wt] == "." and dist[ht][wt] == 0:
            dist[ht][wt] = dist[h][w] + 1
            que.append([ht, wt])

if distance == 0:
    print(-1)
    exit()

total = W * H - 1
for g in graph:
    total -= g.count("#")
print(total - distance)

Submission status: Accepted

Solution code:
# D - Grid Repainting

from collections import deque

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

kuro = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if maze[i][j] == '#':
            kuro += 1

dist = [[0] * (W+2) for _ in range(H+2)]
q = deque()
q.append((1,1))
dist[1][1] = 1
siro = -1
while len(q) > 0:
    y, x = q.popleft()
    if (y, x) == (H, W):
        siro = dist[y][x]
        break
    for vy, vx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        ny = y + vy
        nx = x + vx
        if maze[ny][nx] == '.' and dist[ny][nx] == 0:
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))

if siro == -1:
    print(siro)
else:
    print(H*W - kuro - siro)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque
INF = 10 ** 4
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [readline().rstrip() for _ in range(H)]
    maze = [[INF] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([(0, 0)])
    flg = True
    while que and flg:
        h, w = que.popleft()
        for dh, dw in directions:
            if 0 <= h+dh < H and 0 <= w+dw < W:
                if mat[h+dh][w+dw] == '.' and maze[h+dh][w+dw] > maze[h][w] + 1:
                    maze[h+dh][w+dw] = maze[h][w] + 1
                    que.append((h+dh, w+dw))
                if h+dh == H-1 and w+dw == W-1:
                    flg = False

    if maze[H-1][W-1] == INF:
        print(-1)
    else:
        cnt_b = sum([l.count('#') for l in mat])
        print(H * W - cnt_b - (maze[H-1][W-1] + 1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

row, col = map(int, input().split())
graph = [input() for i in range(row)]

count = 0
for i in range(row):
  for j in range(col):
    if graph[i][j] == ".":
      count += 1
      
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


distance = [[-1]*col for _ in range(row)]
queue = deque([])
distance[0][0] = 0
queue.appendleft([0, 0])

while len(queue) > 0:
  v = queue.popleft() 

  for j in range(4):
    next_y, next_x = v[0]+dy[j], v[1]+dx[j]
    if not 0 <= next_y < row or not 0 <= next_x < col:
      continue
    if distance[next_y][next_x] != -1 or graph[next_y][next_x] == '#':
      continue 

    distance[next_y][next_x] = distance[v[0]][v[1]] + 1
    queue.append([next_y, next_x])
      
if distance[row-1][col-1] == -1:
  print(-1)
else:
  ans = count - distance[row-1][col-1] - 1
  print(ans)

Submission status: Accepted

Solution code:
import queue
h, w = map(int,input().split())
s = ["#"*(w+2) for i in range(h+2)]
for i in range(1,h+1):
    s[i] = "#"+str(input())+"#"

d = [[-1 for i in range(w+2)] for j in range(h+2)]
d[1][1] = 1
q = queue.Queue()
q.put([1,1])

while not q.empty():
    i = q.get()
    r = d[i[0]][i[1]]
    if d[i[0]+1][i[1]] == -1 and s[i[0]+1][i[1]] == ".":
        d[i[0]+1][i[1]] = r+1
        q.put([i[0]+1,i[1]])
    if d[i[0]-1][i[1]] == -1 and s[i[0]-1][i[1]] == ".":
        d[i[0]-1][i[1]] = r+1
        q.put([i[0]-1,i[1]])
    if d[i[0]][i[1]+1] == -1 and s[i[0]][i[1]+1] == ".":
        d[i[0]][i[1]+1] = r+1
        q.put([i[0],i[1]+1])
    if d[i[0]][i[1]-1] == -1 and s[i[0]][i[1]-1] == ".":
        d[i[0]][i[1]-1] = r+1
        q.put([i[0],i[1]-1])

if d[h][w] == -1:
    print(-1)
else:
    num = 0
    for i in range(h+2):
        for j in range(w+2):
            if s[i][j] == ".":
                num += 1
    print(num-d[h][w])