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: Runtime Error

Solution code:


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

c=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[0 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]=='#':
            d[i][j]=-1
        else:
            d[i][j]=inf
            ans+=1


d[0][0]=0
queue=collections.deque([[0,0]])
gy,gx=H-1,W-1

moves=[[1,0],[-1,0],[0,1],[0,-1]]

flag=False
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        
        if 0<=ny and ny<H and 0<=nx and nx<W and c[ny][nx]=='.' and d[ny][nx]==inf:
            d[ny][nx]=d[now[0]][now[1]]+1
            queue.append([ny,nx])
            if ny==gy and nx==gx:
                print(ans-d[ny][nx]-1)
                exit()
print(-1)

Submission status: Runtime Error

Solution code:
import queue
H , W = list(map(int, input().split()))
S = [input() for _ in range(H)]
Sum = 0
for i in range(H):
  for j in range(W):
    Sum += (S[i][j] == '#')
start = [1, 1, 1]
visited = [[0] * W for _ in range(H)]
visited[0][0] = 1
Q = queue.Queue()
Q.put(start)
now = start
while(now[:2] != [H, W] and not Q.empty()):
  now = Q.get()
  for i in range(2):
    for j in range(2):
      h = now[0] + ((-1) ** i + (-1) ** j) // 2
      w = now[1] + ((-1) ** i - (-1) ** j) // 2
      if(1 <= h and h <= H and 1 <= w and w <= W and visited[h - 1][w - 1] == 0 and S[h - 1][w - 1] == '.'):
        visited[h - 1][w - 1] = 1
        Q.put([h, w, now[2] + 1])
if(now[:2] == [H, W]):
  print(H * W - Sum - now[2])
else:
  print(-1)
      h = now[0] + (-1) ** i
      w = now[1] + (-1) ** j
      if(1 <= h and h <= H and 1 <= w and w <= W and visited[h - 1][w - 1] == 0):
        visited[h - 1][w - 1] = 1
        Q.put([h, w, now[2] + 1])
if(now[:2] == [H, W]):
  print(H * W - Sum - now[2])
else:
  print(-1)

Submission status: Runtime Error

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

s = [[]*w for _ in range(h)]
white =0
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == ".":
            white += 1
            s[i].append(10**5)
        elif t[j] == "#":
            s[i].append(t[j])
now = [0,0]
steps =[]
steps.append(now)
direction = []
s[0][0] =0
a = [2]
while len(steps) >0:
    now = copy.copy(steps[0])
    if s[now[0]][now[1]] =="#":
        continue
    for k in [[0,1],[1,0],[-1,0],[0,-1]]:

        if now[0] + k[0] >=0 and now[0] + k[0] < h:
            now[0] += k[0]
            if now[1] + k[1] >=0 and now[1] + k[1] <w:
                if s[now[0]][now[1]] =="#":
                    continue
                else:
                    now[1] += k[1]
                    if s[now[0]][now[1]] == 10**5:
                        if not [now[0],now[1]] in steps:
                            steps.append([now[0],now[1]])
            else:
                continue
        else:
            continue
    # if s[steps[0][0]][steps[0][1]] ==0:
    #     steps.pop(0)
    #     continue
    if s[steps[0][0]][steps[0][1]] >10**4:
        direction =[]
        for l in [[0,1],[1,0],[-1,0],[0,-1]]:
            if steps[0][0]+l[0]>=0 and steps[0][0]+l[0]<h and steps[0][1]+l[1]< w and steps[0][1]+l[1] >=0 and s[steps[0][0]+l[0]][steps[0][1]+l[1]] != "#":
                direction.append(s[steps[0][0]+l[0]][steps[0][1]+l[1]])

        s[steps[0][0]][steps[0][1]] = min(direction)+1
    steps.pop(0)
#print(s)
if s[h-1][w-1] == "#" or s[h-1][w-1] == 10**4:
    print(-1)
else:
    print(white-1 - s[h-1][w-1])

Submission status: Runtime Error

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

s = [[]*w for _ in range(h)]
white =0
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == ".":
            white += 1
            s[i].append(10**5)
        elif t[j] == "#":
            s[i].append(t[j])
