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
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import deque
H, W = map(int, input().split())
areas = []

black_count = 0
for _ in range(H):
    text = list(input().rstrip())
    for char in text:
        if char == '#':
            black_count += 1
    areas.append(text)

# 最短経路探索でかかったコストを使えば、コストが計算できる。全てのますの数から、最初から黒に塗られているを引いて、さらに最短コストを引けば良い
# 0,0からH,wへ行く


def bfs(areas, start_point, goal_point):
    scores = [[10**9 + 7 for _ in range(W)] for _ in range(H)]
    scores[0][0] = 1
    mv = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    queue = deque([start_point])
    while queue:
        now_point = queue.popleft()
        for next_postion in mv:
            next_point = [now_point[0] + next_postion[0],
                          now_point[1] + next_postion[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '#':
                    continue
                if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
    if scores[goal_point[0]][goal_point[1]] == 10**9 + 7:
        return -1
    return scores[goal_point[0]][goal_point[1]]


print(H * W - black_count - bfs(areas, [0, 0], [H - 1, W - 1]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import deque
H, W = map(int, input().split())
areas = []

black_count = 0
for _ in range(H):
    text = list(input().rstrip())
    for char in text:
        if char == '#':
            black_count += 1
    areas.append(text)

# 最短経路探索でかかったコストを使えば、コストが計算できる。全てのますの数から、最初から黒に塗られているを引いて、さらに最短コストを引けば良い
# 0,0からH,wへ行く


def bfs(areas, start_point, goal_point):
    scores = [[H * W for _ in range(W)] for _ in range(H)]
    scores[0][0] = 1
    mv = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    queue = deque([start_point])
    while queue:
        now_point = queue.popleft()
        for next_postion in mv:
            next_point = [now_point[0] + next_postion[0],
                          now_point[1] + next_postion[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '#':
                    continue
                if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
    if scores[goal_point[0]][goal_point[1]] == H * W:
        return -1
    return scores[goal_point[0]][goal_point[1]]


print(H * W - black_count - bfs(areas, [0, 0], [H - 1, W - 1]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import deque
H, W = map(int, input().split())
areas = []

black_count = 0
for _ in range(H):
    text = list(input().rstrip())
    for char in text:
        if char == '#':
            black_count += 1
    areas.append(text)

# 最短経路探索でかかったコストを使えば、コストが計算できる。全てのますの数から、最初から黒に塗られているを引いて、さらに最短コストを引けば良い
# 0,0からH,wへ行く


def bfs(areas, start_point, goal_point):
    scores = [[H * W for _ in range(W)] for _ in range(H)]
    scores[0][0] = 1
    mv = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    queue = deque([start_point])
    while queue:
        now_point = queue.popleft()
        for next_postion in mv:
            next_point = [now_point[0] + next_postion[0],
                          now_point[1] + next_postion[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '#':
                    continue
                if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
    return scores[goal_point[0]][goal_point[1]]


print(H * W - black_count - bfs(areas, [0, 0], [H - 1, W - 1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

H, W = list(map(int, input().split()))
s_y, s_x = 0, 0
g_y, g_x = H - 1, W - 1

visited = np.full((H, W), False)
board = np.zeros((H, W))
for i in range(H):
    row = input()
    for j, r in enumerate(row):
        if r == '.':
            board[i][j] = 1

direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
queue = deque()
queue.append(((s_y, s_x), 0))  # (pos, dist)

while len(queue) > 0:
    (y, x), dist = queue.popleft()
    if x == g_x and y == g_y:
        break

    for dx, dy in direction:
        new_y, new_x = y + dy, x + dx
        if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
            continue
        if board[new_y][new_x] == 0:
            continue
        if visited[new_y][new_x]:
            continue
        queue.append(((new_y, new_x), dist + 1))
        visited[new_y][new_x] = True
print(int(np.sum(board)) - (dist + 1))

Submission status: Wrong Answer

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

    dp = [[0 for _ in range(W)] for _ in range(H)]
    if s[0][0] == "#":
        print(-1)
        return
    if s[-1][-1] == "#":
        print(-1)
        return

    dp[0][0] = 1

    d = ((0, 1), (1, 0), (0, -1), (-1, 0))

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

            if dp[i][j] == 1:
                for dh, dw in d:
                    ni = i + dh
                    nj = j + dw
                    if 0 <= ni < H and 0 <= nj < W:
                        if s[ni][nj] == ".":
                            dp[ni][nj] = 1

    if dp[-1][-1] == 0:
        print(-1)
        return
    else:
        ans = cnt - (H + W - 1)
        print(ans)
        return


main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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] == w - 1 and p[1] == h - 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"):
                que.append((nx,ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[h - 1][w - 1]
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            black += 1
print((h * w - bfs() - 1) - black)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
visited_place=[[-1]*W for _ in range(H)]
visited_place[0][0]=1
stack=[[0,0]]
kazu=0
for a in S:
    kazu+=a.count('.')
def bfs(S,visited_place,stack):
    while len(stack)>0:
        h,w=stack.pop()
        for x,y,in ([1,0],[-1,0],[0,1],[-1,0]):
            new_h=h+x
            new_w=w+y
            if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
                continue
            if S[new_h][new_w]=='.' and visited_place[new_h][new_w]==-1:
                visited_place[new_h][new_w]=visited_place[h][w]+1
                stack.insert(0,[new_h,new_w])
    return visited_place[H-1][W-1]
if bfs(S,visited_place,stack)==-1:
    print(-1)
else:
    answer=kazu-bfs(S,visited_place,stack)
    print(answer)

Submission status: Wrong Answer

Solution code:
#bfs
def bfs(s,sx,sy,gx,gy):
    from collections import deque
    inf = float("inf")
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[inf for _ in  range(w)] for _ in  range(h)]
    que = deque()
    que.append([sx,sy])
    d[sx][sy] = 1
    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and d[nx][ny] == inf:
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

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

cnt = 0
for i in s:
    for j in i:
        if j == ".":
            cnt+=1

print(cnt - bfs(s,0,0,h - 1,w - 1))

Submission status: Wrong Answer

Solution code:
#bfs
def bfs(s,sx,sy,gx,gy):
    from collections import deque
    inf = float("inf")
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[inf for _ in  range(w)] for _ in  range(h)]
    que = deque()
    que.append([sx,sy])
    d[sx][sy] = 1
    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and d[nx][ny] == inf:
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

Submission status: Wrong Answer

Solution code:
from collections import deque

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

"""
count black tiles
"""
blackCount = 0
for row in maze:
  for tile in row:
    if tile=="#":
      blackCount += 1

"""
count shortest Path
"""
dist = [[-1 for i in range(W)]for j in range(H)]
dist[0][0] = 1
que = [[0,0]]
patterns = [[1,0],[-1,0],[0,1],[0,-1]]
shortestStep = 0
while que:
  now = que.pop(0)
  nowH = now[0]
  nowW = now[1]
  nowStep = dist[nowH][nowW]
  for pattern in patterns:
    nextH = nowH + pattern[0]
    nextW = nowW + pattern[1]
    if nextH == H-1 and nextW == W-1:
      shortestStep = nowStep + 1
      break
    if 0 <= nextH <= H-1 and 0 <= nextW <= W-1 and maze[nextH][nextW]!="#" and dist[nextH][nextW]==-1:
      dist[nextH][nextW] = nowStep + 1
      que.append([nextH,nextW])


print(H*W-(shortestStep + blackCount))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

"""
count black tiles
"""
blackCount = 0
for row in maze:
  for tile in row:
    if tile=="#":
      blackCount += 1

"""
count shortest Path
"""
dist = [[-1 for i in range(W)]for j in range(H)]
dist[0][0] = 1
que = [[0,0]]
patterns = [[1,0],[-1,0],[0,1],[0,-1]]
shortestStep = 0
while que:
  print(que)
  now = que.pop(0)
  nowH = now[0]
  nowW = now[1]
  nowStep = dist[nowH][nowW]
  for pattern in patterns:
    nextH = nowH + pattern[0]
    nextW = nowW + pattern[1]
    if nextH == H-1 and nextW == W-1:
      shortestStep = nowStep + 1
      break
    if 0 <= nextH <= H-1 and 0 <= nextW <= W-1 and maze[nextH][nextW]!="#" and dist[nextH][nextW]==-1:
      dist[nextH][nextW] = nowStep + 1
      que.append([nextH,nextW])


print(H*W-(shortestStep + blackCount))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
visited_place=[[-1]*W for _ in range(H)]
visited_place[0][0]=1
stack=[[0,0]]
kazu=0
for a in S:
    kazu+=a.count('.')
def bfs(S,visited_place,stack):
    while len(stack)>0:
        h,w=stack.pop()
        for x,y,in ([1,0],[-1,0],[0,1],[-1,0]):
            new_h=h+x
            new_w=w+y
            if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
                continue
            if S[new_h][new_w]=='.' and visited_place[new_h][new_w]==-1:
                visited_place[new_h][new_w]=visited_place[h][w]+1
                stack.insert(0,[new_h,new_w])
    return visited_place[H-1][W-1]
if bfs(S,visited_place,stack)==-1:
    print(-1)
else:
    answer=kazu-bfs(S,visited_place,stack)
    print(int(answer))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
visited_place=[[-1]*W for _ in range(H)]
visited_place[0][0]=0
stack=[[0,0]]
kazu=0
for a in S:
    kazu+=a.count('.')
def bfs(S,visited_place,stack):
    while len(stack)>0:
        h,w=stack.pop()
        for x,y,in ([1,0],[-1,0],[0,1],[-1,0]):
            new_h=h+x
            new_w=w+y
            if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
                continue
            if S[new_h][new_w]=='.' and visited_place[new_h][new_w]==-1:
                visited_place[new_h][new_w]=visited_place[h][w]+1
                stack.insert(0,[new_h,new_w])
    return visited_place[H-1][W-1]
if bfs(S,visited_place,stack)==-1:
    print(-1)
else:
    answer=kazu-bfs(S,visited_place,stack)-1
    print(answer)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
visited_place=[[-1]*W for _ in range(H)]
visited_place[0][0]=0
stack=[[0,0]]
kazu=0
for a in S:
    kazu+=a.count('.')
def bfs(S,visited_place,stack):
    while len(stack)>0:
        h,w=stack.pop()
        for x,y,in ([1,0],[-1,0],[0,1],[-1,0]):
            new_h=h+x
            new_w=w+y
            if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
                continue
            if S[new_h][new_w]=='.' and visited_place[new_h][new_w]==-1:
                visited_place[new_h][new_w]=visited_place[h][w]+1
                stack.insert(0,[new_h,new_w])
    return visited_place[H-1][W-1]
if bfs(S,visited_place,stack)==1:
    print(-1)
else:
    answer=kazu-bfs(S,visited_place,stack)-1
    print(answer)

Submission status: Wrong Answer

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

def f(sx, sy, gx, gy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(W)] for h in range(H)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
count = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            count += 1
print(H*W-f(0, 0, W-1, H-1)-1-count)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
S = [list(input()) for i in range(H)]
dot = 0
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "#" :
        dot += 1
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return dist[H*W-1]

dist = [-1 for _ in range(H*W)]
ans = dot - bfs(0) - 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
    d = [[float("INF")] * w for i in range(h)]
    d[0][0] = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    que = deque([])
    que.append((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 maze[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]
    
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            cnt += 1
print(h * w - cnt - bfs() - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
count_wall = 0
for i in range(h):
    maze[i] = input()
    count_wall += maze[i].count('#')

visited = [[0 for i in range(w)] for j in range(h)]
distance = [[-1 for i in range(w)] for j in range(h)]
sx=0
sy=0
queue = deque()
queue.append((sy,sx))
distance[sy][sx] = 0

while queue:
    y, x = queue.popleft()
    for i,j in [(1,0),(0,1)]:
        ny, nx = y+i, x+j
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != '#' and distance[ny][nx] == -1:
                queue.append((ny, nx))
                distance[ny][nx] = distance[y][x] + 1

if distance[h-1][w-1] > -1:
    ans = h*w-count_wall- (distance[h-1][w-1]+1)
else:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '#'*(W+2)
S[H+1] = '#'*(W+2)
path_c = 0
for i in range(1,H+1):
  S[i] = '#'+input()+'#'
  path_c += S[i].count('.')
#print(S)
visited = [[False]*(W+2) for _ in range(H+2)]
import queue
q = queue.Queue()
q.put((1,1,1))
visited[1][1]=True
dh = [1,0,-1,0]
dw = [0,1,0,-1]
while not q.empty():
  h,w,c = q.get()
  for i in range(4):
    y,x = h+dh[i],w+dw[i]
    #print(y,x)
    if y == H and x == W:
      c += 1
      break
    if S[y][x]=='.' and visited[y][x]==False:
      #print(y,x,c)
      q.put((y,x,c+1))
      visited[y][x]=True
  else:
      continue
  break
print(path_c-c)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '))
table = [input() for _ in range(H)]

# BFS
dists = [[float('inf') for _ in range(W)] for _ in range(H)]
dists[0][0] = 0
nexts = [(1,0), (-1,0), (0,1), (0,-1)]

buf = [(0, 0)]
while buf:
    h, w = buf.pop()

    for dh, dw in nexts:
        next_h, next_w = h+dh, w+dw
        if 0 <= next_h < H and 0 <= next_w < W:
            if table[next_h][next_w] == '.':
                if dists[next_h][next_w] == float('inf'):
                    dists[next_h][next_w] = dists[h][w] + 1
                    buf.append((next_h, next_w))

num_white = 0
for row in table:
    for r in row:
        if r == '.':
            num_white += 1

# print(num_white)
if dists[H-1][W-1] == float('inf'):
        print(-1)

else:
    print(num_white - dists[H-1][W-1] - 1)

Submission status: Wrong Answer

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

from collections import deque

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

d = [[0]*w for _ in range(h)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
d[0][0] = 1

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

    if x == h-1 and y == w-1:
        break

    for i, j in direction:
        dx, dy = x + i, y + j
        if 0<=dx<h and 0<=dy<w and d[dx][dy] == 0 and maze[dx][dy] != '#':
            d[dx][dy] = d[x][y] + 1
            que.append((dx, dy))


res = 0
for i in range(h):
    res += maze[i].count('#')

res += d[-1][-1]


print(h*w - res)

Submission status: Wrong Answer

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

from collections import deque

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

d = [[0]*w for _ in range(h)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
d[0][0] = 1

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

    for i, j in direction:
        dx, dy = x + i, y + j
        if 0<=dx<h and 0<=dy<w and d[dx][dy] == 0 and maze[dx][dy] != '#':
            d[dx][dy] = d[x][y] + 1
            que.append((dx, dy))


res = 0
for i in range(h):
    res += maze[i].count('#')

res += (d[-1][-1] - 1)


print(h*w - res - 1)

Submission status: Wrong Answer

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

M = [str(input()) for _ in range(h)]

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

M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

from collections import deque
q = deque()
q.append((1, 1))
visit = [[-1]*(w+2) for _ in range(h+2)]
visit[1][1] = 0

while q:
    y, x = q.popleft()
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y+dy, x+dx
        if visit[ny][nx] == -1 and M[ny][nx] != '#':
            visit[ny][nx] = visit[y][x]+1
            q.append((ny, nx))


ans = ans -visit[h][w]-1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
H, W = map(int, input().split())
l = [input() for _ in range(H)]
check = [([0] * (W)) for _ in range(H)]
white = 0
for i in range(H):
    white += l[i].count(".")
q = collections.deque()
check[0][0] = 1
q.append([0, 0])
g = False
while q:
    h, w = q.popleft()
    for i, j in ([0, 1], [0, -1], [1, 0], [-1, 0]):
        new_h = h + i
        new_w = w + j
        if new_w < 0 or new_h < 0 or new_w > W-1 or new_h > H-1 or l[new_h][new_w] == "#":
            continue
        elif check[new_h][new_w] == 0:
            check[new_h][new_w] = check[h][w] + 1
            q.append([new_h, new_w])
print(white - check[H-1][W-1] if check[H-1][W-1] != -1 else -1)

Submission status: Wrong Answer

Solution code:
import collections
H, W = map(int, input().split())
l = [input() for _ in range(H)]
check = [([0] * (W)) for _ in range(H)]
white = 0
ans = 0
for i in range(H):
    white += l[i].count(".")
q = collections.deque()
check[0][0] = 1
q.append([0, 0])
g = False
while q:
    h, w = q.popleft()
    for i, j in ([0, 1], [0, -1], [1, 0], [-1, 0]):
        new_h = h + i
        new_w = w + j
        if new_w < 0 or new_h < 0 or new_w > W-1 or new_h > H-1 or l[new_h][new_w] == "#":
            continue
        if new_w == W - 1 and new_h == H - 1:
            ans = white - (check[h][w] + 1)
            g = True
            break
        elif check[new_h][new_w] == 0:
            check[new_h][new_w] = check[h][w] + 1
            q.append([new_h, new_w])
print(ans if g else -1)

Submission status: Wrong Answer

Solution code:
import collections
H, W = map(int, input().split())
l = [input() for _ in range(H)]
check = [([0] * (W)) for _ in range(H)]
white = 0
ans = 0
for i in range(H):
    white += l[i].count(".")
q = collections.deque()
check[0][0] = 1
q.append([0, 0])
g = False
while q:
    h, w = q.popleft()
    for i, j in ([0, 1], [0, -1], [1, 0], [-1, 0]):
        new_h = h + i
        new_w = w + j
        if new_w < 0 or new_h < 0 or new_w > W-1 or new_h > H-1:
            continue
        if new_w == W - 1 and new_h == H - 1:
            ans = white - (check[h][w] + 1)
            g = True
            break
        elif check[new_h][new_w] == 0:
            check[new_h][new_w] = check[h][w] + 1
            q.append([new_h, new_w])
print(ans if g else -1)

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
INF = float("inf")
ss = [[INF] * w for i in range(h)]
def bfs():
    q = queue.Queue()
    ss[0][0] = 0
    q.put([0, 0])
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        for i in range(4):
            nextx = dx[i] + nowx
            nexty = dy[i] + nowy
            if nextx >= 0 and nexty >= 0 and nextx < h and nexty < w:
                if s[nextx][nexty] == "." and ss[nextx][nexty] == INF:
                    ss[nextx][nexty] = ss[nowx][nowy] + 1
                    q.put([nextx, nexty])

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

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

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
INF = float("inf")
ss = [[INF] * w for i in range(h)]
def bfs():
    q = queue.Queue()
    ss[0][0] = 0
    q.put([0, 0])
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        for i in range(4):
            nextx = dx[i] + nowx
            nexty = dy[i] + nowy
            if nextx >= 0 and nexty >= 0 and nextx < h and nexty < w:
                if s[nextx][nexty] == "." and ss[nextx][nexty] == INF:
                    ss[nextx][nexty] = ss[nowx][nowy] + 1
                    q.put([nextx, nexty])

bfs()
ans = h * w - (ss[h - 1][w - 1] + 1)
cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            cnt += 1

print(ans - cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

r,c = [int(x) for x in input().split()]
sy,sx = [0,0]
gy,gx = [r-1,c-1]
m = []
for _ in range(r):
    m.append(list(input()))

##########################################

q = deque()
d = [[-1]*c for i in range(r)]

q.append([sy,sx])
d[sy][sx] = 0
while q:
    v = q.popleft()
    if v == [gy,gx]:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0]+i[0]
        nx = v[1]+i[1]
        if 0<=ny<r and 0<=nx<c and m[ny][nx] == "." and d[ny][nx] == -1:
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

##########################
count = 0
for i in m:
    for j in i:
        if j==".":
            count += 1
ans = count - d[gy][gx] - 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
    q = deque()
    st = [1, 1]
    go = [h, w]
    q.append(st)
    d[1][1] = 1
    v = [1, -1]
    while q:
        u = q.popleft()
        x, y = u[0], u[1]
        for i in range(2):
            if s[x + v[i]][y] == "." and d[x + v[i]][y] == 0:
                q.append([x + v[i], y])
                d[x + v[i]][y] = d[x][y] + 1
        for i in range(2):
            if s[x][y + v[i]] == "." and d[x][y + v[i]] == 0:
                q.append([x, y + v[i]])
                d[x][y + v[i]] = d[x][y] + 1
    c = 0
    for i in s:
        for j in i:
            if j == ".":
                c += 1
    return c - d[h][w]

h, w = map(int, input().split())
s = [["#"] + list(input()) + ["#"] for _ in range(h)]
t = ["#" for _ in range(w + 2)]
s.append(t)
s.insert(0, t)
d = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque

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

que = deque([(0, 0, 1)])
minDist = [[10**10] * W for _ in range(H)]

while que:
    h, w, d = que.popleft()

    if minDist[h][w] <= d:
        continue
    minDist[h][w] = d

    if (h, w) == (H - 1, W - 1):
        break

    for dh, dw in zip([0, 0, 1, -1], [1, -1, 0, 0]):
        toH, toW = h + dh, w + dw
        if 0 <= toH < H and 0 <= toW < W and A[toH][toW] == '.':
            que.append((toH, toW, d + 1))

white = sum([a.count('.') for a in A])
print(max(0, white - minDist[H - 1][W - 1]))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

que = deque([(0, 0, 0)])
minDist = [[10**10] * W for _ in range(H)]

while que:
    h, w, d = que.popleft()

    if minDist[h][w] <= d:
        continue
    minDist[h][w] = d

    if (h, w) == (H - 1, W - 1):
        break

    for dh, dw in zip([0, 0, 1, -1], [1, -1, 0, 0]):
        toH, toW = h + dh, w + dw
        if 0 <= toH < H and 0 <= toW < W and A[toH][toW] == '.':
            que.append((toH, toW, d + 1))

white = sum([a.count('.') for a in A]) - 2
print(white - (minDist[H - 1][W - 1] - 1))

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['#' for _ in range(W+2)])
ans = [[0 for _ in range(W+2)]for _ in range(H+2)]
score = 0
for i in range(H):
    tmp = list('#'+input()+'#')
    c.append(tmp)
    for j in range(W+2):
        if tmp[j] == '.':
            score += 1

c.append(['#' for _ in range(W+2)])
q = deque()

def bfs(x,y):
    q.append([x,y])
    while q:
        x,y = q.popleft()
        if [x,y] == [W,H]:
            return ans[H][W]
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'
    return -1

tmp = bfs(1,1)
if tmp == -1:
    print(-1)
else:
    print(score - bfs(1,1) - 1)