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 sys
import queue

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

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
s = ['' for i in range(H)]
white = H*W
black = 0
for i in range(H):
    s[i] = input()
    black += s[i].count('#')
white -= black
direction = [[1,0],[0,1],[-1,0],[0,-1]]
q = [[0,0,0]]

mass = [[-1 for i in range(W)] for j in range(H)]
while len(q) > 0:
    tmp = [y,x,d] = q.pop(0)
    if mass[y][x] >= 0: 
        continue
    mass[y][x] = d
    for [dy,dx] in direction:
        ny = y + dy
        nx = x + dx
        if 0 <= ny and ny < H and 0 <= nx and nx < W:
            if s[ny][nx] == '#' or mass[ny][nx] >= 0:
                continue
            q.append([ny,nx,d+1])
# for i in mass:
#     print(i)
print(white - mass[H-1][W-1] - 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
h, w = list(map(int, input().split()))
s = [list(map(str, list(input()))) for i in range(h)]  # 文字列の二次元配列入力
cnt_sharp = 0
G = defaultdict(lambda: [])
vec = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            cnt_sharp += 1
        for dy, dx in vec:
            if 0 <= i+dy < h and 0 <= j+dx < w and s[i+dy][j+dx] == '.':
                G[(i+dy, j+dx)].append((i, j))
                G[(i, j)].append((i+dy, j+dx))
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
N = h*w
dist = defaultdict(lambda: -1)
que = deque([(0, 0)])
dist[(0, 0)] = 1
while que:
    v = que.popleft()
    d = dist[v]
    for ww in G[v]:
        if dist[ww] > -1:
            continue
        dist[ww] = d + 1
        que.append(ww)
if dist[(h-1, w-1)] == -1:
    print(-1)
else:
    print(h*w-cnt_sharp-dist[(h-1, w-1)])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
h, w = list(map(int, input().split()))
s = [list(map(str, list(input()))) for i in range(h)]  # 文字列の二次元配列入力
cnt_sharp = 0
G = defaultdict(lambda: [])
vec = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            cnt_sharp += 1
        for dy, dx in vec:
            if 0 <= i+dy < h and 0 <= j+dx < w and s[i+dy][j+dx] == '.':
                G[(i+dy, j+dx)].append((i, j))
                G[(i, j)].append((i+dy, j+dx))
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
N = h*w
dist = defaultdict(lambda: -1)
que = deque([(0, 0)])
dist[(0, 0)] = 1
while que:
    v = que.popleft()
    d = dist[v]
    for ww in G[v]:
        if dist[ww] > -1:
            continue
        dist[ww] = d + 1
        que.append(ww)
print(h*w-cnt_sharp-dist[(h-1, w-1)])

Submission status: Wrong Answer

Solution code:
from collections import deque


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

    black = 0

    for f in field:
        for s in f:
            if s == "#":
                black += 1

    dir_h = [0, 0, 1, -1]
    dir_w = [1, -1, 0, 0]

    print(bfs(H, W, field, dir_h, dir_w))


def bfs(H, W, field, dir_h, dir_w):
    q = deque([])
    seen = [[-1 for _ in range(W)] for _ in range(H)]

    q.append([0, 0])
    seen[0][0] = 1

    while q:
        h, w = q.popleft()

        for dh, dw in zip(dir_h, dir_w):
            nh, nw = h + dh, w + dw

            if nh < 0 or nh >= H or nw < 0 or nw >= W:
                continue
            elif field[nh][nw] == "#":
                continue
            elif seen[nh][nw] != -1:
                continue

            seen[nh][nw] = seen[h][w] + 1
            q.append([nh, nw])

    if seen[H - 1][W - 1] == -1:
        print(-1)
        exit()

    return seen[H - 1][W - 1]


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


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

    black = 0

    for f in field:
        for s in f:
            if s == "#":
                black += 1

    dir_h = [0, 0, 1, -1]
    dir_w = [1, -1, 0, 0]

    print(H * W - black - bfs(H, W, field, dir_h, dir_w))


def bfs(H, W, field, dir_h, dir_w):
    q = deque([])
    seen = [[-1 for _ in range(W)] for _ in range(H)]

    q.append([0, 0])
    seen[0][0] = 1

    while q:
        h, w = q.popleft()

        for dh, dw in zip(dir_h, dir_w):
            nh, nw = h + dh, w + dw

            if nh < 0 or nh >= H or nw < 0 or nw >= W:
                continue
            elif field[nh][nw] == "#":
                continue
            elif seen[nh][nw] != -1:
                continue

            seen[nh][nw] = seen[h][w] + 1
            q.append([nh, nw])

    return seen[H - 1][W - 1]


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = [int(i) - 1 for i in input().split()]
ans  = 0
maze = []
for i in range(h+1):
  s = list(input())
  maze.append(s)
  ans += s.count(".")

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

while pos:
  y,x,b = pos.pop()
  for ny,nx in [[1,0],[-1,0],[0,1],[0,-1]]:
    if y+ny==h and x+nx==w:
      print(ans-b-2)
      exit()
    if 0<=y+ny<=h and 0<=x+nx<=w and maze[y+ny][x+nx] == ".":
      pos.append([y+ny,x+nx,b+1])
      maze[y+ny][x+nx] = "#"
print(-1)

Submission status: Wrong Answer

Solution code:
h,w = [int(i) - 1 for i in input().split()]
ans  = 0
maze = []
for i in range(h+1):
  s = list(input())
  maze.append(s)
  ans += s.count(".")

pos = [[0,0,0]]

while pos:
  y,x,b = pos.pop()
  for ny,nx in [[1,0],[-1,0],[0,1],[0,-1]]:
    if y+ny==h and x+nx==w:
      print(ans-b-2)
      exit()
    if 0<=y+ny<=h and 0<=x+nx<=w and maze[y+ny][x+nx] == ".":
      pos.append([y+ny,x+nx,b+1])
      maze[y+ny][x+nx] = "#"
print(-1)

Submission status: Wrong Answer

Solution code:
h,w = [int(i) - 1 for i in input().split()]
ans  = 0
maze = []
for i in range(h+1):
  s = list(input())
  maze.append(s)
  ans += s.count(".")

pos = [[0,0,0]]
lst = [[1,0],[-1,0],[0,1],[0,-1]]

while pos:
  y,x,b = pos.pop()
  maze[y][x] = "#"
  for ny,nx in lst:
    if y+ny==h and x+nx==w:
      print(ans-b-2)
      exit()
    if 0<=y+ny<=h and 0<=x+nx<=w and maze[y+ny][x+nx] == ".":
      pos.append([y+ny,x+nx,b+1])
print(-1)

Submission status: Wrong Answer

Solution code:
#キューのクラス
class Queue:
    def __init__(self,data = []):
        self.data = data
    def enqueue(self,x):
        self.data.append(x)
        return self.data
    def dequeue(self):
        if len(self.data) == 0:
            return "Queue is Empty!"
        else:
            cell = self.data[0]
            del self.data[0]
            return self.data

H, W = map(int, input().split())
s = [list(input()) for i in range(H)]
#4近傍探索のために用意
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
#最小距離のリスト(Falseで初期化)
min_dis = [[False for i in range(W)] for j in range(H)]
min_dis[0][0] = 1#スタート位置を1にする(注意!!)
#キューのインスタンスQ作成
Q = Queue()
Q.enqueue([0, 0])
#キューの中身がなくなるまでループ
while Q.data:
    y = Q.data[0][0]
    x = Q.data[0][1]
    #4近傍探索
    for i, j in zip(dy, dx):
        if  (0 <= y + i < H) and  (0 <= x + j <W) and s[y + i][x + j] == ".":#（範囲内にあった場合）かつ（道だった場合）
            if min_dis[y+i][x+j] == False:#最小距離がFalseだった場合
                min_dis[y+i][x+j] = min_dis[y][x] + 1
                Q.enqueue([y+i, x+j])#値を更新したマスをQにプッシュ
    Q.dequeue()#探索し終わったマスをQからプル

##マスをカウント
num_shap = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            num_shap += 1
#スコア＝（全ます)-(#マス)-(gへの最短経路)
score = (H*W) - num_shap - (min_dis[H-1][W-1])
print(score)

Submission status: Wrong Answer

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

A = [list('#' * (w + 2))]
count_sharp = 0
for _ in range(h):
    C = list(input())
    count_sharp += C.count('#')
    A.append(['#'] + C + ['#'])
A.append(list('#') * (w + 2))

matrix = [[] for _ in range(10000)]


for i in range(h+1):
    for j in range(w+1):
        if A[i][j] == '.':
            if A[i-1][j] == '.':
                matrix[(i-1) * 100 + j].append(i*100+j)
            elif A[i][j-1] == '.':
                matrix[i * 100 + j - 1].append(i*100+j)
            elif A[i+1][j] == '.':
                matrix[(i+1) * 100 + j].append(i*100+j)
            elif A[i][j+1] == '.':
                matrix[i * 100 + j + 1].append(i*100+j)

# print(matrix)
def solver(matrix, h, w, count_):
    depth = 0
    path = [10000000] * 10000
    path[101] = 0
    stack = []
    stack.append(101)
    reached = [101]
    while len(stack) > 0:
        depth += 1
        for _ in range(len(stack)):
            val = stack.pop(0)
            for j in matrix[val]:
                if j not in set(reached):
                    path[j] = min(depth, path[j])
                    reached.append(j)
                    stack.append(j)
    # print(path)
    # print(path[h*100 + w] + 1)
    if path[h*100 + w] == 10000000:
        print(-1)
    else:
        print(h * w - path[h*100+w] - 1 - count_)
solver(matrix, h, w, count_sharp)

Submission status: Wrong Answer

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

A = [list('#' * (w + 2))]
count_sharp = 0
for _ in range(h):
    C = list(input())
    count_sharp += C.count('#')
    A.append(['#'] + C + ['#'])
A.append(list('#') * (w + 2))

matrix = [[] for _ in range(10000)]


for i in range(h+1):
    for j in range(w+1):
        if A[i][j] == '.':
            if A[i-1][j] == '.':
                matrix[(i-1) * 100 + j].append(i*100+j)
            elif A[i][j-1] == '.':
                matrix[i * 100 + j - 1].append(i*100+j)
            elif A[i+1][j] == '.':
                matrix[(i+1) * 100 + j].append(i*100+j)
            elif A[i][j+1] == '.':
                matrix[i * 100 + j + 1].append(i*100+j)

# print(matrix)
def solver(matrix, h, w, count_):
    depth = 0
    path = [100000] * 10000
    path[101] = 0
    stack = []
    stack.append(101)
    reached = [101]
    while len(stack) > 0:
        depth += 1
        for _ in range(len(stack)):
            val = stack.pop(0)
            for j in matrix[val]:
                if j not in set(reached):
                    path[j] = min(depth, path[j])
                    reached.append(j)
                    stack.append(j)
    # print(path)
    # print(path[h*100 + w] + 1)
    print(h * w - path[h*100+w] - 1 - count_)
solver(matrix, h, w, count_sharp)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt = 0
maze = []
for i in range(h):
    t = list(input())
    cnt += t.count('.')
    maze.append(t)
    
maze[h-1][w-1] = "g"
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

maze[0][0] = "#"

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

distance = deque([0]) 

goal = False
while queue:
    y, x = queue.popleft()
    past_count = distance.popleft()
    for dxi, dyi in zip(dx, dy):
        if not (0<=x+dxi<w and 0<=y+dyi<h) or maze[y+dyi][x+dxi] == "#":
            continue
        if maze[y+dyi][x+dxi] == "g":
            d = past_count+1
            goal = True
            break
        distance.append(past_count+1)
        maze[y+dyi][x+dxi] = "#"
        queue.append((y+dyi, x+dxi))
if goal:
    print(cnt-(d+1))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt = 0
maze = []
for i in range(h):
    t = list(input())
    cnt += t.count('.')
    maze.append(t)
    
maze[h-1][w-1] = "g"
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

maze[0][0] = "#"

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

distance = [[float('inf')]*w for _ in range(h)]
distance[0][0] = 0

goal = False
while queue:
    y, x = queue.popleft()
    for dxi, dyi in zip(dx, dy):
        if not (0<=x+dxi<w and 0<=y+dyi<h) or maze[y+dyi][x+dxi] == "#":
            continue
        if maze[y+dyi][x+dxi] == "g":
            d = min(distance[y][x]+1, distance[y+dyi][x+dxi])
            goal = True
            break
        distance[y+dyi][x+dxi] = min(distance[y][x]+1, distance[y+dyi][x+dxi])
        maze[y+dyi][x+dxi] = "#"
        queue.append((y+dyi, x+dxi))
if goal:
    print(cnt-(d+1))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
G = [input() for _ in range(H)]
black = 0
white = 0
dist = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = set()
for line in G:
  black+=line.count('#')
  white+=line.count('.')

D = deque()
D.append((0,0,0))
rout = -1
while D:
  h, w, c = D.popleft()
  if h == H-1 and w == W-1:
    rout = c
    break
  if (h, w) in visited:
    continue
  else:
    visited.add((h, w))
  for dh, dw in dist:
    if (0<=h+dh<H) and (0<=w+dw<W):
      if (h+dh, w+dw) not in visited:
        D.append((h+dh, w+dw, c+1))
        
if rout == -1:
  print(rout)
else:
  print(white-rout)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
G = [input() for _ in range(H)]
black = 0
white = 0
dist = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = set()
for line in G:
  black+=line.count('#')
  white+=line.count('.')

D = deque()
D.append((0,0,1))
rout = -1
while D:
  h, w, c = D.popleft()
  if h == H-1 and w == W-1:
    rout = c
    break
  if (h, w) in visited:
    continue
  else:
    visited.add((h, w))
  for dh, dw in dist:
    if (0<=h+dh<H) and (0<=w+dw<W):
      if (h+dh, w+dw) not in visited:
        D.append((h+dh, w+dw, c+1))
        
if rout == -1:
  print(rout)
else:
  print(white-rout)

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, input().split())
sx = 0
sy = 0
gx = H-1
gy = W-1
C = [list(i for i in input()) for _ in range(H)]
inf = -1
distance = [[inf] * W for _ in range(H)]
queue = []
queue.insert(0, (sy, sx))
distance[sy][sx] = 0
X = 0
while True:
    try:
        y, x = queue.pop()
        # print(y,x)
    except:
        # print("Fail")
        break
    for i in range(4):
        nx = x + (-1, 0, 1, 0)[i]
        ny = y + (0, -1, 0, 1)[i]
        # print("nynx",ny,nx)
        if (0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and C[ny][nx] != '#' and distance[ny][nx] == inf):
            queue.insert(0, (ny, nx))
            distance[ny][nx] = distance[y][x] + 1
            C[ny][nx] = "!"
    # print(queue,"Q")

