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: Wrong Answer

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 -= dep[(h,w)]
print(ans)

Submission status: Wrong Answer

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)]
ans = 0
for elm in grid:
    ans += elm.count(0)

q = col.deque([(1,1)])
know = col.defaultdict(int)

depth = 0
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)]:
        x,y = next[0],next[1]
        if grid[x][y]: continue
        if know[next]: continue
        else: know[next] = 1; q.append(next)

ans -= depth
print(ans)

Submission status: Wrong Answer

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))

    ans = H*W - black_cnt - visited[H][W] - 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    print(h*w-totalsharp-visited[h-1][w-1])
resolve()

Submission status: Wrong Answer

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
    print(h*w-totalsharp-visited[h-1][w-1])

resolve()

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W = map(int,readline().split())
grid = ['#']*(W+2)
for _ in range(H):
  grid += ['#'] + list(map(str,readline().decode().rstrip())) + ['X']
grid += ['#']*(W+2)

dist = [-1]*((H+2)*(W+2)-1)

s = W + 3
g = (H+1)*(W+2)-2

def bfs():
  while q:
    x = q.popleft()
    if x == g:
      return
    for dx in (1,W+2,-1,-W-2):
      if dist[x+dx] == -1 and grid[x+dx] =='.':
        dist[x+dx] = dist[x]+1
        q.append(x+dx)

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