now = [0,0]
steps =[]
steps.append(now)
direction = []
s[0][0] =0
a = [2]
while len(steps) >0:
    now = copy.copy(steps[0])
    if s[now[0]][now[1]] =="#":
        continue
    for k in [[0,1],[1,0],[-1,0],[0,-1]]:
        if now[0] + k[0] >=0 and now[0] + k[0] < h:
            now[0] += k[0]
            if now[1] + k[1] >=0 and now[1] + k[1] <w:
                if s[now[0]][now[1]] =="#":
                    continue
                else:
                    now[1] += k[1]
                    if s[now[0]][now[1]] == 10**5:
                        if not [now[0],now[1]] in steps:
                            steps.append([now[0],now[1]])
            else:
                continue
        else:
            continue
    if s[steps[0][0]][steps[0][1]] ==0:
        steps.pop(0)
        continue
    elif s[steps[0][0]][steps[0][1]] >10**4:
        direction =[]
        for l in [[0,1],[1,0],[-1,0],[0,-1]]:
            if steps[0][0]+l[0]>=0 and steps[0][0]+l[0]<h and steps[0][1]+l[1]< w and steps[0][1]+l[1] >=0 and s[steps[0][0]+l[0]][steps[0][1]+l[1]] != "#":
                direction.append(s[steps[0][0]+l[0]][steps[0][1]+l[1]])
        s[steps[0][0]][steps[0][1]] = min(direction)+1
    steps.pop(0)

if s[h-1][w-1] == "#" or s[h-1][w-1] == 10**4:
    print(-1)
else:
    print(white - s[h-1][w-1])

Submission status: Runtime Error

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

s = [[]*w for _ in range(h)]
white =0
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == ".":
            white += 1
            s[i].append(10**5)
        elif t[j] == "#":
            s[i].append(t[j])
now = [0,0]
steps =[]
steps.append(now)
direction = []
s[0][0] =0
a = [2]
while len(steps) >0:
    now = copy.copy(steps[0])
    if s[now[0]][now[1]] =="#":
        continue
    for k in [[0,1],[1,0],[-1,0],[0,-1]]:
        if now[0] + k[0] >=0 and now[0] + k[0] < h:
            now[0] += k[0]
            if now[1] + k[1] >=0 and now[1] + k[1] <w:
                if s[now[0]][now[1]] =="#":
                    continue
                else:
                    now[1] += k[1]
                    if s[now[0]][now[1]] == 10**5:
                        if not [now[0],now[1]] in steps:
                            steps.append([now[0],now[1]])
            else:
                continue
        else:
            continue
    if s[steps[0][0]][steps[0][1]] ==0:
        steps.pop(0)
        continue
    elif s[steps[0][0]][steps[0][1]] >10**4:
        direction =[]
        for l in [[0,1],[1,0],[-1,0],[0,-1]]:
            if steps[0][0]+l[0]>=0 and steps[0][0]+l[0]<h and steps[0][1]+l[1]< w and steps[0][1]+l[1] >=0 and s[steps[0][0]+l[0]][steps[0][1]+l[1]] != "#":
                direction.append(s[steps[0][0]+l[0]][steps[0][1]+l[1]])
        s[steps[0][0]][steps[0][1]] = min(direction)+1
    steps.pop(0)

if s[h-1][w-1] == "#" or s[h-1][w-1] == 10**4:
    print(-1)
else:
    print(white-1 - s[h-1][w-1])

Submission status: Runtime Error

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

s = [[]*w for _ in range(h)]
white =0
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == ".":
            white += 1
            s[i].append(10**5)
        elif t[j] == "#":
            s[i].append(t[j])
now = [0,0]
steps =[]
steps.append(now)
direction = []
s[0][0] =0
a = [2]
while len(steps) >0:
    now = copy.copy(steps[0])
    if s[now[0]][now[1]] =="#":
        continue
    for k in [[0,1],[1,0],[-1,0],[0,-1]]:
        if now[0] + k[0] >=0 and now[0] + k[0] < h:
            now[0] += k[0]
            if now[1] + k[1] >=0 and now[1] + k[1] <w:
                now[1] += k[1]
                if s[now[0]][now[1]] == 10**5:
                    steps.append([now[0],now[1]])
            else:
                continue
        else:
            continue
    if s[steps[0][0]][steps[0][1]] ==0:
        steps.pop(0)
        continue
    elif s[steps[0][0]][steps[0][1]] >10**4:
        direction =[]
        for l in [[0,1],[1,0],[-1,0],[0,-1]]:
            if steps[0][0]+l[0]>=0 and steps[0][0]+l[0]<h and steps[0][1]+l[1]< w and steps[0][1]+l[1] >=0 and s[steps[0][0]+l[0]][steps[0][1]+l[1]] != "#":
                direction.append(s[steps[0][0]+l[0]][steps[0][1]+l[1]])
        s[steps[0][0]][steps[0][1]] = min(direction)+1
    steps.pop(0)