if distance[H-1][W-1] != inf:
    #print(distance[gy][gx])
    ans = 0
    for i in C:
        ans += i.count(".")
        print(i)
    print(ans)
    print(distance)
else:
    print("Fail")

Submission status: Wrong Answer

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

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

if s[0][0] == "#":
    print(-1)
    exit()

num_black = 0
for i in s:
    for j in i:
        if j == "#":
            num_black += 1

map_ = [[0]*w for i in range(h)]
dq = deque([[0, 0, 0, map_]])


ans = 0
while(len(dq) > 0):
    y, x, dis, map_tmp = dq.popleft()
    # print(y, x, dis)

    if (y, x) == (h-1, w-1):
        ans_tmp = w*h-(dis+1)-num_black
        ans = max(ans, ans_tmp)

    map_tmp[y][x] = 1

    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if y+i < 0 or y+i >= h:
            continue
        if x+j < 0 or x+j >= w:
            continue
        if map_tmp[y+i][x+j] == 1:
            continue
        if s[y+i][x+j] == "#":
            continue
        else:
            dq.appendleft([y+i, x+j, dis+1, map_tmp[:]])

if ans == 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

num_black = 0
for i in s:
    for j in i:
        if j == "#":
            num_black += 1

map_ = [[0]*w for i in range(h)]
dq = deque([[0, 0, 0, map_]])


