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:
H,W = map(int,input().split())
S = [input() for i in range(H)]
blk = sum(row.count('#') for row in S)

from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '#': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))
if visited[-1][-1]:
    print(H*W - blk - dist[-1][-1] - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0

        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    #辺の追加
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]


    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.adjacent

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #ある1点からの距離
    def distance_all(self,u):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        return T

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in self.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None

    #グラフの直径
    def diameter(self):
        from collections import deque
        inf=float("inf")

        u=self.vertex[0]
        T={u:inf  for u in self.vertex}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)

        w=max(T,key=lambda x:T[x])
        T={u:inf  for u in self.vertex}

        Q=deque([w])
        T[w]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        w=max(T,key=lambda x:T[x])
        return T[w]

#格子グラフ
def Grid_Graph(m,n):
    E=[]
    for x in range(1,m+1):
        E+=[(x,y) for y in range(1,n+1)]

    G=Graph(E)
    H=[(1,0),(0,1)]

    for y in range(1,n+1):
        for x in range(1,m+1):
            for a,b in H:
                p=x+a
                q=y+b
                if 1<=p<=m and 1<=q<=n:
                    G.add_edge((x,y),(p,q))
    return G
#================================================
H,W=map(int,input().split())
G=Grid_Graph(W,H)

for i in range(H):
    S=input()
    for j in range(W):
        if S[j]=="#":
            G.remove_vertex((j+1,i+1))

L=G.distance((1,1),(W,H))

if L==float("inf"):
    print(-1)
else:
    print(len(G.adjacent)-(L+1))

Submission status: Accepted

Solution code:
from collections import deque

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

s_lst = [[i for i in input()]for j in range(H)]

dist = [[-1 for i in range(W)] for i in range(H)]
dist[0][0] = 1
d = deque()
d.append([0,0])

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

dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

while d:
    x,y = d.popleft()
    for dx, dy in dy_dx:
        nx = x + dx
        ny = y + dy

        if 0>nx or W<=nx or 0>ny or H<=ny:
            continue

        if dist[ny][nx] != -1 or s_lst[ny][nx] == "#":
            continue
        d.append([nx,ny])
        dist[ny][nx] = dist[y][x] +1

if dist[H-1][W-1] == -1:
    print(-1)
