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:
#create date: 2020-07-03 14:46

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    h, w = na()
    g = [[1] * (w+2)]
    white = 0
    for i in range(h):
        r = ns()
        white += r.count(".")
        g.append([1] + [1 if s=="#" else 0 for s in r] + [1])
    g.append([1] * (w+2))
    q = deque([[1,1]])
    move = ((1, 0), (-1, 0), (0, 1), (1, 0))
    while q:
        x, y = q.popleft()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if g[nx][ny] > 0:
                continue
            g[nx][ny] = g[x][y] + 1
            q.append((nx, ny))
    if g[h][w] == 0:
        print(-1)
    else:
        print(white - g[h][w] - 1)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#create date: 2020-07-03 14:46

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    h, w = na()
    g = [[1] * (w+2)]
    white = 0
    for i in range(h):
        r = ns()
        white += r.count(".")
        g.append([1] + [1 if s=="#" else 0 for s in r] + [1])
    g.append([1] * (w+2))
    q = deque([[1,1]])
    move = ((1, 0), (-1, 0), (0, 1), (1, 0))
    while q:
        x, y = q.popleft()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if g[nx][ny] > 0:
                continue
            g[nx][ny] = g[x][y] + 1
            q.append((nx, ny))
    print(white - g[h][w] - 1)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(sy, sx, gy, gx):
    # yが下方向，xが右方向
    d = [[float("inf")] * w for _ in range(h)]

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

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

    while que:

        p = que.popleft()

        if p[0] == gy and p[1] == gx:
            break

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

            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    return d[gy][gx]


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

res = 0
for y in range(h):
    for x in range(w):
        if maze[y][x] == '#':
            res += 1