if s[h-1][w-1] == "#" or s[h-1][w-1] == 10**4:
    print(-1)
else:
    print(white-1 - s[h-1][w-1])

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
maze = [list(input()) for i in range(h)]


q = deque([])
q.append((0,0,0))
f = 0
while len(q) > 0:
  y,x,d = q.popleft()
  if y == h-1 and x == w-1:
      print("-1")
      f = 1
      break
  if x >= 1:
      if maze[y][x-1] == ".":
          q.append((y,x-1,d+1))
          maze[y][x-1] = "checked"
  if x  <= w - 2:
      if maze[y][x-1] == ".":
          q.append((y,x-1,d+1))
          maze[y][x+1] = "checked"
  if y >= 1:
      if maze[y-1][x] == ".":
          q.append((y-1,x,d+1))
          maze[y-1][x] = "checked"
  if y <= h - 2:
      if maze[y-1][x] == ".":
          q.append((y-1,x,d+1))
ans = 0
if f != 1:
  for i in range(h):
    for j in range(w):
      if maze[i][j] == "#":
        ans += 1
print(h*w - ans - d - 1)

Submission status: Runtime Error

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

sq=[list(input()) for i in range(H)]

pos=[[0,0,0]]
g=True

while pos!=[]:
    y,x,depth=pos.pop(0)

    if y==H-1 and x==W-1:
        g=False
        break
    
    if x-1>=0:
        if sq[y][x-1]==".":
            pos.append([y,x-1,depth+1])
            sq[y][x-1]="!"
    if x+1<=W-1:
        if sq[y][x+1]==".":
            pos.append([y,x+1,depth+1])
            sq[y][x+1]="!"
    if y-1>=0:
        if sq[y-1][x]==".":
            pos.append([y-1,x,depth+1])
            sq[y-1][x]="!"
    if y+1<=H-1:
        if sq[y+1][x]==".":
            pos.append([y+1,x,depth+1])

if g==True:
    print(-1)
else:
    temp=0
    for k in range(H):
        for m in range(W):
            if sq[k][m]=="#":
                temp+=1


print(H*W-temp-depth-1)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
sq=[list(input()) for i in range(H)]
ans=False
c=H*W
pos=[[0,0,0]]

while ans==False:
    y,x,depth=pos.pop(0)

    if x==W-1 and y==H-1:
        ans=True

    if 0<=x+1<=W-1:
        if sq[y][x+1]==".":
            pos.append([y,x+1,depth+1])
            sq[y][x+1]="!"
            
    if 0<=x-1<=W-1:
        if sq[y][x-1]==".":
            pos.append([y,x-1,depth+1])
            sq[y][x-1]="!"
            
    if 0<=y+1<=H-1:
        if sq[y+1][x]==".":
            pos.append([y+1,x,depth+1])
            sq[y+1][x]="!"
            
    if 0<=y-1<=H-1:
        if sq[y-1][x]==".":
            pos.append([y-1,x,depth+1])
            sq[y-1][x]="!"
    
    
for j in range(H):
    for k in range(W):
        if sq[j][k]=="#":
            c-=1

print(c-depth-1)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
distance=[[-1]*w for i in range(h)]

cnt=0
for i in maze:
  cnt+=i.count('#')

Q=deque()
Q=((0,0))
distance[0][0]=1

ans=-1

while Q:
  p=Q.pop(0)
  if p[0]==h-1 and p[1]==w-1:
    ans=h*w-cnt-distance[h-1][w-1]
    break

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

  for i in range(4):
    nx=p[0]+dx[i]
    ny=p[1]+dy[i]

    if 0<=nx<h and 0<=ny<w and distance[nx][ny]==-1 and maze[nx][ny]!='#':
      Q.append((nx,ny))
      distance[nx][ny]=distance[p[0]][p[1]]+1