print(grid.count('.')-dist[g]-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
def bfs():
    d=[[float("inf")]*w for i in range(h)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=deque()
    que.append((0,0))
    d[0][0]=0
    while que:
        p=que.popleft()
        if p[0]==h-1 and p[1]==w-1:
            break
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx<h and 0<=ny<w and s[nx][ny]!="#" and d[nx][ny]==float("inf"):
                d[nx][ny]=d[p[0]][p[1]]+1
                que.appendleft((nx,ny))
    return d[h-1][w-1]
ans=h*w
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            ans-=1
if bfs()==float("inf"):
    print(-1)
    exit()
print(ans-bfs()-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
def bfs():
    d=[[float("inf")]*w for i in range(h)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=deque()
    que.append((0,0))
    d[0][0]=0
    while que:
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx<h and 0<=ny<w and s[nx][ny]!="#" and d[nx][ny]==float("inf"):
                d[nx][ny]=d[p[0]][p[1]]+1
                que.appendleft((nx,ny))
    return d[h-1][w-1]
ans=h*w
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            ans-=1
if bfs()==float("inf"):
    print(-1)
    exit()
print(ans-bfs()-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Submission status: Wrong Answer

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

Submission status: Wrong Answer

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

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

    d[0][0] = 0

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

    return h*w - d[h-1][w-1] - 1 - sum(1 for i in range(h) for j in range(w) if map[i][j] == "#")

print(bfs())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

from collections import deque
d = deque()

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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





        
    
main()

Submission status: Wrong Answer

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	ol = queue.Queue()
	m=[input() for _ in range(h)]
	b = [[-1]*w for _ in range(h)]
	b[0][0]=1
	ol.put(0)
	while not ol.empty():
		p = ol.get()
		x, y = p//1000, p%1000
		for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
			if x+dx<0 or x+dx>=h or y + dy <0 or y+dy >= w:
				continue
			if m[x+dx][y+dy]=='#':
				continue
			if b[x+dx][y+dy]>=0:
				continue
			b[x+dx][y+dy]=b[x][y]+1
			ol.put((x+dx)*1000+(y+dy))
	#print(b)
	return sum([s.count('.') for s in m])- b[-1][-1]
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
sharp = 0
for i in range(h):
	t = input()
	sharp += t.count("#")
	s.append(t)

queue = deque([[0,0]])

visited = [[-1 for i in range(w)] for j in range(h)]
visited[0][0] = 0
d = [(1,0),(0,1),(-1,0),(0,-1)]
while queue:
	i, j = queue.popleft()
	for n, m in d:
		x = i+n
		y = j+m
		if x < 0 or x >= h or y < 0 or y >= w or s[x][y] == "#" or visited[x][y] != -1:
			continue
		visited[x][y] = visited[i][j] + 1
		queue.append([x,y])
ans = h*w-visited[h-1][w-1]-1-sharp
print (ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import numpy as np


def main():
    H, W = map(int, input().split())
    s_x = 1
    s_y = 1
    g_x = H
    g_y = W
    dp = - np.ones((H+2, W+2))
    black = 0
    for i in range(1, H+1):
        line = input()
        for j in range(1, W+1):
            if line[j - 1] == '.':
                dp[i][j] = 0
            else:
                black += 1
    queue = deque()
    queue.append((s_x, s_y))
    while len(queue) != 0:
        now_x, now_y = queue.popleft()
        for x in range(-1, 2):
            for y in range(-1, 2):
                if (x + y) % 2 == 0:
                    continue
                next_x = now_x + x
                next_y = now_y + y
                if dp[next_x][next_y] == 0:
                    dp[next_x][next_y] = dp[now_x][now_y] + 1
                    queue.append((next_x, next_y))
    print(int(H * W - black - dp[g_x][g_y] - 1))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[0]*w for _ in range(h)]
b[0][0]=1
d=[(0,0)]
while d:
    y,x=d.pop(0)
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if h>t>=0<=u<w and a[t][u]=="." and b[t][u]<1:
            d+=[(t,u)]
            b[t][u]=b[y][x]+1
print(max(-1,sum([i.count(".") for i in a])-b[-1][-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque

h ,w = map(int, input().split())
s = ['$'*(w+2)] * (h+2)
cnt = 0
for i in range(1,h+1):
    s[i] = '$' + input() + '$'
    cnt += s[i].count('.')

dist = [[-1]*(w+2) for _ in range(h+2)] # スタートからの距離の記録をするリスト
dist[1][1] = 0 # スタート地点を0 にする
q = deque()
q.append((1,1))
while q:
    x, y = q.popleft() # 探索地点を取り出す

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    for i in range(4):
        nx = x + vx[i]
        ny = y + vy[i]
        if s[nx][ny] == '$' or s[nx][ny] == '#': continue # 壁なら通れないね！
        if dist[nx][ny] != -1: continue # もう最短距離がわかってるなら飛ばす
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx, ny)) # 新しい地点の周りも探索したいからキューに入れておく

print(cnt - dist[h][w]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h ,w = map(int, input().split())
s = ['$'*(w+2)] * (h+2)
cnt = 0
for i in range(1,h+1):
    s[i] = '$' + input() + '$'
    cnt += s[i].count('#')

dist = [[-1]*(w+2) for _ in range(h+2)] # スタートからの距離の記録をするリスト
dist[1][1] = 0 # スタート地点を0 にする
q = deque()
q.append((1,1))
while q:
    x, y = q.popleft() # 探索地点を取り出す

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    for i in range(4):
        nx = x + vx[i]
        ny = y + vy[i]
        if s[nx][ny] == '$' or s[nx][ny] == '#': continue # 壁なら通れないね！
        if dist[nx][ny] != -1: continue # もう最短距離がわかってるなら飛ばす
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx, ny)) # 新しい地点の周りも探索したいからキューに入れておく

print(h*w - (dist[h][w]+1) - cnt)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [input() for i in range(h)]
reach = [[False]*w for i in range(h)]
reach[0][0]=True
from collections import deque
q = deque([(0,0)])

goal = False
while q:
    x,y = q.popleft()
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+i<h and 0<=y+j<w:
            if x+i==h-1 and y+j==w-1:
                goal = True
                break
            if not reach[x+i][y+j] and s[x+i][y+j]=='.':
                reach[x+i][y+j] = True
                q.append([x+i,y+j])

c = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            c += 1

if goal:
    print(c-h-w+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [input() for i in range(h)]
reach = [[False]*w for i in range(h)]
reach[0][0]=True
from collections import deque
q = deque([(0,0)])

goal = False
while q:
    x,y = q.popleft()
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+i<h and 0<=y+j<w:
            if x+i==h-1 and y+j==w-1:
                goal = True
                break
            if not reach[x+i][y+j] and s[x+i][y+j]=='.':
                reach[x+i][y+j] = True
                q.append([x+i,y+j])

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

if goal:
    print(h*w-c-h-w+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
u = [list(input()) for _ in range(h)]

from collections import deque
q = deque([(0,0)])
dist = [[-1]*w for _ in range(h)]
dist[0][0]=0

while q:
    (i,j) = q.popleft()
    if 0<=i-1<h:
        if u[i-1][j]=='.' and dist[i-1][j]==-1:
            q.append((i-1,j))
            dist[i-1][j]=dist[i][j]+1
    if 0<=i+1<h:
        if u[i+1][j]=='.' and dist[i+1][j]==-1:
            q.append((i+1,j))
            dist[i+1][j]=dist[i][j]+1
    if 0<=j-1<w:
        if u[i][j-1]=='.' and dist[i][j-1]==-1:
            q.append((i,j-1))
            dist[i][j-1]=dist[i][j]+1
    if 0<=j+1<w:
        if u[i][j+1]=='.' and dist[i][j+1]==-1:
            q.append((i,j+1))
            dist[i][j+1]=dist[i][j]+1

count=0
for i in range(h):
    for j in range(w):
        if u[i][j]=='.':
            count+=1

print(count-dist[h-1][w-1]-1)