print(h * w - res - bfs(0, 0, h - 1, w - 1) - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(sy, sx, gy, gx):
    # yが下方向，xが右方向
    d = [[float("inf")] * w for _ in range(h)]

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

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

    while que:

        p = que.popleft()

        if p[0] == gy and p[1] == gx:
            break

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

            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    return d[gy][gx]


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

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

print(h * w - res - bfs(0, 0, h - 1, w - 1) - 1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S =[]
for _ in range(H):
    a = input()
    S.append(a)
count =0
for i in range(H):
    for j in range(W):
        if S[i][j] =='.':
            count += 1
from collections import deque

seen = [[False]*(W) for _ in range(H)]
seen[0][0] = True
dq = deque([(0,0,1)])
d = [(1,0),(0,1),(0,-1),(-1,0)]
while dq:
    x,y,cnt = dq.popleft()
    if x ==H-1 and y ==W-1:
        print(count-cnt);exit()
    for dx,dy in d:
        if 0<=x+dx<H and 0<=y+dy<W and seen[x+dx][y+dy] ==False:
            seen[x+dx][y+dy] = True
            dq.append((x+dx,y+dy,cnt+1))
print(-1)

Submission status: Wrong Answer

Solution code:
# %%
H, W = [int(i) for i in input().split()]
maze = [[] for _ in range(H)]

num_black = 0
for i in range(H):
    temp = input()
    for j in temp:
        maze[i].append(j)
        if j == "#":
            num_black += 1

# %%
import copy, collections

maze_copy = copy.deepcopy(maze)
maze_copy[-1][-1] = -1
color = [["W"] * W for _ in range(H)]


def BFS(Y, X):
    vec = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    color[Y][X] = "G"
    que = collections.deque()
    maze_copy[Y][X] = 1
    que.append([Y, X])

    while len(que) != 0:
        u = que.popleft()
        for y, x in vec:
            temp_x = u[1] + x
            temp_y = u[0] + y
            if (0 <= temp_x < W and 0 <= temp_y < H
                    and maze_copy[temp_y][temp_x] == "." and color[temp_y][temp_x] == "W"):
                color[temp_y][temp_x] = "G"
                maze_copy[temp_y][temp_x] = maze_copy[u[0]][u[1]] + 1
                que.append([temp_y, temp_x])


BFS(0, 0)
if maze_copy[-1][-1] == -1:
    print(-1)
else:
    print(W * H - num_black - maze_copy[-1][-1])

Submission status: Wrong Answer

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

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
visit = set()                                 # 訪れたかどうかをメモ ([]をつけないとtupleが展開されて各要素をsetに入れる操作になってしまう)
next_set = deque()                            # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる

def debug(p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    debug_grid[start[0]][start[1]] = "S"
    debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(debug_grid[debug_h][debug_w] for debug_w in range(W)))

def search(start=(0,0), goal=(None,None)):      #
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set.append((start, 0))                 # スタート地点を決める。第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == "#":         # 壁があったら進まない
                continue
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
cnt = 0

for h in range(H):
    grid.append(input())
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)
if search(start,goal) == -1:
    print(-1)
else:
    print(cnt - search(start,goal) - 1)

Submission status: Wrong Answer

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

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
visit = set()                                 # 訪れたかどうかをメモ ([]をつけないとtupleが展開されて各要素をsetに入れる操作になってしまう)
next_set = deque()                            # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる

def debug(p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    debug_grid[start[0]][start[1]] = "S"
    debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(debug_grid[debug_h][debug_w] for debug_w in range(W)))

def search(start=(0,0), goal=(None,None)):      #
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set.append((start, 0))                 # スタート地点を決める。第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == "#":         # 壁があったら進まない
                continue
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
cnt = 0

for h in range(H):
    grid.append(input())
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)
print(cnt - search(start,goal)-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = [list(input()) for _ in range(H)]

    maze = [[f_inf] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([[0, 0]])
    while que:
        h, w = que.popleft()
        for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W or grid[next_h][next_w] == "#":
                continue
            if maze[next_h][next_w] > maze[h][w] + 1:
                maze[next_h][next_w] = maze[h][w] + 1
                que.append([next_h, next_w])
    mi = maze[H - 1][W - 1] + 1

    cnt = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "#":
                cnt += 1
    res = H * W - cnt - mi
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
    q = deque([[sy, sx]])
    dist = [[float('inf')]*(W) for _ in range(H)]
    dist[sy][sx] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == '.' and dist[ny][nx] == float('inf'):
                dist[ny][nx] = dist[y][x] + 1
                q += [[ny, nx]]

    return dist

d = bfs(0, 0)

ans = H*W 
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            ans -= 1

ans -= d[-1][-1] + 1
print(ans)

Submission status: Wrong Answer

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


def main():
  H, W = list(map(int, input().split()))
  M = [input()[:-1] for _ in range(H)]

  white = 0
  black = 0
  for i in range(H):
    for j in range(W):
      if M[i][j] == '.':
        white += 1
      elif M[i][j] == '#':
        black += 1

  start = (0, 0)
  q = deque()
  q.append(start)
  is_visited = [[0]*W for _ in range(H)]
  d = [[float('inf')]*W for _ in range(H)]
  d[0][0] = 0

  while len(q):

    ur, uc = q.popleft()

    for vr, vc in [(ur, uc+1), (ur, uc-1), (ur-1, uc), (ur+1, uc)]:
      if 0 <= vr < H and \
         0 <= vc < W and \
         not(is_visited[vr][vc]) and not(M[vr][vc] == '#'):

        q.append((vr, vc))
        is_visited[vr][vc] = True
        d[vr][vc] = d[ur][uc] + 1

  print(white - (d[H-1][W-1] + 1))


if(__name__ == '__main__'):
  main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in  range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            cnt += 1
dist = [[-1]*W for _ in range(H)]
dist[0][0] = 0
que = deque([[0,0]])
while que:
    h,w = que.pop()
    for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
        nh,nw = h+dh,w+dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            continue
        if dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w]+1
            que.appendleft([nh,nw])
print(H*W-cnt-dist[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[-1 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
now = [0,0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    now = queue.popleft()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

print(-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()

    for i in range(4):
        if now[0] + y[i] < 0 or now[0] + y[i] >= n or now[1] + x[i] < 0 or now[1] + x[i] >= m:
            continue
        if a[now[0]+y[i]][now[1]+x[i]] == '.':
            queue.append([now[0]+y[i],now[1]+x[i]])
            b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])
    a[now[0]][now[1]] = "#"

if b[now[0]][now[1]] == 100000:
    print(-1)
    exit()

ans = n * m - (b[n-1][m-1] + count)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()

    for i in range(4):
        if now[0] + y[i] < 0 or now[0] + y[i] >= n or now[1] + x[i] < 0 or now[1] + x[i] >= m:
            continue
        if a[now[0]+y[i]][now[1]+x[i]] == '.':
            queue.append([now[0]+y[i],now[1]+x[i]])
            b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])
    a[now[0]][now[1]] = "#"
    
    if now == [n-1,m-1]:
        break

if b[now[0]][now[1]] == 100000:
    print(-1)
    exit()

ans = n * m - (b[n-1][m-1] + count)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


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

white_cnt = 0
grid = [[] for i in range(H+2)]
check = [[0] * (W+2) for i in range(H+2)]
grid[0] = ['#']*(W+2)
for i in range(1, H+1):
    w = list(input())
    white_cnt += w.count('.')
    grid[i] = ['#'] + w + ['#']
grid[-1] = ['#']*(W+2)

mv_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que_hwc = deque([(1, 1, 1)])
check[1][1] = 1
while que_hwc:
    hwc = que_hwc.popleft()
    h = hwc[0]
    w = hwc[1]
    cnt = hwc[2]
    if h == H and w == W:
        print(white_cnt-cnt)
        exit(0)

    for mv in mv_list:
        mv_h = h + mv[0]
        mv_w = w + mv[1]
        if grid[mv_h][mv_w] == '.' and check[mv_h][mv_w] != 1:
            check[mv_h][mv_w] = 1
            que_hwc.append((mv_h, mv_w, cnt+1))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

s = [[] for _ in range(h)]
dis = [[-1] * w for _ in range(h)]

for i in range(h):
    s[i] = input()

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

q = deque()
q.append([0, 0, 1])  # x,y,d
dis[0][0] = 1

while len(q) > 0:
    x, y, d = q.popleft()
    dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy
        if 0 > nx or w <= nx or 0 > ny or h <= ny:
            continue
        if dis[ny][nx] != -1 or s[ny][nx] == "#":
            continue
        q.append([nx, ny, d + 1])
        dis[y][x] = d + 1

if dis[h - 1][w - 1] == -1:
    print(-1)
else:
    print(white_cnt - dis[h - 1][w - 1])

Submission status: Wrong Answer

Solution code:
H, W = 10, 37

ARR = [
    ".....................................",
    "...#...####...####..###...###...###..",
    "..#.#..#...#.##....#...#.#...#.#...#.",
    "..#.#..#...#.#.....#...#.#...#.#...#.",
    ".#...#.#..##.#.....#...#.#.###.#.###.",
    ".#####.####..#.....#...#..##....##...",
    ".#...#.#...#.#.....#...#.#...#.#...#.",
    ".#...#.#...#.##....#...#.#...#.#...#.",
    ".#...#.####...####..###...###...###..",
    ".....................................",
]

H, W = map(int, input().split())
ARR = []

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


def calculate(h, w, arr):
    total = h * w
    distance = h + w - 1
    alreadyPaiting = 0

    for s in arr:
        for ss in s:
            if ss == "#":
                alreadyPaiting += 1

    if total - alreadyPaiting <  distance:
        return -1
    else:
        return total - distance - alreadyPaiting


result = calculate(H, W, ARR)

print(result)

Submission status: Wrong Answer

Solution code:
H, W = 10, 37

ARR = [
    ".....................................",
    "...#...####...####..###...###...###..",
    "..#.#..#...#.##....#...#.#...#.#...#.",
    "..#.#..#...#.#.....#...#.#...#.#...#.",
    ".#...#.#..##.#.....#...#.#.###.#.###.",
    ".#####.####..#.....#...#..##....##...",
    ".#...#.#...#.#.....#...#.#...#.#...#.",
    ".#...#.#...#.##....#...#.#...#.#...#.",
    ".#...#.####...####..###...###...###..",
    ".....................................",
]

H, W = map(int, input().split())
ARR = []

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


def calculate(h, w, arr):
    total = h * w
    distance = h + w - 1
    alreadyPaiting = 0

    for s in arr:
        for ss in s:
            if ss == "#":
                alreadyPaiting += 1

    if total - alreadyPaiting <=  distance:
        return distance - (total - alreadyPaiting)
    else:
        return total - distance - alreadyPaiting


result = calculate(H, W, ARR)

print(result)

Submission status: Wrong Answer

Solution code:
H, W = 10, 37

ARR = [
    ".....................................",
    "...#...####...####..###...###...###..",
    "..#.#..#...#.##....#...#.#...#.#...#.",
    "..#.#..#...#.#.....#...#.#...#.#...#.",
    ".#...#.#..##.#.....#...#.#.###.#.###.",
    ".#####.####..#.....#...#..##....##...",
    ".#...#.#...#.#.....#...#.#...#.#...#.",
    ".#...#.#...#.##....#...#.#...#.#...#.",
    ".#...#.####...####..###...###...###..",
    ".....................................",
]

H, W = map(int, input().split())
ARR = []

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


def calculate(h, w, arr):
    total = h * w
    distance = h + w - 1
    alreadyPaiting = 0

    for s in arr:
        for ss in s:
            if ss == "#":
                alreadyPaiting += 1
    return total - distance - alreadyPaiting


result = calculate(H, W, ARR)

print(result)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

    return True

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

    print(q)

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

    cx, cy = q.popleft()

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

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

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

    print(Grid)

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from sys import stdin

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

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