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

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start,end):
    tansaku = deque()
    tansaku.append(start)
    visited = {i:set() for i in range(h)}
    kyori = [[0]*w for _ in range(h)]
    while tansaku:
        pre_y,pre_x = tansaku.popleft()
        if pre_x in visited[pre_y]:
            continue
        for i in range(pre_x-1,pre_x+2,2):
            if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                tansaku.append([pre_y,i])
                kyori[pre_y][i] = kyori[pre_y][pre_x] + 1
        for j in range(pre_y-1,pre_y+2,2):
            if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                tansaku.append([j,pre_x])
                kyori[j][pre_x] = kyori[pre_y][pre_x] + 1
        visited[pre_y].add(pre_x)
        if [pre_y,pre_x] == end:
            return kyori[pre_y][pre_x]
    return -1



h,w = nm()
white = 0
tizu = []
for i in range(h):
    temp = list(input())
    white += temp.count('.')
    tizu.append(temp)
res = bfs([0,0],[h-1,w-1])
if res == -1:
    print(res)
else:
    print(white-(res+1))

Submission status: Accepted

Solution code:
from collections import deque
def main():
    H, W = list(map(int, input().split()))
    A = [['#'] * (W + 2)] + [['#', ] + list(input()) + ['#', ] for _ in range(H)] + [['#'] * (W + 2)]
    printl = lambda l: [print(x) for x in l]
    stack = deque([[1, 1], ])
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    INF = float('inf')
    L = [[INF] * W for _ in range(H)]
    visited = [[0] * W for _ in range(H)]
    L[0][0] = 1
    while stack:
        x, y = stack.popleft()
        if visited[x - 1][y - 1] == 1:
            continue
        visited[x - 1][y - 1] = 1
        for (dx, dy) in dxy:
            X = x + dx
            Y = y + dy
            if A[X][Y] == '#':
                continue
            if visited[X - 1][Y - 1] == 0:
                stack.append([X, Y])
            L[X - 1][Y - 1] = min(L[X - 1][Y - 1], L[x - 1][y - 1] + 1)
    ans = 0
    for a in A:
        for i in a:
            if i == '.':
                ans += 1
    if L[H - 1][W - 1] == INF:
        print(-1)
    else:
        print(ans - L[H - 1][W - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W = map(int,readline().split())
grid = ['#']*(W+2)
for _ in range(H):
  grid += ['#'] + list(map(str,readline().decode().rstrip())) + ['X']
grid += ['#']*(W+2)
 
dist = [-1]*((H+2)*(W+2)-1)
 
s = W + 3
g = (H+1)*(W+2)-2
 
def bfs():
  while q:
    x = q.popleft()
    if x == g:
      return
    for dx in (1,W+2,-1,-W-2):
      if dist[x+dx] == -1 and grid[x+dx] =='.':
        dist[x+dx] = dist[x]+1
        q.append(x+dx)

dist[s]=0
q = deque([(s)])
bfs()

if dist[g] ==-1:
  print(-1)
else:
  print(grid.count('.')-dist[g]-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
def bfs():
    d=[[float("inf")]*w for i in range(h)]
    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]==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 s[nx][ny]!="#" and d[nx][ny]==float("inf"):
                d[nx][ny]=d[p[0]][p[1]]+1
                que.append((nx,ny))
    return d[h-1][w-1]
ans=h*w
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            ans-=1
if 0<bfs()<float("inf"):
    print(ans-bfs()-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
d = [input() for i in range(h)]
count = 0
for i in range(h):
    for j in range(w):
        if d[i][j] == '#':
            count+=1
visited = [[0 for i in range(w)] for i in range(h)]
def bfs(sy,sx,gy,gx):
    que = deque()
    que.append((sy,sx))
    visited[sy][sx] = 0
    while que:
        y,x = que.popleft()
        if y == gy and x == gx:
            return visited[y][x]
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if ny < 0 or nx < 0 or ny >= h or nx >= w:
                continue
            elif d[ny][nx] == '#':
                continue
            elif visited[ny][nx] != 0:
                continue
            else:
                visited[ny][nx] = visited[y][x] + 1
                que.append((ny,nx))
    return visited[gy][gx]
ans = bfs(0,0,h-1,w-1)
if ans == 0:
    print(-1)
    exit()
print(h*w - ans - count - 1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]

from collections import deque
d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((0,0))
d[0][0]=1

while queue:
    y,x=queue.popleft()
    for d_y, d_x in zip(dx,dy):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
            d[new_y][new_x]=d[y][x]+1
            queue.append((new_y, new_x))

ans=0
black=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            black+=1

print(h*w-black-d[h-1][w-1] if d[h-1][w-1]!=-1 else -1)

Submission status: Accepted

Solution code:
from collections import deque

R,C=list(map(int,input().split()))
ans=[[0 for _ in range(C+2)] for _ in range(R+2)]
wall,flag = 0,False

maze=[['#']*(C+2)]+[list("#"+input()+"#") for _ in range(R)]+[['#']*(C+2)]

for i in range(R+2):
  wall += maze[i].count('#')
wall = wall - ((R+2)*(C+2)-R*C)

vector=[(1,0),(0,1),(-1,0),(0,-1)]
road=deque()
road.append([1,1])

while road:
  ny,nx=road.popleft()
  for i,j in vector:
    my,mx=ny+i,nx+j
    if not ans[my][mx] and maze[my][mx] == ".":
      ans[my][mx] = ans[ny][nx]+1
      road.append([my,mx])
      if my == R and mx == C:
        root=ans[my][mx]+1
        print(R*C-wall-root)
        exit()
        
if not flag:
  print("-1")

Submission status: Accepted

Solution code:
# ABC088D

import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W=map(int,input().split())
    mas=[input() for i in range(H)]
    dist=[[-1]*W for i in range(H)]
    sharps=0
    for row in mas:
        sharps+=row.count("#")
    qu=deque([(0,0)])
    dist[0][0]=1
    d=((-1,0),(1,0),(0,-1),(0,1))
    qup=qu.popleft
    qua=qu.append
    while(len(qu)>0):
        v=qup()
        for di in d:
            nv=(v[0]+di[0],v[1]+di[1])
            if not(0<=nv[0]<H) or not(0<=nv[1]<W) or mas[nv[0]][nv[1]]=="#" or dist[nv[0]][nv[1]]!=-1:
                continue
            else:
                dist[nv[0]][nv[1]]=dist[v[0]][v[1]]+1
                qua(nv)
    ms=dist[H-1][W-1]
    if ms==-1:
        print(ms)
    else:
        print(H*W-sharps-ms)
    
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

INF = float('inf')
H, W = map(int, input().split())
grid = [str(input()) for _ in range(H)]
d = [[-1] * W for _ in range(H)]
d[0][0] = 0
dh = [1, -1, 0, 0]
dw = [0, 0, 1, -1]
q = deque([[0, 0]])
while q:
    h, w = q.popleft()
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if 0 <= nh < H and 0 <= nw < W and d[nh][nw] < 0:
            if grid[nh][nw] == '#':
                d[nh][nw] = INF
            else:
                d[nh][nw] = d[h][w] + 1
                q.append([nh, nw])
if d[H-1][W-1] == -1:
    print(-1)
else:
    cnt = 0
    for i in range(H):
        cnt += grid[i].count('.')
    print(cnt - d[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
def main():
    h, w = map(int, input().split())
    maze = {}
    white_cell = 0  # 白いマスの数
    for i1 in range(h):
        mazerow = input()
        for i2 in range(w):
            if mazerow[i2] == '.':
                maze[(i1, i2)] = 0  # 白います。通れる。
                white_cell += 1
            else:
                maze[(i1, i2)] = -1  # 黒います。とおれない。

    vx = (0, 0, 1, -1)
    vy = (1, -1, 0, 0)
    cnt = 1
    next_nodes = deque()
    next_nodes.append((0, 0))
    next2_nodes = deque()
    """
    方針：
    mazeをBFSで更新し「ゴール到達可否」「最短路」を求める。
    ゴール到達可なら「白いマスの数 - スタートとゴールを含む再短路のマス数」が
    塗ることのできる黒いマス数になる。
    (0,0)からの距離cntを１で開始し、１ずつカウントアップして更新してmapの各マスにいれる。
    ゴールセルに入った数が「スタートとゴールを含む再短路のセル数」になる。
    """
    while next_nodes:
        while next_nodes:
            nextn = next_nodes.popleft()
            nextny = nextn[0]
            nextnx = nextn[1]
            for j1 in range(4):
                ny = nextny + vy[j1]
                nx = nextnx + vx[j1]
                if ny == -1 or ny == h or nx == -1 or nx == w:
                    continue
                elif maze[(ny, nx)] == 0:
                    next2_nodes.append((ny, nx))
                    # 「次の遷移先ノード」を更新し、重複してnext2_nodesに加えないようにする。
                    maze[(ny, nx)] = cnt + 1
        cnt += 1
        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()

    """
    結果出力。maze[(h-1, w-1)]が0のままなら「ゴール到達不可」なので-1、
    そうではないなら「黒にできるマスの数」をprint
    """
    if maze[(h-1, w-1)] == 0:
        print(-1)
    else:
        r = white_cell - maze[(h-1, w-1)]
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    maze = []
    wn = 0
    for _ in range(H):
        maze.append(input())
        wn += maze[-1].count(".")
    pc = -1
    que = deque([(0, 0, 1)])
    visited = {(0, 0)}
    while que:
        y, x, d = que.popleft()
        if y == H-1 and x == W-1:
            pc = d
        for dy, dx in moves:
            ny, nx = y+dy, x+dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == "." and (ny, nx) not in visited:
                que.append((ny, nx, d+1))
                visited.add((ny, nx))
    if pc == -1:
        print(-1)
    else:
        print(wn-pc)


if __name__ == "__main__":
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

h, w = map(int, input().split())
grid = [list(map(str, input().rstrip())) for _ in range(h)]

kuro = 0
for g in grid:
    kuro += g.count("#")

q = deque([[0, 0]])
grid[0][0] = 1
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while q:
    cx, cy = q.popleft()
    for m in moves:
        nx, ny = cx + m[0], cy + m[1]
        if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1:
            continue
        elif grid[nx][ny] == "#":
            continue
        elif grid[nx][ny] == ".":
            grid[nx][ny] = grid[cx][cy] + 1
            q.append([nx, ny])
            if nx == h - 1 and ny == w - 1:
                print(h * w - grid[nx][ny] - kuro)
                sys.exit()
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

h, w = map(int, input().split())
grid = [list(list(map(str, input().rstrip()))) for _ in range(h)]

kuro = 0
for g in grid:
    kuro += g.count("#")

q = deque([[0, 0]])
grid[0][0] = 1
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while q:
    cx, cy = q.popleft()
    for m in moves:
        nx, ny = cx + m[0], cy + m[1]
        if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1:
            continue
        elif grid[nx][ny] == "#":
            continue
        elif grid[nx][ny] == ".":
            grid[nx][ny] = grid[cx][cy] + 1
            q.append([nx, ny])
            if nx == h - 1 and ny == w - 1:
                print(h * w - grid[nx][ny] - kuro)
                sys.exit()
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, sy, sx):
    gy, gx = H - 1, W - 1
    q = deque()
    q.append((sy, sx))
    visited[sy][sx] = 1
    #print(sy, sx, gy, gx)
    now = 0
    while q:
      y, x = q.popleft()
      if (y, x) == (gy, gx):
        return visited[y][x]
      for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + j, x + k #改行して条件文を続けるときにバックスラッシュ
        if (0 <= new_y <= H - 1) and (0 <= new_x <= W - 1):
          if maze[new_y][new_x] == "." and visited[new_y][new_x] > 10 ** 5:#まだ来たことない点だったという条件
            visited[new_y][new_x] = visited[y][x] + 1
            q.append((new_y, new_x))
    return 0

          
if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [[0] * W for i in range(H)]
    count = 0
    for i in range(H):
      s = str(input())
      for j in range(W):
        maze[i][j] = s[j]
        if s[j] == ".":
          count += 1
    visited = [[float("inf")] * W for j in range(H)]
    ans = bfs(maze, 0, 0)
    if ans == 0:
      print(-1)
    else:
      print(count - ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, sy, sx):
    gy, gx = H - 1, W - 1
    q = deque([[sy, sx]])
    visited[sy][sx] = 1
    #print(sy, sx, gy, gx)
    now = 0
    while q:
      y, x = q.popleft()
      if (y, x) == (gy, gx):
        return visited[y][x]
      for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + j, x + k #改行して条件文を続けるときにバックスラッシュ
        if (0 <= new_y <= H - 1) and (0 <= new_x <= W - 1):
          if maze[new_y][new_x] == "." and visited[new_y][new_x] > 10 ** 5:#まだ来たことない点だったという条件
            visited[new_y][new_x] = visited[y][x] + 1
            q.append([new_y, new_x])
    return 0

          
if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [[0] * W for i in range(H)]
    count = 0
    for i in range(H):
      s = str(input())
      for j in range(W):
        maze[i][j] = s[j]
        if s[j] == ".":
          count += 1
    visited = [[float("inf")] * W for j in range(H)]
    ans = bfs(maze, 0, 0)
    if ans == 0:
      print(-1)
    else:
      print(count - ans)

Submission status: Accepted

Solution code:
#from collections import deque

def bfs(maze, sy, sx):
    gy, gx = H - 1, W - 1
    q = [[sy, sx]]
    visited[sy][sx] = 1
    #print(sy, sx, gy, gx)
    now = 0
    while q:
      y, x = q.pop(0)
      if (y, x) == (gy, gx):
        return visited[y][x]
      for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + j, x + k #改行して条件文を続けるときにバックスラッシュ
        if (0 <= new_y <= H - 1) and (0 <= new_x <= W - 1):
          if maze[new_y][new_x] == "." and visited[new_y][new_x] > 10 ** 5:#まだ来たことない点だったという条件
            visited[new_y][new_x] = visited[y][x] + 1
            q.append([new_y, new_x])
    return 0

          
if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [[0] * W for i in range(H)]
    count = 0
    for i in range(H):
      s = str(input())
      for j in range(W):
        maze[i][j] = s[j]
        if s[j] == ".":
          count += 1
    visited = [[float("inf")] * W for j in range(H)]
    ans = bfs(maze, 0, 0)
    if ans == 0:
      print(-1)
    else:
      print(count - ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
map = [list(input()) for _ in range(h)]
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

def bfs():
    q = deque([])
    q.append((0,0))
    d = [([-1]*w)for _ in range(h)]

    d[0][0] =  ~-sum(1 for i in range(h) for j in range(w) if map[i][j] == ".")

    while q:
        x,y = q.popleft()
        if (x,y) == (h-1,w-1):
            break
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<h and 0<=ny<w and d[nx][ny]==-1 and map[nx][ny]!="#":
                q.append((nx,ny))
                d[nx][ny]= d[x][y] -1
    return d[h-1][w-1]
print(bfs())

Submission status: Accepted

Solution code:
dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def main():
  H, W = map(int, input().split())
  d = [[-1] *W for _ in range(H)]
  S = []
  for i in range(H):
    S.append(list(str(input())))
  ans =  -1
  que = [[0, 0]]
  d[0][0] = 1
  while len(que)>0:
    now = que.pop(0)
    for move in dir:
      nex = [now[0] + move[0], now[1] + move[1]]
      if 0 <= nex[0] < H and 0 <= nex[1] < W and S[nex[0]][nex[1]] == '.' and d[nex[0]][nex[1]] == -1:
        d[nex[0]][nex[1]] = d[now[0]][now[1]] + 1
        if nex[0] == H-1 and nex[1] == W-1:
          ans = d[H-1][W-1]
          break
        else:
          que.append(nex)
  if ans == -1:
    print(ans)
  else:
    num = 0
    for i in range(H):
      for j in range(W):
        if S[i][j] == '.':
          num += 1
    print(num - ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 1
Q = deque()
Q.append([0, 0])
c = 0
for l in s:
    c += l.count('.')

yudlr = [1, -1, 0, 0]
xudlr = [0, 0, -1, 1]

while len(Q) > 0:
    q = Q.popleft()
    y, x = q[0], q[1]
    for i in range(4):
        y1 = y + yudlr[i]
        x1 = x + xudlr[i]
        if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
            continue
        if s[y1][x1] == '#':
            continue
        if dist[y1][x1] != -1:
            continue
        dist[y1][x1] = dist[y][x] + 1
        if y1 == H - 1 and x1 == W - 1:
            print(c - dist[y1][x1])
            sys.exit()
        Q.append([y1, x1])

print('-1')

Submission status: Accepted

Solution code:
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))
p=0
for i in range(h):
    j=input()
    p+=j.count('#')
    l.append('#'+j+'#')
l.append('#'*(w+2))
q=deque([[1,1]])
s=[[-1 for j in i] for i in l]
s[1][1]=1
while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
        if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
            q.append([x+i,y+j])
            s[x+i][y+j]=s[x][y]+1
    if s[h][w]!=-1:
        break
if s[h][w]!=-1:
  print(h*w-p-s[h][w]) 
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))
p=0
for i in range(h):
    j=input()
    p+=j.count('#')
    l.append('#'+j+'#')
l.append('#'*(w+2))
q=deque([[1,1]])
s=[[-1 for j in i] for i in l]
s[1][1]=1
while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
        if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
            q.append([x+i,y+j])
            s[x+i][y+j]=s[x][y]+1
    if s[h][w]!=-1:
        break
print(h*w-p-s[h][w] if s[h][w]!=-1 else -1)

Submission status: Accepted

Solution code:
from collections import deque, Counter


def bfs():
    dist = [[float("inf")] * W for i in range(H)]
    dist[Sy][Sx] = 0

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

    que = deque([])
    que.append((Sy, Sx))

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        if y == Gy and x == Gx:
            break

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

            if 0 <= ny < H and 0 <= nx < W and Map[ny][nx] != "#" and dist[ny][nx] == float("inf"):
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))

    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]