print(ans)

Submission status: Runtime Error

Solution code:
import networkx as nx
import numpy as np

h, w, *X, = open(0).read().split()
h, w = int(h), int(w)

G = nx.grid_2d_graph(h, w)
for i, S in enumerate(X):
    for j, s in enumerate(S):
        if s == '#':
            G.remove_node((i, j))
try:
    path = nx.shortest_path(G, (0, 0), (h-1, w-1))
except NetworkXNoPath:
    print(-1)
else:
    for node in path:
        G.remove_node(node)
    print(len(G.nodes))

Submission status: Runtime Error

Solution code:
import networkx as nx
import numpy as np

h, w, *X, = open(0).read().split()
h, w = int(h), int(w)

G = nx.grid_2d_graph(h, w)
for i, S in enumerate(X):
    for j, s in enumerate(S):
        if s == '#':
            G.remove_node((i, j))
path = nx.shortest_path(G, (0, 0), (h-1, w-1))
for node in path:
    G.remove_node(node)
print(len(G.nodes))

Submission status: Runtime Error

Solution code:

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

maze=[]

count_white=0

for i in range(h):
    maze_row = input()
    maze.append(maze_row)
    
    count_white+=maze_row.count(".")
    
dist = [ [-1]*w for i in range(h)]
goal = [w-1,h-1]
q=queue.Queue()
q.put((0,0,0))

moves = [[0,1], [1,0], [0,-1], [-1,0]]
dmax=-1
while not q.empty():
    
    x,y,d = q.get()
    
    if x==goal[0] and y==goal[1]:
        time=d
        dist[x][y]=d
        dmax=d
        break
    
    if dist[y][x] >= 0:
        continue
    
    else:
        
        dist[y][x]=d
        
        for dx,dy in moves:
            
            if 0<=x+dx<w and 0<=y+dy<h:
                if dist[y+dy][x+dx] == -1 and maze[y+dy][x+dx]!="#":
                
                    q.put((x+dx,y+dy,d+1))
if dmax!=-1:
    print(count_white-dmax-1)
    
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
S = []
white = 0
for i in range(H):
  s = str(input())
  S.append(s)
  white += s.count('.')
  
def main(h, w):
  global H
  global W
  global S
  global l
  tmp = []
  if h < H-1:
    if (S[h+1][w]=='.') and ([h+1, w] not in l):
      tmp.append([h+1, w])
  if w < W-1:
    if (S[h][w+1]=='.') and ([h, w+1] not in l):
      tmp.append([h, w+1])
  if 0 < h:
    if (S[h-1][w]=='.') and ([h-1, w] not in l):
      tmp.append([h-1, w])
  if 0 < w:
    if (S[h][w-1]=='.') and ([h, w-1] not in l):
      tmp.append([h, w-1])
  return tmp
    
cnt = 0
l = [[0, 0]]
tmp = [[0, 0]]
for i in range(10000):
  t = []
  for n in tmp:
    u = main(n[0], n[1])
    l += u
    t += u
  if [H-1, W-1] in t:
    ans = i+2
    break
  else:
    tmp = t
print(white-ans)

Submission status: Runtime Error

Solution code:
print(-1

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

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

grid = []
for _ in range(W):
    grid.append(sys.stdin.readline().strip())

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

q = deque()
q.append((0, 0, 0))
visited = set()
while q:
    x, y, c = q.popleft()
    if x == W-1 and y == H-1:
        break
    if (x, y) in visited:
        continue
    visited.add((x, y))

    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                q.append((nx, ny, c+1))

if x == W-1 and y == H-1:
    print(H*W - black - c - 1)
else:
    print(-1)

Submission status: Runtime Error

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

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

black_cnt=0
for ss in s:
    black_cnt+=ss.count("#")

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

while len(stack)>0:
    #print(stack)
    tmp=stack.popleft()
    if tmp[0]==h-1 and tmp[1]==w-1:
        break

    for (my,mx) in [(1,0),(0,1),(-1,0),(0,-1)]:
        ny=tmp[0]+my
        nx=tmp[1]+mx
        #print(ny,nx)
        if 0<=ny and ny<h and 0<=nx and nx<w:
            #print(ny,nx)
            if s[ny][nx]==".":
                #print(ny,nx,tmp[0],tmp[1],stack)
                s[ny][nx]=s[tmp[0]][tmp[1]]+1
                stack.append((ny,nx))

#for item in s:
 #   print(item)

print(h*w-s[-1][-1]-black_cnt)

Submission status: Runtime Error

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],
]

