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 solve():
    if s[0][0] == '#':
        print(-1)
        return

    stack = deque()
    stack.append([0, 0, 0])
    used = [[False for _ in range(W)] for _ in range(H)]
    costs = [[float('inf') for _ in range(W)] for _ in range(H)]
    while stack:
        i, j, cost = stack.popleft()
        costs[i][j] = cost
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if not 0 <= x < H or not 0 <= y < W or used[x][y] or s[x][y] == '#':
                continue
            stack.append([x, y, cost + 1])
            used[x][y] = True

    print(dot_num - 1 - costs[H - 1][W - 1] if costs[H - 1][W - 1] != float('inf') else -1)

if __name__ == "__main__":
    H, W = map(int, input().split())
    s = []
    dot_num = 0
    for _ in range(H):
        tmp = list(input())
        dot_num += tmp.count('.')
        s.append(tmp)
    solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

from collections import deque


def initialize_maze(h, w):
    grid = [["."] * (w + 2) for _ in range(h + 2)]

    for row in range(h + 2):
        grid[row][0] = "#"
        grid[row][w + 1] = "#"

    for col in range(w + 2):
        grid[0][col] = "#"
        grid[h + 1][col] = "#"

    return grid


def main():
    def bfs():
        que = deque()
        que.append((1, 1, 0))

        while que:
            row, col, count = que.popleft()
            for mr, mc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                nr, nc = row + mr, col + mc
                if grid[nr][nc] == ".":
                    que.append((nr, nc, count + 1))
                    grid[nr][nc] = "!"
                elif grid[nr][nc] == "G":
                    min_count = count + 1
                    return min_count
        return - 1

    h, w = map(int, readline().split())
    grid = initialize_maze(h, w)

    black_num = 0
    for row in range(1, h + 1):
        s = input()
        for col, state in enumerate(s, 1):
            grid[row][col] = state
            if state == "#":
                black_num += 1

    grid[h][w] = "G"

    grid[1][1] = "!"
    min_count = bfs()

    if min_count == -1:
        print(-1)
    else:
        print(h * w - black_num - min_count - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

from collections import defaultdict, deque


def initialize_maze(h, w):
    grid = dict()

    for x in range(w + 2):
        grid[(x, 0)] = "#"
        grid[(x, h + 1)] = "#"

    for y in range(h + 2):
        grid[(0, y)] = "#"
        grid[(w + 1, y)] = "#"

    return grid


def main():
    def bfs():
        que = deque()
        que.append((1, 1, 0))

        while que:
            x, y, count = que.popleft()
            for mx, my in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                nx, ny = x + mx, y + my
                if grid[(nx, ny)] == ".":
                    que.append((nx, ny, count + 1))
                    grid[(nx, ny)] = "!"
                elif grid[(nx, ny)] == "G":
                    min_count = count + 1
                    return min_count
        return - 1

    h, w = map(int, readline().split())
    grid = initialize_maze(h, w)

    black_num = 0
    for y in range(1, h + 1):
        s = input()
        for x, state in enumerate(s, 1):
            grid[(x, y)] = state
            if state == "#":
                black_num += 1

    grid[(w, h)] = "G"

    grid[(1, 1)] = "!"
    min_count = bfs()

    if min_count == -1:
        print(-1)
    else:
        print(h * w - black_num - min_count - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
h,w=map(int,input().split())
s=[input() for _ in range(h)]
seen=[[0]*w for _ in range(h)]
p=[(1,0),(-1,0),(0,1),(0,-1)]
cnt=0
for i in range(h):
    cnt+=s[i].count(".")
d=deque()
d.append((0,0))
seen[0][0]=1
res=0
while True:
    if not d:
        break
    i,j=d.pop()
    for idx in p:
        x,y=idx
        if 0<=i+x<h and 0<=j+y<w and seen[i+x][j+y]==0 and s[i+x][j+y]==".":
            d.appendleft((i+x,j+y))
            seen[i+x][y+j]=seen[i][j]+1
    if seen[h-1][w-1]!=0:
        break
if seen[h-1][w-1]==0:
  print(-1)
else:
  print(cnt-seen[h-1][w-1])

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
m = [list(map((lambda x: 0 if x == '#' else 1),list(input()))) for i in range(h)]
ret = sum(list(map(sum,m)))

q = [[0,0,0]]
m[0][0] = 0
while len(q)!=0:
    qtop = q.pop(0)
    x = qtop[0]
    y = qtop[1]
    d = qtop[2]
    if x == h-1 and y == w-1:
        print(ret-d-1)
        break
    if 0 < x and m[x-1][y] == 1:
        m[x-1][y] = 0
        q.append([x-1,y,d+1])
    if h-1 > x and m[x+1][y] == 1:
        m[x+1][y] = 0
        q.append([x+1,y,d+1])
    if 0 < y and m[x][y-1] == 1:
        m[x][y-1] = 0
        q.append([x,y-1,d+1])
    if w-1 > y and m[x][y+1] == 1:
        m[x][y+1] = 0
        q.append([x,y+1,d+1])
else:
    print(-1)

Submission status: Accepted

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

import queue, itertools
dist = {(i, j) : -1 for i, j in itertools.product(range(W), range(H))}
dist[(0, 0)] = 1
q = queue.Queue()
q.put((0, 0))

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

while not q.empty():
    x, y = q.get()
    d = dist[(x, y)]
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if min(nx, ny) >= 0 and nx <= W - 1 and ny <= H - 1:
            if dist[(nx, ny)] == -1 and G[ny][nx] == '.':
                dist[(nx, ny)] = d + 1
                q.put((nx, ny))
            else: 
                continue

if dist[(W - 1, H - 1)] == -1:
    print(-1)
else:    
    print(H * W - ''.join(G).count('#') - dist[(W - 1, H - 1)])

Submission status: Accepted

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

h, w = map(int, input().split())
maze = [list("#" * (w + 2))]
white = 0
for _ in [0] * h:
    line = "#" + input().strip() + "#"
    maze.append(list(line))
    white += line.count(".")
maze += [list("#" * (w + 2))]
maze[1][1] = 0
maze[-2][-2] = "goal"

q = set([(1,1)])
dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dis = 0
while q:
    next_q = set()
    dis += 1
    for x, y in q:
        #print("x,y:", x, y)
        maze[y][x] = dis

        for dx, dy in dir:
            next_x, next_y = x + dx, y + dy
            if maze[next_y][next_x] == ".":
                #print(next_y,next_x)
                next_q.add((next_x, next_y))

            if maze[next_y][next_x] == "goal":
                print(white - dis - 1)
                exit()
    q = next_q
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4000)

def validCordinate(x, y, dist, Grid):
    if x < 0 or x >= len(Grid[0]):
        return False
    if y < 0 or y >= len(Grid):
        return False

    if dist[y][x] != -1:
        return False

    if Grid[y][x] != '.':
        return False

    return True

def bfs(x, y, q, dist, Grid):
    # 隣接点を検証
    if validCordinate(x + 1, y, dist, Grid):
        q.append((x+1, y))
        dist[y][x+1] = dist[y][x] + 1
    if validCordinate(x, y + 1, dist, Grid):
        q.append((x, y + 1))
        dist[y+1][x] = dist[y][x] + 1
    if validCordinate(x - 1, y, dist, Grid):
        q.append((x-1, y))
        dist[y][x-1] = dist[y][x] + 1
    if validCordinate(x, y - 1, dist, Grid):
        q.append((x, y-1))
        dist[y-1][x] = dist[y][x] + 1


    # finish
    if x == len(Grid[0]) - 1 and y == len(Grid) - 1:
        return dist
    if len(q) == 0:
        return False

    cx, cy = q.popleft()

    return bfs(cx, cy, q, dist, Grid)
    

def main():
    # input
    H, W = map(int, input().split())
    Grid = []
    dist = [[-1 for j in range(W)] for i in range(H)]
    q = deque()

    for i in range(H):
       Grid.append(input()) 


    dist[0][0] = 0
    res = bfs(0, 0, q, dist, Grid)

    if res:
        whiteNumber = 0
        for i in range(H):
            for j in range(W):
                if Grid[i][j] == ".":
                    whiteNumber += 1
        print(whiteNumber - res[-1][-1] - 1)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import itertools
from collections import deque
import bisect
import heapq

def IN(): return int(input())
def sIN(): return input()
def lIN(): return list(input())
def MAP(): return map(int,input().split())
def LMAP(): return list(map(int,input().split()))
def TATE(n): return [input() for i in range(n)]
ans = 0

def bfs(sx,sy):
    global count 
    
    d = [[-1] * w for i in range(h)]

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

    que = deque([])
    que.append((sx, sy))#スタート座標の記録
    d[sx][sy] = 0#スタートからスタートへの最短距離は0

    while que:#中身がなくなるまで
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:#ゴールなら終わり
            break
        for m in range(4):#現在地から4方向の移動を考える
            nx = p[0] + dx[m]
            ny = p[1] + dy[m]

            if 0 <= nx < h and 0 <= ny < w:
              if maze[nx][ny] != "#" and d[nx][ny] == -1:
                que.append((nx, ny))#↑範囲内である＆壁でない＆まだ通ってない
                d[nx][ny] = d[p[0]][p[1]] + 1

    if d[h-1][w-1] == -1:
      return -1
    else:
      for i in range(h):
        count += maze[i].count('.')
      count -= 2#スタートとゴールの分引いた
      return count - d[h-1][w-1] + 1
  
  

h,w = MAP()
maze = [list(input()) for i in range(h)]
count = 0

print(bfs(0,0))

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import copy
def mi() : return map(int,input().split())
a,b=mi()
l=[list(input()) for _ in range(a)]
count=0
for i in range(a):
  for _ in range(b):
    if l[i][_]==".":
      count+=1
l[0][0]=1
q=deque([[0,0]])
while q:
  x,y=q.popleft()
  if x==a-1 and y==b-1:
    print(count-l[x][y])
    sys.exit()
  for e,f in [[0,1],[0,-1],[1,0],[-1,0]]:
    if 0<=x+e<a and 0<=y+f<b and l[x+e][f+y]==".":
      l[x+e][f+y]=l[x][y]+1
      q.append([x+e,y+f])
print(-1)

Submission status: Accepted

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

def 周辺埋め(grid, W):
    U = "#" * (W + 2)
    return [list(U)] + [["#"] + list(g) + ["#"] for g in grid] + [list(U)]

H, W, *grid = open(0).read().split()
H, W = map(int, (H, W))

C = sum(g.count(".") for g in grid)

grid = 周辺埋め(grid, W)

grid[1][1] = "!"
grid[H][W] = "G"

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

def bfs():
    que = deque()
    que.append((1, 1, 0))

    while que:
        cy, cx, c = que.popleft()

        for my, mx in D:
            nx = cx + mx
            ny = cy + my

            if grid[ny][nx] == ".":
                # 未探索
                que.append((ny, nx, c + 1))
                grid[ny][nx] = "!"  # 探索済み
            
            elif grid[ny][nx] == "G":  # ゴール
                return C - (c + 2)

    return -1

print(bfs())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
# from pprint import pprint

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    G = LLS(H)

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

    G[-1][-1] = 'G'
    G[0][0] = '#'

    G2 = grid_wall(G, H, W, '#')
    # print(np.array(G2))

    q = deque([(1, 1, 1)])
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    cost = INF
    while q:
        x, y, d = q.popleft()
        for dx, dy in move:
            nx, ny = x+dx, y+dy
            if G2[nx][ny] == 'G':
                cost = min(cost, d + 1)
            elif G2[nx][ny] == '#': continue
            else:
                q.append((nx, ny, d+1))
                G2[nx][ny] = '#'
    if cost == INF:
        print(-1)
        return
    # print(cost)
    print(H * W - black_cnt - cost)
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
import numpy as np
# from numpy import cumsum  # accumulate
from pprint import pprint

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    G = LLS(H)

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

    G[-1][-1] = 'G'
    G[0][0] = '#'

    G2 = grid_wall(G, H, W, '#')
    # print(np.array(G2))

    q = deque([(1, 1, 1)])
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    cost = INF
    while q:
        x, y, d = q.popleft()
        for dx, dy in move:
            nx, ny = x+dx, y+dy
            if G2[nx][ny] == 'G':
                cost = min(cost, d + 1)
            elif G2[nx][ny] == '#': continue
            else:
                q.append((nx, ny, d+1))
                G2[nx][ny] = '#'
    if cost == INF:
        print(-1)
        return
    # print(cost)
    print(H * W - black_cnt - cost)
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    from collections import deque
    import copy
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [[0] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    b = 0
    for i in range(1, h + 1):
        s = input()
        for j in range(1, w + 2):
            if s[j - 1] == ".":
                cm[i][j] = -1
            elif s[j - 1] == "#":
                b += 1
    que.append([1, 1, 0])
    while len(que) > 0:
        y, x, r = que.popleft()
        c = r + 1
        if cm[y + 1][x] == -1:
            cm[y + 1][x] = c
            que.append([y + 1, x, c])
        if cm[y - 1][x] == -1:
            cm[y - 1][x] = c
            que.append([y - 1, x, c])
        if cm[y][x + 1] == -1:
            cm[y][x + 1] = c
            que.append([y, x + 1, c])
        if cm[y][x - 1] == -1:
            cm[y][x - 1] = c
            que.append([y, x - 1, c])
    if cm[h][w] == -1:
        print(-1)
    else:
        print(h * w - b - cm[h][w] - 1)
main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    H, W = map(int, input().split())
    grid = []; cnt = 0
    grid.append(['#'] * (W+2))
    for _ in range(H):
        tmp = list(input())
        cnt += sum([1 for x in tmp if x == '#'])
        grid.append(['#'] + tmp + ['#'])
    grid.append(['#'] * (W+2))

    que = deque([(1, 1)])
    grid[1][1] = 1
    for _ in range(10000):
        a, b = que.popleft()
        for dx, dy in digtmp:
            x, y = (a + dx, b + dy)
            if grid[x][y] == '.':
                grid[x][y] = grid[a][b] + 1
                que.append((x, y))
        if len(que) == 0:
            break
    if grid[H][W] in ['#', '.']:
        print(-1)
        return
    ans = H*W - grid[H][W] - cnt
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    H, W = list(map(int, input().split()))
    C = [list(input()) for i in range(H)]
    passed = [[False for _ in range(W)] for _ in range(H)]
    import collections
    q = collections.deque([[0,0,1]])
    minhop = float("inf")    
    while q:
        y, x, cnt = q.popleft()
        if y == H-1 and x == W-1:
            minhop = min(minhop, cnt)
            continue
        if passed[y][x]:
            continue
        passed[y][x] = True
        for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            _y, _x = y+i, x+j
            if 0 <= _y < H and 0 <= _x < W and C[_y][_x] == ".":
                q.append([_y, _x, cnt+1])
    
    nblack = 0
    for i in range(H):
        for j in range(W):
            if C[i][j] == "#":
                nblack += 1
    print(H*W-minhop-nblack if minhop != float("inf") else -1)

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
m = [['#'] * (w+2) for i in range(h+2)]
for j in range(h):
    m[j+1][1:w+1] = list(input()) #適宜変える

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

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

seen = [[0] * (w+2) for i in range(h+2)]

todo = [[1, 1]]
seen[1][1] = 1
while(todo != []):
    v = todo.pop(0)
    for i in range(4):
        if m[v[0]+dx[i]][v[1]+dy[i]] != '#' and seen[v[0]+dx[i]][v[1]+dy[i]] == 0:
            seen[v[0]+dx[i]][v[1]+dy[i]] = seen[v[0]][v[1]] + 1
            todo.append([v[0]+dx[i], v[1]+dy[i]])
    
print(white-seen[h][w] if seen[h][w] else -1)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

# 番兵法
h,w = imap()
grid = [[1]*(w+2)] + [[1]+[int(elm == "#") for elm in list(sinput())]+[1] for i in range(h)] + [[1]*(w+2)]

q = col.deque([(1,1)])
dep = col.defaultdict(int)
dep[(1,1)] = 1
while q:
    now = q.popleft()
    if now == (h,w): break
    x,y = now[0],now[1]
    for next in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
        nx,ny = next[0],next[1]
        if grid[nx][ny] or dep[next]: continue # 壁か探索済ならスキップ
        else: dep[next] = dep[now] + 1; q.append(next)

ans = 0
for elm in grid: ans += elm.count(0)
ans = ans - dep[(h,w)] if dep[(h,w)] else -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

G = []
G.append(["#" for _ in range(W + 2)])
for i in range(H):
    G.append(["#"] + list(input()) + ["#"])
G.append(["#" for _ in range(W + 2)])

# print(G)

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

INF = 10 ** 18
d = [[INF for i in range(W + 2)] for j in range(H + 2)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0
    while q:
        a, b = q.popleft()
        for k in range(4):
            if G[a + dx[k]][b + dy[k]] == "#":
                continue
            if d[a + dx[k]][b + dy[k]] != INF:
                continue
            d[a + dx[k]][b + dy[k]] = d[a][b] + 1
            q.append((a + dx[k], b + dy[k]))


bfs(1, 1)
# print(d)
# print(d[H][W])

# (H+2)*(W+2) から「経路+1」と、全ての'#'の数を引いたものが答え
if d[H][W] == INF: # 到達できないときは -1を出力
    print(-1)
else:
    ans = (H + 2) * (W + 2)
    ans -= d[H][W] + 1
    cnt = 0
    for h in range(H + 2):
        for w in range(W + 2):
            if G[h][w] == "#":
                cnt += 1
    ans -= cnt
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

cnt_white = 0
for path in field:
    cnt_white += path.count('.')

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

dyx = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque()
q.append((sy, sx, 0))

while q:
    cy, cx, ct = q.popleft()
    for dy, dx in dyx:
        ny, nx = cy + dy, cx + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if (ny, nx) == (gy, gx):
            print(cnt_white - (ct + 2)) # ct + 2 が使用した '.' の個数
            exit()
        if field[ny][nx] == '#':
            continue
        q.append((ny, nx, ct + 1))
        field[ny][nx] = '#'

print('-1')

Submission status: Accepted

Solution code:
import queue

h, w = map(int, input().split())
S = [input() for _ in range(h)]
n_black = 0
for s in S:
    n_black += s.count('#')

q = queue.Queue()
if S[0][0] == '.': 
    q.put((0, 0))
else: 
    print(-1)
    exit()

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

while True:
    i, j = q.get()

    for ni, nj in ((i-1, j), (i, j-1), (i, j+1), (i+1, j)):
        if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
        if S[ni][nj] == '.' and dist[ni][nj] == -1:
            q.put((ni, nj))
            dist[ni][nj] = dist[i][j] + 1
    
    if q.empty(): break

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

Submission status: Accepted

Solution code:
from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
def S(): return stdin.readline().rstrip()
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def BFS(table,s,step,next,w,h):
    if table[h-1][w-1] != -2:
        return
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    nnext = []
    for rep in next:
        for j in range(4):
            nx = rep[0] + dx[j]
            ny = rep[1] + dy[j]
            if nx<0  or ny<0 or w<=nx or h<=ny:
                continue
            else:
                if s[ny][nx]=='#':
                    continue
                if table[ny][nx]==-2 or step+1<table[ny][nx]:
                    table[ny][nx] = step+1
                    nnext.append([nx,ny])
    if 0<len(nnext):
        BFS(table,s,step+1,nnext,w,h)

def main():
    tmp = LI()
    w,h = tmp.pop(),tmp.pop()
    s = [S() for _ in range(h)]
    table = [[-2]*w for _ in range(h)]
    BFS(table,s,0,[[0,0]],w,h)
    step = table[h-1][w-1]
    if step==-2:
        print(-1)
        exit()
    c = 0
    for rep in s:
        c += rep.count('#')
    ans = w*h-step-c-1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    H, W = map(int, input().rstrip().rsplit())

    visited = [[0]*(W+2) for i in range(H+2)]
    maze = [["#"]*(W+2)]

    black_cnt = 0
    for i in range(H):
        # 黒色のマス目の数をカウント
        row = input().rstrip()
        black_cnt += row.count("#")

        # maze作成
        row = "#" + row + "#"
        maze.append(list(row))

    maze.append(["#"]*(W+2))

    # 幅優先探索で始点からの距離を求める
    queue = deque([(1, 1)])

    while queue:
        x, y = queue.popleft()
        # 黒マスの時
        if maze[x][y] == "#":
            continue

        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            # 探索済みかチェック
            if visited[x+dx][y+dy] > 0:
                continue
            # 次のマス目候補に経路長を入れる
            visited[x+dx][y+dy] = visited[x][y] + 1

            # 探索候補に追加
            queue.append((x+dx, y+dy))

    if visited[H][W] == 0:
        print(-1)
        return
    ans = H*W - black_cnt - visited[H][W] - 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from collections import deque
from copy import deepcopy

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  grid.append(["#" for x in range(W + 2)])
  for y in range(H):
    grid.append(list("#" + input() + "#"))
  grid.append(["#" for x in range(W + 2)])
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      print(grid[y][x], end="")
    print("")
  print("")

def print_visited(visited):
  H = len(visited)
  W = len(visited[0])
  for y in range(H):
    for x in range(W):
      if visited[y][x]:
        print(1, end="")
      else:
        print(0, end="")
    print("")
  print("")

def print_grid_with_paths(grid, paths):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if (x, y) in paths:
        print("*", end="")
      else:
        print(grid[y][x], end="")
    print("")
  print("")

def main():
  H, W, grid = parse()

  visited = [[False for x in range(W + 2)] for y in range(H + 2)]
  for y in range(H + 2):
    for x in range(W + 2):
      if x == 0 or x == W + 1 or y == 0 or y == H + 1:
        visited[y][x] = True
  visited[0][0] = True

  # print_grid(grid)
  # print_visited(visited)

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

  # 幅優先探索で最短経路を求める
  q = deque([(1, 1, [])])
  while len(q) > 0:
    x, y, paths = q.popleft()
    paths.append((x, y))
    # print_grid_with_paths(grid, paths)
    # input()
    
    # 終了条件
    if y == H and x == W:
      # print(paths)
      ans = 0
      for y in range(H + 2):
        for x in range(W + 2):
          # 経路は除外
          if (x, y) in paths:
            continue

          if grid[y][x] == ".":
            ans += 1

      # 最短経路周辺に"#"を置く数をカウント
      # prev_x, prev_y = paths[0]
      # cur_x, cur_y = paths[1]
      # for next_x, next_y in paths[2:]:
      #   for vec in vecs:
      #     adj_x = cur_x + vec[0]
      #     adj_y = cur_y + vec[1]

      #     # 経路上のマスの色は変えない
      #     if adj_x == prev_x and adj_y == prev_y:
      #       continue
      #     if adj_x == next_x and adj_y == next_y:
      #       continue
          
      #     # マスの色を変える
      #     if grid[adj_y][adj_x] == ".":
      #       grid[adj_y][adj_x] = "#"
      #       ans += 1
      #   prev_x, prev_y = cur_x, cur_y
      #   cur_x, cur_y = next_x, next_y
      #   # print_grid(grid)
      #   # input()
      print(ans)
      exit(0)

    for vec in vecs:
      next_x = x + vec[0]
      next_y = y + vec[1]
      if grid[next_y][next_x] == "#":
        continue

      if not visited[next_y][next_x]:
        visited[next_y][next_x] = True
        q.append((next_x, next_y, deepcopy(paths)))

  print(-1)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def resolve():
    from collections import deque
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]
    visited = [[-1]*w for _ in range(h)]
    nxt = [[0,0]]
    nxt = deque(nxt)
    visited[0][0] = 1
    while nxt:
        x, y = nxt.popleft()
        for i, j in ([1,0], [0,1], [-1,0], [0,-1]):
            nx = x+ i
            ny = y+j
            if 0 <= nx < h and 0 <= ny < w and visited[nx][ny]== -1 and maze[nx][ny] != "#":
                visited[nx][ny] = visited[x][y] + 1
                nxt.append([nx, ny])
    totalsharp = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                totalsharp += 1
    if visited[h-1][w-1] == -1:
        print(-1)
    else:
        print(h*w-totalsharp-visited[h-1][w-1])
resolve()