ans = 0
while(len(dq) > 0):
    y, x, dis, map_tmp = dq.popleft()
    # print(y, x, dis)

    if (y, x) == (h-1, w-1):
        ans_tmp = w*h-(dis+1)-num_black
        ans = max(ans, ans_tmp)

    map_tmp[y][x] = 1

    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if y+i < 0 or y+i >= h:
            continue
        if x+j < 0 or x+j >= w:
            continue
        if map_tmp[y+i][x+j] == 1:
            continue
        if s[y+i][x+j] == "#":
            continue
        else:
            dq.appendleft([y+i, x+j, dis+1, map_tmp[:]])

if ans == 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import deque

def li():
    return [int(x) for x in input().split()]


H, W = li()

maze = []
wall_cnt = 0
for i in range(H):
    row = input()
    wall_cnt += row.count("#")
    maze.append(list(row))

seen = [[INF] * W for _ in range(H)]

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

que = deque()

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

dist = INF
while len(que) > 0:
    x, y = que.popleft()
    if x == gx and y == gy:
        dist = seen[y][x]
        break
    children = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
    for child in children:
        cx, cy = child
        # validation and seen check
        if 0 <= cx < W and 0 <= cy < H and maze[cy][cx] == '.' and seen[cy][cx] == INF:
            seen[cy][cx] = seen[y][x] + 1
            que.append((cx, cy))