dists = defaultdict(lambda: defaultdict(lambda: float('inf')))
passed = defaultdict(lambda: defaultdict(lambda: False))

# h,w,dist
dq = deque([(0,0)])
dists[0][0] = 0

while dq:
    h, w = dq.popleft()
    dist = dists[h][w]
    passed[h][w] = True
    
    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 not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if passed[nh][nw]:
            continue
        if sss[nh][nw]:
            continue
        dists[nh][nw] = min(dists[nh][nw], ndist)
        dq.append((nh,nw))

print(H * W - sum(sum(sss,[])) - fdist - 1)

Submission status: Runtime Error

Solution code:
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:]]

from functools import lru_cache
dhw = [
    [0,1],
    [0,-1],
    [1,0],
    [-1,0],
]
passed = set()

@lru_cache(maxsize=None)
def calc(h,w):
    passed.add((h,w))
    if h == H-1 and w == W-1:
        return 1
    ans = float('inf')
    for dh, dw in dhw:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and sss[nh][nw]==0 and ((nh,nw) not in passed or dh+dw>0):
            ans = min(ans, calc(nh,nw) + 1)
    return ans
result = calc(0,0)
if calc(0,0) == float('inf'):
    print(-1)
else:
    print(H * W - sum(map(sum, sss)) - calc(0,0))

Submission status: Runtime Error

Solution code:
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:]]

from functools import lru_cache
dhw = [
    [0,1],
    [0,-1],
    [1,0],
    [-1,0],
]
passed = set()

@lru_cache(maxsize=None)
def calc(h,w):
    passed.add((h,w))
    if h == H-1 and w == W-1:
        return 1
    ans = float('inf')
    for dh, dw in dhw:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and sss[nh][nw]==0 and ((nh,nw) not in passed or dh+dw>0):
            ans = min(ans, calc(nh,nw) + 1)
    return ans

print(H * W - sum(map(sum, sss)) - calc(0,0))

Submission status: Runtime Error

Solution code:
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:]]

from functools import lru_cache
dhw = [
    [0,1],
    [1,0],
    [0,-1],
    [-1,0],
]
passed = set()

@lru_cache(maxsize=None)
def calc(h,w):
    passed.add((h,w))
    if h == H-1 and w == W-1:
        return 1
    ans = float('inf')
    for dh, dw in dhw:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and (nh,nw) not in passed and sss[nh][nw]==0:
            ans = min(ans, calc(nh,nw) + 1)
    return ans

print(H * W - sum(map(sum, sss)) - calc(0,0))

Submission status: Runtime Error

Solution code:
from collections import deque
H,W = map(int,input().split())
grid = [0] * H
num_black = 0
for i in range(H):
    s = input()
    for j in range(len(s)):
        if s[j] == '#':
            num_black += 1
    grid[i] = list(s)
time_grid = [[-1] * W for _ in range(H)]
time_grid[0][0] = 0
queue = deque()
queue.append([0,0,0])
while queue:
    y,x,t = queue.popleft()
    for next_y, next_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0 <= next_x < W and 0 <= next_y < H and grid[next_y][next_x] == '.':
            queue.append([next_y,next_x,t+1])
            time_grid[next_y][next_x] = t+1
            grid[next_y][next_x] = '#'
if time_grid[H][W] != -1:
    print(H*W-time_grid[-1][-1]-1-num_black)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W = map(int,input().split())
grid = [0] * H
num_black = 0
for i in range(H):
    s = input()
    for j in range(len(s)):
        if s[j] == '#':
            num_black += 1
    grid[i] = list(s)
time_grid = [[0] * W for _ in range(H)]
queue = deque()
queue.append([0,0,0])
while queue:
    y,x,t = queue.popleft()
    for next_y, next_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if next_y == H-1 and next_x == W-1:
            time = t+1
            break
        if 0 <= next_x < W and 0 <= next_y < H and grid[next_y][next_x] == '.':
            queue.append([next_y,next_x,t+1])
            grid[next_y][next_x] = '#'