else:
    print(white_cnt-dist[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dist = [[-1 for _ in range(w+2)] for _ in range(h+2)]
dist[1][1] = 1
white = 0
dl = [[1, 0], [0, 1], [-1, 0], [0, -1]]
tmp = ["#" for _ in range(w+2)]
S = [tmp]
for i in range(h):
    S.append([])
    for j in range(w):
        white += 1 if s[i][j] == "." else 0
    S[i+1].extend("#")
    S[i+1].extend(s[i])
    S[i+1].extend("#")
S.append(tmp)


def dfs():
    global S, dl
    queue = deque([[1, 1]])

    while queue:
        [x, y] = queue.popleft()
        for d in dl:
            if dist[x + d[0]][y + d[1]] == -1 and S[x + d[0]][y + d[1]] == ".":
                dist[x + d[0]][y + d[1]] = dist[x][y] + 1
                queue.append([x + d[0], y + d[1]])


dfs()
if dist[h][w] == -1:
    print(-1)
else:
    print(white-dist[h][w])

Submission status: Accepted

Solution code:
#ABC088 d Grid Repainting 
from collections import deque 

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 and nx < h and 0 <= ny and ny < w and maze[nx][ny] != '#' and d[nx][ny] == float('inf'):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            white += 1
res = bfs()
if 0 < res < float('inf'):
    print(white - res - 1)
else :
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    Q = deque([])
    Q.append([0,0])
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    d = [[float('inf')] * W for _ in range(H)]
    d[0][0] = 0
    while Q:
        h, w = Q.popleft()
        if h == H - 1 and w == w - 1:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.' and d[nh][nw] == float('inf'):
                    d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                    Q.append([nh,nw])

    if d[H-1][W-1] == float('inf'):
        print(-1)
        exit()
    
    cnt = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                cnt += 1

    print(cnt - d[H-1][W-1] - 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = []
Blank = 0
for i in range(H):
  temp = str(input());temp = list(temp)
  Blank += temp.count(".")
  S.append(temp)
#print(S,Blank)
INF = float("inf")
Q = deque([])
Q.append([0,0])
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
visited = [[INF]*W for _ in range(H)]
visited[0][0] = 1
while Q:
  temp = Q.popleft()
  x = temp[0]; y = temp[1]
  for i in range(4):
    nx = x+dxdy[i][0]
    ny = y+dxdy[i][1]
    if 0<=nx<H and 0<=ny<W and visited[nx][ny] == INF and S[nx][ny] == ".":
      visited[nx][ny] = visited[x][y] + 1
      Q.append([nx,ny])
      if [nx,ny] == [H,W]:
        break
#print(visited)
if visited[H-1][W-1] == INF:
  print(-1)
  exit()
ans = Blank - visited[H-1][W-1]
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
black=0
for i in range(h):
    black+=s[i].count("#")




from collections import deque
que=deque()
que.append([0,0])
s[0][0]="#"
count=[[0]*w for _ in range(h)]
while que:
    
    x=que.pop()
    dx_dy=[[0,1],[1,0],[0,-1],[-1,0]]
    for k in range(4):
        nx=x[0]+dx_dy[k][0]
        ny=x[1]+dx_dy[k][1]
        if 0<=nx<=h-1 and 0<=ny<=w-1 and s[nx][ny]==".":
            s[nx][ny]="#"
            count[nx][ny]=count[x[0]][x[1]]+1
            que.appendleft([nx,ny])
if s[-1][-1]=="#":
    print(h*w-count[-1][-1]-black-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]

sh, sw, gh, gw = 0, 0, h - 1, w - 1
d = [[float("inf")] * w for _ in range(h)]

que = deque([])
que.append((sh, sw))
d[sh][sw] = 0


def bfs():
    while que:
        p = que.popleft()
        if p[0] == gh and p[1] == gw:
            break
        for i in range(4):
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]
            if 0 <= nh < h and 0 <= nw < w and maze[nh][nw] != "#" and d[nh][nw] == float("inf"):
                que.append((nh, nw))
                d[nh][nw] = d[p[0]][p[1]] + 1
    return d[gh][gw]

##最短距離を格納
bfs = bfs()
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            cnt += 1
if bfs == float("inf"):
    print(-1)
else:
    print(cnt - (bfs + 1))

Submission status: Accepted

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

sx, sy, gx, gy = 0, 0, h - 1, w - 1
d = [[float("inf")] * w for _ in range(h)]

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


def bfs():
    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"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

##最短距離を格納
bfs = bfs()
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            cnt += 1
if bfs == float("inf"):
    print(-1)
else:
    print(cnt - (bfs + 1))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
g=[input() for _ in range(h)]
d=[[-1]*w for _ in range(h)]
d[0][0]=0
q=[(0,0)]
while q:
  tx,ty=q.pop(0)
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
      d[nx][ny]=d[tx][ty]+1
      q+=[(nx,ny)]
print((sum(s.count('.') for s in g)-d[-1][-1])*(d[-1][-1]>0)-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
g=[input() for _ in range(h)]
d=[[-1]*w for _ in range(h)]
d[0][0]=0
q=[(0,0)]
while q:
  tx,ty=q.pop(0)
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
      d[nx][ny]=d[tx][ty]+1
      q+=[(nx,ny)]
print((h*w-sum(s.count('#') for s in g)-d[-1][-1])*(d[-1][-1]>0)-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
g=[input() for _ in range(h)]
from collections import *
d=[[-1]*w for _ in range(h)]
d[0][0]=0
q=deque([(0,0)])
while q:
  tx,ty=q.popleft()
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
      d[nx][ny]=d[tx][ty]+1
      q.append((nx,ny))
print((h*w-sum(s.count('#') for s in g)-d[-1][-1])*(d[-1][-1]>0)-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
g=[input() for _ in range(h)]
from collections import *
def bfs(x,y):
  d=[[-1]*w for _ in range(h)]
  d[x][y]=0
  q=deque([(x,y)])
  while q:
    tx,ty=q.popleft()
    for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
      nx,ny=tx+dx,ty+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
        d[nx][ny]=d[tx][ty]+1
        q.append((nx,ny))
  return d
d=bfs(0,0)[-1][-1]
print((h*w-sum(s.count('#') for s in g)-d)*(d>0)-1)

Submission status: Accepted

Solution code:
from collections import deque

INF = 10**18

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

live_cell_count = 0
for S_line in S:
    live_cell_count += S_line.count(".")

dist = [[INF for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
q = deque([(0, 0)])
while q:
    t_pos = tx, ty = q.popleft()
    t_dist = dist[ty][tx]

    for dx, dy in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        pos = x, y = tx+dx, ty+dy
        if not (0 <= x < W and 0 <= y < H):
            continue
        elif S[y][x] == "#":
            continue
        elif dist[y][x] <= t_dist + 1:
            continue
        dist[y][x] = t_dist + 1
        q.append(pos)
# print(dist)

if dist[H-1][W-1] == INF:
    print(-1)
else:
    print(live_cell_count - dist[H-1][W-1] - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

H, W = map(int, input().split())
sss = [[int(c == '#') for c in input().rstrip()] for _ in range(H)]

dhw = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
]

# h,w,dist
dq = deque([(0, 0, 0)])
# h,w
queued = {(0, 0)}

fdist = -1
while dq:
    h, w, dist = dq.popleft()
    
    if h == H - 1 and w == W - 1:
        fdist = dist
        break
        
    for dh, dw in dhw:
        nh = h + dh
        nw = w + dw
        ndist = dist + 1

        if (nh,nw) in queued:
            continue
        if not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if sss[nh][nw]:
            continue

        dq.append((nh, nw, ndist))
        queued.add((nh, nw))

if fdist == -1:
    print(-1)
else:
    print(H * W - sum(sum(sss,[])) - fdist - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

dhw = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
]

# h,w,dist
dq = deque([(0, 0, 0)])
# h,w
queued = {(0, 0)}

fdist = -1
while dq:
    h, w, dist = dq.popleft()
    
    if h == H - 1 and w == W - 1:
        fdist = dist
        break
        
    for dh, dw in dhw:
        nh = h + dh
        nw = w + dw
        ndist = dist + 1

        if (nh,nw) in queued:
            continue
        if not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if sss[nh][nw]:
            continue

        dq.append((nh, nw, ndist))
        queued.add((nh, nw))

if fdist == -1:
    print(-1)
else:
    print(H * W - sum(sum(sss,[])) - fdist - 1)

Submission status: Accepted

Solution code:
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
s = []
nb = 0
for i in range(h):
    ss = ins()
    s.append(ss)
    nb += ss.count('#')
q = deque([(0,0)])
d = [[BIG]*w for i in range(h)]
d[0][0] = 0
while len(q)>0:
    x,y = q.popleft()
    dd = d[x][y]
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and s[xx][yy]=='.' and d[xx][yy]>dd+1:
            d[xx][yy] = dd+1
            q.append((xx,yy))
z = d[h-1][w-1]
print(-1 if z==BIG else (h*w-nb-z-1))

Submission status: Accepted

Solution code:
def neighbor(i, j):
    dxy4 = [(0, 1), (-1, 0), (0, -1), (1, 0)]
    neighL = []
    for dxy in dxy4:
        ni, nj = i+dxy[0], j+dxy[1]
        if 0<= ni < H and 0<= nj < W:
            if map_[ni][nj] =='.':
                neighL.append((ni, nj))
    return neighL
            
def bfs(start, goal):
    from collections import deque
    WHITE, GRAY, BLACK, INF = 0, 1, 2, float('inf')
    
    color = [[WHITE]*W for _ in range(H)]
    d = [[INF]*W for _ in range(H)]
    
    i0, j0 = start
    i1, j1 = goal
    depth = 0
    color[i0][j0] = GRAY
    d[i0][j0] = depth + 1
    Q = deque([(i0, j0)])
    while Q:
        i, j = Q.popleft()
        depth = d[i][j]
        for ni, nj in neighbor(i, j):
            if color[ni][nj] == WHITE:
                color[ni][nj] = GRAY
                d[ni][nj] = depth + 1
                Q.append((ni, nj))
        color[i][j] = BLACK
    return d[i1][j1]


H, W = map(int, input().split())
map_ =  [list(input().strip()) for _ in range(H)]   #; print(map_)
n_open = sum([map_[i].count('.') for i in range(H)])
start, goal = (0, 0), (H-1, W-1)
min_d = bfs(start, goal)
if min_d == float('inf'):
    print(-1)
else:
    print(n_open - min_d)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
cost_map =  [[None]*W for i in range(H)]
whites = 0
for i in range(H):
    for j in range(W):
        if map[i][j]==".":
            whites += 1
# 迷路を最短で抜ける
queue = list()
queue.append([0, 0])
cost_map[0][0] = 0
while queue:
    x,y = queue.pop(0)
    if x==H-1 and y==W-1:break
    current = cost_map[x][y]
    if 0<=x+1<H:
        if cost_map[x+1][y] is None and map[x+1][y]==".":
            queue.append([x+1, y])
            cost_map[x+1][y] = current + 1
    if 0<=x-1<H:
        if cost_map[x-1][y] is None and map[x-1][y]==".":
            queue.append([x-1, y])
            cost_map[x-1][y] = current + 1
    if 0<=y+1<W:
        if cost_map[x][y+1] is None and map[x][y+1]==".":
            queue.append([x, y+1])
            cost_map[x][y+1] = current + 1
    if 0<=y-1<W:
        if cost_map[x][y-1] is None and map[x][y-1]==".":
            queue.append([x, y-1])
            cost_map[x][y-1] = current + 1
# ゲーム開始時の白のマスの数から最短のマス目を引く
if cost_map[H-1][W-1] is None:
    print("-1")
else:
    print(whites - cost_map[H-1][W-1]-1)

Submission status: Accepted

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

from collections import deque

def bfs():
    seen = [[float('inf')]*W for _ in range(H)]
    que = deque([(0,0)])
    seen[0][0] = 0
    while que:
        a,b = que.popleft()
        if a==W-1 and b==H-1:
            break
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = x + a
            ny = y + b
            if 0<=nx<W and 0<=ny<H and masu[ny][nx]!='#' and seen[ny][nx] == float('inf'):
                que.append((nx,ny))
                seen[ny][nx] = seen[b][a]+1
    return seen[H-1][W-1]
saitan = bfs()
count = 0
for h in range(H):
    for w in range(W):
        if masu[h][w] == '#':
            count += 1
if saitan == float('inf'):
    print(-1)
else:print(H*W-saitan-count-1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R,C = NMI()
    sy, sx = 0,0
    gy, gx = R-1,C-1
    board = [list(input()) for _ in range(R)]

    #移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #すべての点をINFで初期化
    INF = R*C*2
    distance = [[INF for _ in range(C)] for _ in range(R)]

    #地点を保存するqueを作成、スタート地点を入れる
    que = deque([])
    que.append((sy,sx))

    #スタート地点の距離は0
    distance[sy][sx] = 0
    
    #最短経路
    shortest = INF

    #queが空になるまでループ
    while len(que) != 0:
        #取り出してきた状態がゴールなら探索をやめる
        pop = que.popleft()
        if pop[0]==gy and pop[1]==gx:
            shortest = distance[gy][gx]+1


        #移動4方向をループ
        for i in range(len(dx)):
            #移動した後の点をny,nxとする
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]

            #nyが0以上R未満   nxが0以上C未満     盤上で壁ではない        まだ訪れたことがない
            if 0<= ny < R and 0 <= nx < C and board[ny][nx]!='#' and distance[ny][nx] == INF:
                #つまり移動可能でまだ行ったことがなければqueへ入れる
                que.append((ny,nx))
                #その距離をもとのpopの最短距離+1でdistanceに記録
                distance[ny][nx] = distance[pop[0]][pop[1]]+1
    
    if shortest == INF:
        print(-1)
    else:
        dots = 0
        for r in range(R):
            for c in range(C):
                if board[r][c] == '.':
                    dots += 1
        print(dots-shortest)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

h,w=map(int,readline().split())
wb={'#':0,'.':1}
s=[wb[g] for g in read() if g!='\n']
dist=[0]*(h*w)
dist[0]=1
stack=deque([(0,0)])
while stack:
  cg=stack.popleft()
  for i in range(4):
    ng=(cg[0]+(1-2*(i&1))*(i>>1),cg[1]+(1-2*(i&1))*(1-(i>>1)))
    fcg=w*cg[0]+cg[1]
    fng=w*ng[0]+ng[1]
    if 0<=ng[0]<=h-1 and 0<=ng[1]<=w-1 and \
        s[fng] and dist[fng]==0:
      stack.append(ng)
      dist[fng]=dist[fcg]+1
if dist[-1]:
  print(sum(s)-dist[-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=[int(x) for x in input().split()]
c=[]
b=0
for i in range(h):
  C=input()
  b+=C.count("#")
  c.append(C)

dist=[[0]*w for i in range(h)]
dist[0][0]=1
d=deque()
d.append([0,0])

dydx=[[1,0],[0,1],[-1,0],[0,-1]]

while d:
  y,x=d.popleft()
  if y==h-1 and x==w-1:
    break
  for i in range(4):
    ny,nx=y+dydx[i][0],x+dydx[i][1]
    if not(0 <= ny < h) or not(0 <= nx < w) or dist[ny][nx]!=0 or c[ny][nx]=="#":
      continue
    dist[ny][nx]=dist[y][x]+1
    d.append([ny,nx])

if dist[h-1][w-1]==0:
  print(-1)
else:
  ans=h*w-b-dist[h-1][w-1]
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
wall = '#'
maze = [[wall] * (w + 2)]
wn = 0
for y in range(1, h+1):
    maze.append([wall] + [c for c in input()] + [wall])
    for x in range(1, w+1):
        if maze[y][x] == '.':
            wn += 1
maze.append([wall] * (w + 2))

q = deque()
q.append((1, 1, 0))
reachable = False
while q:
    y, x, i = q.popleft()
    if maze[y][x] == '#':
        continue
    if y == h and x == w:
        reachable = True
        break
    maze[y][x] = '#'
    i += 1
    q.append((y+1, x, i))
    q.append((y-1, x, i))
    q.append((y, x+1, i))
    q.append((y, x-1, i))
print(wn - i - 1 if reachable else -1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    d = Init(H, W, -1)
    mylist = [input().rstrip() for i in range(H)]
    move = [[1,0],[0,1],[-1,0],[0,-1]]
    dq = deque()
    dq.append([0,0])
    goal = [H-1,W-1]
    d[0][0] = 0
    while dq:
        ht, wt = dq.popleft()
        for h, w in move:
            h += ht
            w += wt
            if h >= 0 and h < H and w >= 0 and w < W and d[h][w] == -1 and mylist[h][w] != "#":
                d[h][w] = d[ht][wt]+1
                dq.append([h,w])
                
    goal_dist = d[goal[0]][goal[1]]
    if goal_dist == -1:
        print(-1)
    else:
        white = 0
        for i in mylist:
            white += i.count('.')
        print(white-goal_dist-1)


        
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import collections
from collections import deque

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

def main():
    H, W = map(int, input().split())
    field = []
    white = 0
    for h in range(H):
        tmp = list(input()[:-1])
        white += collections.Counter(tmp)['.']
        field.append(tmp)

    # BFS
    field[0][0] = 1
    que = deque([(0, 0)])
    while True:
        fr_x, fr_y = que.popleft()
        cnt = field[fr_x][fr_y]
        for d_x, d_y in digtmp:
            to_x = fr_x + d_x
            to_y = fr_y + d_y
            if 0 <= to_x < H and 0 <= to_y < W:
                if field[to_x][to_y] == '.':
                    field[to_x][to_y] = cnt + 1
                    que.append((to_x, to_y))
                else:
                    continue
        if len(que) == 0:
            break

    goal = field[H-1][W-1]
    if goal in ['.', '#']:
        print(-1)
        return
    ans = white - goal
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 白ます数 - 最短距離が答え

import sys
readline = sys.stdin.readline

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

G = [None] * H
white = 0
for i in range(H):
  G[i] = readline().rstrip()
  white += G[i].count(".")

from collections import deque
q = deque([])
# y,x, 距離
q.append([0, 0, 0])
seen = set()
cases = ((0,1),(0,-1),(1,0),(-1,0))
while q:
  y,x,d = q.popleft()
  if G[y][x] == "#":
    continue
  if (y,x) in seen:
    continue
  seen.add((y,x))
  if y == H - 1 and x == W - 1:
    print(white - d - 1)
    break
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      q.append([y + c[0], x + c[1], d + 1])
else:
  print(-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=[]
for _ in range(h): m.append(list(input()))
black=0
white=0
for i in range(h):
    for j in range(w):
        if m[i][j]=="#": black+=1
white=h*w-black
node=[[0,0,1]]
dx,dy=[-1,0,1,0],[0,1,0,-1]
while node:
    temp=node.pop(0)
    if temp[0]==h-1 and temp[1]==w-1:
        print(h*w-black-temp[2])
        exit()
    m[temp[0]][temp[1]]="#"
    for i in range(4):
        if 0<=temp[0]+dx[i]<h and 0<=temp[1]+dy[i]<w:
            if m[temp[0]+dx[i]][temp[1]+dy[i]]==".":
                node.append([temp[0]+dx[i],temp[1]+dy[i],temp[2]+1])
                m[temp[0]+dx[i]][temp[1]+dy[i]]="#"
print(-1)