ans = H * W - wall_cnt - (dist + 1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
tb = {'#': -1, '.': 0}
ss = [
    list(map(lambda x: tb[x], list(input().rstrip())))
    for _ in range(h)
]

wh = 0
for y in range(h):
    for x in range(w):
        if ss[y][x] == 0:
            wh += 1

ss[0][0] = 1
q = deque([(0, 0)])
while q:
    pos = q.pop()
    d = ss[pos[1]][pos[0]]
    for x, y in ((0, -1), (-1, 0), (1, 0), (0, 1)):
        yy = pos[1] + y
        xx = pos[0] + x
        if 0 <= yy < h and 0 <= xx < w:
            if ss[yy][xx] == 0:
                ss[yy][xx] = d + 1
                q.append((xx, yy))
d = ss[h - 1][w - 1]
if d == 0:
    print(-1)
else:
    print(wh - d)

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
tb = {'#': -1, '.': 0}
ss = [
    list(map(lambda x: tb[x], list(input().rstrip())))
    for _ in range(h)
]

b = 0
for y in range(h):
    for x in range(w):
        if ss[y][x] == -1:
            b += 1

ss[0][0] = 1
q = deque([(0, 0)])
while q:
    pos = q.pop()
    d = ss[pos[1]][pos[0]]
    for x, y in ((0, -1), (-1, 0), (1, 0), (0, 1)):
        yy = pos[1] + y
        xx = pos[0] + x
        if 0 <= yy < h and 0 <= xx < w:
            if ss[yy][xx] == 0:
                ss[yy][xx] = d + 1
                q.append((xx, yy))
d = ss[h - 1][w - 1]
if d == 0:
    print(-1)
else:
    print(w * h - b - d)

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
tb = {'#': -1, '.': 0}
ss = [
    list(map(lambda x: tb[x], list(input().rstrip())))
    for _ in range(h)
]

b = 0
for y in range(h):
    for x in range(w):
        if ss[y][x] == -1:
            b += 1

ss[0][0] = 1
q = deque([(0, 0)])
while q:
    pos = q.pop()
    d = ss[pos[1]][pos[0]]
    for x, y in ((0, -1), (-1, 0), (1, 0), (0, 1)):
        yy = pos[1] + y
        xx = pos[0] + x
        if 0 <= yy < h and 0 <= xx < w:
            if ss[yy][xx] == 0:
                ss[yy][xx] = d + 1
                q.append((xx, yy))
    if pos == (w - 1, h - 1):
        break
d = ss[h - 1][w - 1]
if d == 0:
    print(-1)
else:
    print(w * h - b - d)

Submission status: Wrong Answer

Solution code:
from collections import deque
inf = 1000000000
h, w = map(int, input().split())
root = [[-inf]*w for i in range(h)]
root[0][0] = 1
s = [[] for i in range(h)]

cnt = 0
for i in range(h):
    s[i] = input()
    for j in range(w):
        if s[i][j] == '#': cnt+=1
dw = [-1, 0, 1, 0]
dh = [0, 1, 0, -1]
que = deque()
que.append([0, 0])
while que:
    x, y = que.pop()
    for dx, dy in zip(dw, dh):
        nx, ny = x+dx, y+dy
        if 0<=nx<w and 0<=ny<h and root[ny][nx]<=0 and s[ny][nx]=='.':
                que.append([nx, ny])
                root[ny][nx] = root[y][x] + 1
if root[h-1][w-1]<0:
    print(-1)
else:
    print(h*w - cnt - root[h-1][w-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
m = []
for i in range(H):
  m.append(input())
#白の個数数える(スタートゴール以外)
cnt0 = -2
for ma in m:
  for n in ma:
    if n == ".":
      cnt0 += 1
q = deque([(0,0)])
v = [[float("inf")]*W for i in range(H)]
v[0][0] = 0
g = (H-1, W-1)
move = ((0,1), (1,0), (0,-1), (-1,0))  
#ゴールの白個数はカウントしないから-1スタート
cnt1 = -1
#ここからBFS
while q:
  s = q.popleft()
  for mo in move:
    ns = (s[0]+mo[0], s[1]+mo[1])
    if 0<=ns[0]<=H-1 and 0<=ns[1]<=W-1 and v[ns[0]][ns[1]]==float("inf") and m[ns[0]][ns[1]]==".":
      q.append(ns)
      if v[ns[0]][ns[1]]>v[s[0]][s[1]]+1:
        v[ns[0]][ns[1]] = v[s[0]][s[1]]+1
    if ns == g:
      cnt1 += v[g[0]][g[1]]
      break
  if ns == g:
    break

print(cnt0-cnt1)

Submission status: Wrong Answer

Solution code:
from collections import deque

inf = 10**10

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

length = [[inf for j in range(w)]for i in range(h)]
visited = [[0 for j in range(w)]for i in range(h)]

move = [[-1,0],[1,0],[0,-1],[0,1]]

que = deque([])
que.append([0,0])
length[0][0] = 0
visited[0][0] = 1

white = 0

for i in range(h):
    white += field[i].count(".")

while que:
    y,x = que.popleft()

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        elif visited[ny][nx] == 1:
            continue
        
        visited[ny][nx] = 1
        que.append([ny,nx])
        length[ny][nx] = length[y][x] + 1

if length[h-1][w-1] == inf:
    print(-1)
else:
    print(white-(length[h-1][w-1]+1))

Submission status: Wrong Answer

Solution code:
from collections import deque

inf = 10**10

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

length = [[inf for j in range(w)]for i in range(h)]
visited = [[0 for j in range(w)]for i in range(h)]

move = [[-1,0],[1,0],[0,-1],[0,1]]

que = deque([])
que.append([0,0])
length[0][0] = 1
visited[0][0] = 1

white = 0

for i in range(h):
    white += field[i].count(".")

while que:
    y,x = que.popleft()

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        elif visited[ny][nx] == 1:
            continue
        
        visited[ny][nx] = 1
        que.append([ny,nx])
        length[ny][nx] = min(length[ny][nx],length[y][x] + 1)

if length[h-1][w-1] == inf:
    print(-1)
else:
    print(white-length[h-1][w-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

inf = 10**10

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

length = [[inf for j in range(w)]for i in range(h)]
visited = [[0 for j in range(w)]for i in range(h)]

move = [[-1,0],[1,0],[0,-1],[0,1]]

que = deque([])
que.append([0,0])
length[0][0] = 1
visited[0][0] = 1

black = 0

for i in range(h):
    black += field[i].count("#")

while que:
    y,x = que.popleft()

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        elif visited[ny][nx] == 1:
            continue
        
        visited[ny][nx] = 1
        que.append([ny,nx])
        length[ny][nx] = length[y][x] + 1

if length[h-1][w-1] == inf:
    print(-1)
else:
    print(h*w-length[h-1][w-1]-black)

Submission status: Wrong Answer

Solution code:
from collections import deque
dis = [[1, 0], [-1, 0], [0, 1], [0, -1]]
H, W = map(int, input().split())
A = []
count = 0
for i in range(H):
  a = input()
  A.append(a)
  count += a.count(".")
B = [[0 for j in range(W)] for i in range(H)]
D = deque([[0, 0]])
B[0][0] = 1
while len(D) > 0:
  d = D.pop()
  for k in range(4):
    p = d[0] + dis[k][0]
    q = d[1] + dis[k][1]
    if 0 <= p < H and 0 <= q < W and A[p][q] == "." and B[p][q] == 0:
      B[p][q] = B[d[0]][d[1]] + 1
      D.append([p, q])
if B[H-1][W-1] == 0:
  print(-1)
else:
  print(count - B[H-1][W-1])

Submission status: Wrong Answer

Solution code:





dx = (0,1,0,-1)
dy = (1,0,-1,0)


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

S=[input() for i in range(H)]
S_check = [[False]*W for _ in range(H)]

start = (0, 0, 1)
goal = (H-1, W-1)

Q = []
Q.append(start)

step = 0
is_reached = False

while Q:
    current = Q.pop(0)
    step = current[2]
    
    for i in range(4):
        next_pos = (current[0]+dx[i], current[1]+dy[i])

        if next_pos[0] < 0 or next_pos[0] > H-1 or next_pos[1] < 0 or next_pos[1] > W-1:
            continue
        elif S_check[next_pos[0]][ next_pos[1]]:
            continue
        elif next_pos == goal:
            is_reached = True
            break
        elif S[next_pos[0]][ next_pos[1]] == "#":
            continue
        else:
            S_check[next_pos[0]][ next_pos[1]] = True
            Q.append((next_pos[0], next_pos[1], step+1))

    if is_reached:
        break

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

ans = H * W - step -1 - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    h, w = LI()
    grid = SRL(h)
    v = [[-1] * w for i in range(h)]
    v[0][0] = 1
    q = deque()
    q.append((1, 1))

    while q:
        i, j = q.popleft()
        grid[i - 1][j - 1] = "*"
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if i + x < 1 or i + x > h or j + y < 1 or j + y > w or grid[i + x - 1][j + y - 1] != "." or v[i + x - 1][j + y - 1] < 0:
                continue
            v[i + x - 1][j + y -
                         1] = v[i - 1][j - 1] + 1
            q.append((i + x, j + y))

    if v[h-1][w-1] < 0:
        print(-1)
        return
    print(h*w-v[h-1][w-1]-list(chain.from_iterable(grid)).count("#"))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

from collections import deque


def main():
    def input(): return sys.stdin.readline()[:-1]
    H, W = map(int, input().split())

    graph = [input() for _ in range(H)]

    dist = [[-1] * W for _ in range(H)]
    queue = deque()

    H -= 1
    W -= 1
    
    # initialize
    queue.append((0, 0))
    dist[0][0] = 0
    cnt = 0

    while queue:
        vx, vy = queue.popleft()

        if (vx, vy) == (W, H):
            break

        dxdy = [(1,0), (0, 1), (-1, 0), (0, -1)]
        for dx, dy in dxdy:
            if (vx + dx > W) or (vy + dy > H): continue
            elif (vx + dx < 0) or (vy + dy < 0): continue

            elif graph[vy + dy][vx + dx] == ".":
                if dist[vy + dy][vx + dx] != -1: continue
                queue.append((vx + dx, vy + dy))
                dist[vy + dy][vx + dx] = dist[vy][vx] + 1
                cnt += 1

            elif graph[vy + dy][vx + dx] == "#": continue
            else: continue

    # can't goal
    if dist[H][W] == -1:
        print(-1)
    else:
        print(cnt - dist[H][W])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

H,W = map(int,input().split())
sy, sx = 0,0
gy, gx = H-1,W-1
D = [list(input()) for i in range(H)]
Bs = 0
for i in range(H):
    Bs += D[i].count("#")

Q = deque()
Q.append((sy,sx))
dist = [[-1]*W for i in range(H)]
dist[sy][sx] = 0
dx = [1,0,-1,0]
dy = [0,-1,0,1]

while Q:
    x,y = Q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<=W-1 and 0<=ny<=H-1 and D[ny][nx]!="#" and dist[ny][nx] == -1:
            Q.append((nx,ny))
            dist[ny][nx] = dist[y][x]+1

print(H*W-Bs-1-dist[gy][gx])