print(H*W-time-1-num_black)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
c=[list(input()) for _ in range(h)]
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dis=[[-1]*w for _ in range(h)]
que=deque()
def bfs(x,y):
  que.append([x,y])
  min_dis[x][y]=0
  while que:
    sh,sw=que.popleft()
    for dh,dw in dhdw:
      nh,nw = sh+dh,sw+dw
      if not(0<=nh<=h-1) or not(0<=nw<=w-1) or min_dis[nh][nw]!=-1 or c[nh][nw]=='#':
        continue
      min_dis[nh][nw]=min_dis[sh][sw]+1
      que.append([nh,nw])
      if [nh,nw]==[h-1,w-1]:
        return min_dis[sh][sw]+1
a=bfs(0,0) or ans-2
ans=0
for i in c:
  ans+=i.count(".")
print(ans-1-a)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
c=[list(input()) for _ in range(h)]
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dis=[[-1]*w for _ in range(h)]
que=deque()
def bfs(x,y):
  que.append([x,y])
  min_dis[x][y]=0
  while que:
    sh,sw=que.popleft()
    for dh,dw in dhdw:
      nh,nw = sh+dh,sw+dw
      if not(0<=nh<=h-1) or not(0<=nw<=w-1) or min_dis[nh][nw]!=-1 or c[nh][nw]=='#':
        continue
      min_dis[nh][nw]=min_dis[sh][sw]+1
      que.append([nh,nw])
      if [nh,nw]==[h-1,w-1]:
        return min_dis[sh][sw]+1
a=bfs(0,0)
ans=0
for i in c:
  ans+=i.count(".")
print(ans-1-a)

Submission status: Runtime Error

Solution code:
10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Submission status: Runtime Error

Solution code:
from collections import deque

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

maze = [list(input()) for _ in range(h)]
step = [[0] * w for _ in range(h)]
direction = [[1,0],[-1,0],[0,1],[0,-1]]

def bfs(maze,h,w):
    start = [0,0]
    #キューで座標保存
    q = deque([start])
    while q:
        x, y = q.popleft()
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == "." and step[nx][ny] == 0:
                q.append([nx,ny])
                step[nx][ny] = step[x][y] + 1
        if step[h-1][w-1] != 0:
            return step[h-1][w-1]

#壁の数
wall = 0
for i in maze:
    for j in i:
        if j == "#":
            wall += 1