# Start and Goal
Sy, Sx = 0, 0
Gy, Gx = H - 1, W - 1

# Count #
sharp = 0
for l in Map:
    for s in l:
        if s == "#":
            sharp += 1

# BFS
dist = bfs()

# Can't reach goal
if dist[Gy][Gx] == float("inf"):
    print(-1)
    exit()

# 1 dim array
c = []
for l in dist:
    c += l

ans = H * W - (sharp + dist[Gy][Gx] + 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

stack = deque([(0, 0)])
d = [[-1]*W for _ in range(H)]
d[0][0] = 0

while stack:
  nowx, nowy = stack.popleft()
  if nowx >= 1:
    if s[nowy][nowx-1]=='.' and d[nowy][nowx-1]==-1:
      d[nowy][nowx-1] = d[nowy][nowx] + 1
      stack.append((nowx-1, nowy))
  if nowx <= W-2:
    if s[nowy][nowx+1]=='.' and d[nowy][nowx+1]==-1:
      d[nowy][nowx+1] = d[nowy][nowx] + 1
      stack.append((nowx+1, nowy))
  if nowy >= 1:
    if s[nowy-1][nowx]=='.' and d[nowy-1][nowx]==-1:
      d[nowy-1][nowx] = d[nowy][nowx] + 1
      stack.append((nowx, nowy-1))
  if nowy <= H-2:
    if s[nowy+1][nowx]=='.' and d[nowy+1][nowx]==-1:
      d[nowy+1][nowx] = d[nowy][nowx] + 1
      stack.append((nowx, nowy+1))

if d[H-1][W-1] == -1:
  print(-1)
  exit()
  
white = 0
for si in s:
  for sii in si:
    if sii == '.':
      white += 1
print(white-d[H-1][W-1]-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
sh, sw = 1,1
gh, gw = H,W

S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
white = 0
for h in range(1,H+1):
    S[h] = '*' + input() + '*'
    white += S[h].count('.')

visited = [[False]*(W+2) for _ in range(H+2)]
dh = [0,1,0,-1]
dw = [1,0,-1,0]

from collections import deque
d = deque()

visited[sh][sw]=True
d.append((sh,sw,1))

while len(d)>0:
    h,w,cnt = d.popleft()
    for i in range(4):
        h0 = h+dh[i]
        w0 = w+dw[i]
        if (h0,w0) == (gh,gw):
            print(white-cnt-1)
            break
        if S[h0][w0]=='.' and visited[h0][w0]==False:
            visited[h0][w0]=True
            d.append((h0,w0,cnt+1))
    else:
        continue
    break
else:
    print(-1)

Submission status: Accepted

Solution code:
import queue
import itertools
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
G = [[] for _ in range(H * W)]

for i in range(H * W):
    u = i // W
    v = i % W
    
    if s[u][v] == '#':
        continue
    if u-1 >= 0 :
        if s[u-1][v] == '.':
            G[i].append(i-W)
    if v-1 >= 0:
        if s[u][v-1] == '.':
            G[i].append(i-1)
    if v+1 < W:
        if s[u][v+1] == '.':
            G[i].append(i+1)
    if u+1 < H:
        if s[u+1][v] == '.':
            G[i].append(i+W)

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist
dist = dfs(G, H*W, 0)

if dist[-1] == -1:
    print(-1)
    exit()
count = list(itertools.chain.from_iterable(s)).count('#')
print(H*W - (dist[-1] + 1) - count)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

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

    que = collections.deque([[0, 0, 1]])
    fp[0][0] = 1
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    is_found = False

    while que:
        temp = que.popleft()

        if temp[0] == H-1 and temp[1] == W-1:
            pass_num = temp[2]
            que = False
            is_found = True
        else:
            for dy, dx in next_y_x:
                ny = temp[0] + dy
                nx = temp[1] + dx

                if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                    if grid[ny][nx] == '.' and fp[ny][nx] == -1:
                        que.append([ny, nx, temp[2]+1])
                        fp[ny][nx] = temp[2] + 1

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

    if is_found:
        print(H*W - black_cnt - pass_num)
    else:
        print(-1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
def BFS(x,y,l):
   que=deque([(x,y)])
   visited=[[0]*W for i in range(H)]
   visited[0][0]=1
   while que:
      x,y=que.popleft()
      node=visited[y][x]
      if 0 < x:
         if l[y][x-1] != "#" and not visited[y][x-1]:
            visited[y][x-1]+=node+1
            que.append((x-1,y))
      if 0 < y:
         if l[y-1][x] != "#" and not visited[y-1][x]:
            visited[y-1][x]+=node+1
            que.append((x,y-1))
      if x < W-1:
         if l[y][x+1] != "#" and not visited[y][x+1]:
            visited[y][x+1]+=node+1
            que.append((x+1,y))
      if y < H-1:
         if l[y+1][x] != "#" and not visited[y+1][x]:
            visited[y+1][x]+=node+1
            que.append((x,y+1))
      if x==W-1 and y==H-1:
         return visited[H-1][W-1]
   return -1
H,W=list(map(int,input().split()))
l=[]
tmp2=0
for i in range(H):
   tmp=list(input())
   tmp2+=tmp.count("#")
   l.append(tmp)
ans=BFS(0,0,l)
if ans != -1 and l[0][0] != "#":
   print(W*H-ans-tmp2)
else:
   print(-1)

Submission status: Accepted

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

def main():
    H, W = map(int, input().split())
    grid = [None] * H
    white = 0
    for i in range(H):
        grid[i] = input()
        white += grid[i].count('.')

    q = deque()
    q.append([0, 0, 1])
    opt = ((0, 1), (0, -1), (1, 0), (-1, 0))
    visited = set()

    while q:
        y, x, dist = q.popleft()
        if grid[y][x] == '#':
            continue
        if (y, x) in visited:
            continue
        visited.add((y, x))
        if y == H-1 and x == W-1:
            print(white - dist)
            exit()
        for dy, dx in opt:
            if 0 <= y+dy < H and 0 <= x+dx < W:
                q.append([y+dy, x+dx, dist+1])
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    #H*W - 最短経路の距離 - 黒いマスの数　- スタート分の1
    H,W = LMIIS()
    grid = []
    num_black = 0
    for i in range(H):
        line = list(input())
        grid.append(line)
        num_black += line.count('#')

    
    #bfs
    target_queue = deque()
    
    visited = []
    for i in range(H):
        visited.append([-1]*W)
    visited[0][0] = 0
    target_queue.append((0,0))

    while target_queue:
        y,x = target_queue.popleft()
        if y == H-1 and x == W-1:
            break
        next_distance = visited[y][x] + 1
        if y > 0 and grid[y-1][x] != '#' and visited[y-1][x] == -1:
            visited[y-1][x] = next_distance
            target_queue.append((y-1,x))
        if y + 1 < H and grid[y+1][x] != '#' and visited[y+1][x] == -1:
            visited[y+1][x] = next_distance
            target_queue.append((y+1,x))
        if x > 0 and grid[y][x-1]!= '#' and visited[y][x-1] == -1:
            visited[y][x-1] = next_distance
            target_queue.append((y,x-1))
        if x+1 < W and grid[y][x+1]!='#' and visited[y][x+1] == -1:
            
            visited[y][x+1] = next_distance
            target_queue.append((y,x+1))
    
    if visited[H-1][W-1] == -1:
        print(-1)
    else:
        print(H*W - num_black - visited[H-1][W-1] -1)
    





        
    
main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(input()))
q = deque([(0, 0)])
s[0][0] = 0
dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)
blacks = 0
for y in range(h):
    blacks += s[y].count("#")
while q:
    y, x = q.popleft()
    dist = s[y][x]
    if (y, x) == (h - 1, w - 1):
        break
    for k in range(4):
        ny, nx = y + dy[k], x + dx[k]
        if 0 <= ny < h and 0 <= nx < w:
            if s[ny][nx] == ".":
                s[ny][nx] = dist + 1
                q.append((ny, nx))
if s[h - 1][w - 1] == ".":
    print(-1)
else:
    print(h * w - s[h - 1][w - 1] - blacks - 1)