ans = h * w - wall - (bfs(maze,h,w) + 1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

h, w = map(int, input().split())
Map = [['#'] * (w+2)]
Map += [['#'] + list(input()) + ['#'] for _ in range(h)]
Map += [['#'] * (w+2)]

cnt = 0

for i in range(h+2):
    for j in range(w+2):
        if Map[i][j] == '.':
            cnt += 1
            
stack = deque([(1,1)])
Map[1][1] = 1
moved = [[0,1], [0,-1], [1,0], [-1,0]]

while stack:
    x, y = stack.popleft()
    for s, t in moved:
        if Map[x+s][y+t] == '.':
            stack.append((x+s, y+t))
            Map[x+s][y+t] = Map[x][y] + 1
            
goal = Map[-2][-2]

print(cnt - goal)

Submission status: Runtime Error

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

h,w = map(int,input().split())
MAP = [list(input().rstrip()) for i in range(h)]  #rstripで最後の/nを省ける
sharp = 0
for i in range(h):
  sharp += MAP[i].count("#")
#print(sharp)

#必要なもの MAP(list), MOVE(list), STACK(deque)
MAP[0][0]=1
MOVE = [[1,0],[-1,0],[0,1],[0,-1]]
STACK = deque([(0,0)])
while STACK:
  y, x = STACK.popleft()
  for dy,dx in MOVE:
    ny = y + dy
    nx = x + dx
    if not(0 <= ny < h) or not(0 <= nx < w) or MAP[ny][nx]!='.':
      continue
    else:
      STACK.append((ny,nx))
      MAP[ny][nx] = MAP[y][x] + 1

ans = h*w -MAP[h-1][w-1]-sharp
#print(MAP)
print(ans)

Submission status: Runtime Error

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

city = []

for _ in range(H):
    city.append(list(input()))

dist = [[float("inf") for _ in range(W)] for _ in range(H)]

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

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

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

while len(queue) > 0:
    now_x, now_y = queue.popleft()

    for dx_, dy_ in zip(dx, dy):

        adj_x = now_x + dx_
        adj_y = now_y + dy_

        if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
            continue

        if city[adj_y][adj_x] == "#":
            continue

        if dist[adj_y][adj_x] > H*W:
            dist[adj_y][adj_x] = dist[now_x][now_y] + 1
            queue.append((adj_x, adj_y))
            dist_count[dist[adj_y][adj_x]] += 1

#すぬけ君がどうやってもたどり着けない場合
if dist[H-1][W-1] > H*W:
    print(-1)
    sys.exit()

#すぬけ君がたどり着ける場合
max_dist = dist[H-1][W-1]

ans = 0
for i in range(1, max_dist+1):
    ans += dist[i] - 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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



def bfs(maze,maze_s,sy,sx):
  maze_s[sy][sx] = 0
  queue = deque([[sy,sx]])
  while queue:
    y,x = queue.popleft()
    if maze[y][x] == "g":
      return maze_s[y][x]
    else:
      for j,k in [(0,1),(0,-1),(1,0),(-1,0)]:
        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 maze_s[new_y][new_x] == -1:
            maze_s[new_y][new_x] = maze_s[y][x] + 1
            queue.append([new_y,new_x])

maze_s = list([-1] * W for i in range(H))
count = 0
for row in maze:
  count += row.count(".")

maze[H-1][W-1] = "g"

ans = count - bfs(maze,maze_s,0,0) -1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
def cango(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
    
q = deque([(-1,-1,0,0,0)]) 
been = [[False]*W for _ in range(H)]

while q:
    x_old,y_old,x_now,y_now,time = q.popleft()
    been[x_now][y_now]=True
    cand = cango(x_now,y_now)
    
    if x_now==H-1 and y_now==W-1:
        break
    
    for x_new,y_new in cand:
        if not been[x_new][y_new] and s[x_new][y_new]==".":
            q.append((x_now,y_now,x_new,y_new,time+1))

print( sum(ss.count(".") for ss in s)-time-1 )

Submission status: Runtime Error

Solution code:
def read():
    H, W = map(int, input().split(' '))
    Ss = []
    for _ in range(H):
        Ss.append(input())
    return H, W, Ss

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

def add(p1, p2):
    return (p1[0] + p2[0], p1[1] + p2[1])

def ans(H, W, Ss):
    if Ss[0][0] == '#':
        print('0,0 #')
        return -1
    ds =[ [-1 for _ in range(W)] for _ in range(H)]
    ds[0][0] = 1
    q = [(0, 0)]
    while q:
        p = q.pop()
        d = ds[p[1]][p[0]]
        for dr in DIRS:
            x, y = add(p, dr)
            if x < 0 or x >= W or y < 0 or y >= H:
                continue # 範囲外へは移動できない
            if Ss[y][x] == '#':
                continue # 行き止まりへは移動できない
            if ds[y][x] >= 0 and ds[y][x] < d + 1: # すでに訪れていて短縮にもなっていない
                continue
            ds[y][x] = d + 1
            q.append((x, y))
    if ds[H-1][W-1] < 0:
        return -1
    # 白マスを数える
    ws = sum([l.count('.') for l in Ss])
    return ws - ds[H-1][W-1]

if __name__ == '__main__':
	H, W, Ss = read()
    print(ans(H, W, Ss))

Submission status: Runtime Error

Solution code:
def MI(): return map(int, input().split())
from collections import deque
H,W=MI()
#Map=[[]*W for _ in range(H)]
Map=[]
white=0
for _ in range(H):
  Map.append(list(input()))
def bfs():
  dx=[-1,0,1,0]
  dy=[0,-1,0,1]
  INF=float('inf')
  dist=[[INF]*W for _ in range(H)]
  dist[0][0]=0
  que=deque()
  que.append((0,(0,0)))

  while que:
    d,(x,y) =que.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='#':
          if dist[nx][ny]==INF:
            dist[nx][ny]=d+1
            que.append((d+1,(nx,ny)))
  return dist
res=bfs()  
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
ans=white-res[H-1][W-1]-1
if 0<ans<INF:
  print(ans)
else:
  print(-1)