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:
from collections import deque

INF = 100000000

# 入力
H, W = map(int, input().split())

maze = [input() for i in range(H)]

# 移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# (sx,sy)から(gx,gy)への最短距離を求める
# たどりつけないとINF

def bfs():
    que = deque([])
    # 全ての点をINFで初期化
    d = [[INF for j in range(W)] for i in range(H)]

    # スタート地点をキューに入れ、その点の距離を0にする
    que.append([0,0])
    d[0][0]= 0

    # キューが空になるまでループ
    while len(que) > 0:
        # キューの先頭を取り出す
        p = que.popleft()
        #取り出してきた状態がゴールなら探索をやめる
        if p[0] == H-1 and p[1] == W-1:
            break
        # 移動4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能化の判定とすでに訪れたことがあるかの判定
            if 0<=nx and nx<H and 0<ny and ny<W and maze[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[H-1][W-1]

white = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            white += 1
if bfs() == INF:
    print(-1)
else:
    print(white - bfs() - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 100000000

# 入力
H, W = map(int, input().split())

maze = [input() for i in range(H)]

# 移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# (sx,sy)から(gx,gy)への最短距離を求める
# たどりつけないとINF

def bfs():
    que = deque([])
    # 全ての点をINFで初期化
    d = [[INF for j in range(W)] for i in range(H)]

    # スタート地点をキューに入れ、その点の距離を0にする
    que.append([0,0])
    d[0][0]= 0

    # キューが空になるまでループ
    while len(que) > 0:
        # キューの先頭を取り出す
        p = que.popleft()
        #取り出してきた状態がゴールなら探索をやめる
        if p[0] == H-1 and p[1] == W-1:
            break
        # 移動4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能化の判定とすでに訪れたことがあるかの判定
            if 0<=nx and nx<H and 0<ny and ny<W and maze[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[H-1][W-1]

white = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            white += 1
if white == bfs()+1:
    print(-1)
else:
    print(white - bfs() - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 100000000

# 入力
H, W = map(int, input().split())

maze = [input() for i in range(H)]

# 移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# (sx,sy)から(gx,gy)への最短距離を求める
# たどりつけないとINF

def bfs():
    que = deque([])
    # 全ての点をINFで初期化
    d = [[INF for j in range(W)] for i in range(H)]

    # スタート地点をキューに入れ、その点の距離を0にする
    que.append([0,0])
    d[0][0]= 0

    # キューが空になるまでループ
    while len(que) > 0:
        # キューの先頭を取り出す
        p = que.popleft()
        #取り出してきた状態がゴールなら探索をやめる
        if p[0] == H-1 and p[1] == W-1:
            break
        # 移動4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能化の判定とすでに訪れたことがあるかの判定
            if 0<=nx and nx<H and 0<ny and ny<W and maze[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[H-1][W-1]

white = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            white += 1

print(white - bfs() - 1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
dist = [[0] * w for _ in range(h)]
dist[0][0] = 1
queue = [(0, 0)]
cnt = 0
while len(queue) > 0:
    n_h, n_w = queue.pop(0)
    if n_h == h - 1 and n_w == w - 1:
        break

    for i, j in ([0, 1], [1, 0], [0, -1], [-1, 0]):
        y, x = n_h + i, n_w + j
        if 0 <= x < w and 0 <= y < h:
            if s[y][x] == "." and dist[y][x] == 0:
                dist[y][x] = dist[n_h][n_w] + 1
                queue.append([y, x])

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans += 1
    
print(ans - dist[h - 1][w - 1])

Submission status: Wrong Answer

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

allcnt = 0
for i in range(w):
    for j in range(h):
        if block[j][i] == '.':
            allcnt += 1
import sys
sys.setrecursionlimit(10**6)
# BFSで最短経路を求める。allcnt - (cnt + 1)
INF = float('inf')
AR = [[INF] * w for _ in range(h)]
from collections import deque
# cnt = 0
dy = [1,0,0,-1]
dx = [0,-1,1,0]
def bfs():
    d = deque()
    d.append([0,0])
    while d:
        y,x = d.popleft()
        if y == 0 and x == 0:
            AR[y][x] = 0
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if (not 0 <= ny < h) or (not 0 <= nx < w):
                continue
            if AR[ny][nx] == INF and block[ny][nx] != '#':
                AR[ny][nx] = AR[y][x] + 1
                d.append([ny,nx])
bfs()
print(allcnt - (AR[h-1][w-1]+1))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[1 if s == "#" else 0 for s in input()] for _ in range(h)]
dp = [[10**10 for _ in range(w)] for _ in range(h)]
dp[0][0] = 0
for wi in range(1, w):
    dp[0][wi] = dp[0][wi-1] + s[0][wi]
for hi in range(1, h):
    dp[hi][0] = dp[hi-1][0] + s[hi][0]
    for wi in range(1, w):
        dp[hi][wi] = min(dp[hi-1][wi] + s[hi][wi], dp[hi][wi-1] + s[hi][wi])
if dp[h-1][w-1] != 0:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        cnt += s[hi][wi]
print(h*w - ((h-1) + (w-1) + 1) - cnt)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[1 if s == "#" else 0 for s in input()] for _ in range(h)]
dp = [[10**10 for _ in range(w)] for _ in range(h)]
dp[0][0] = 0
for wi in range(1, w):
    dp[0][wi] = dp[0][wi-1] + s[0][wi]
for hi in range(1, h):
    dp[hi][0] = dp[hi-1][0] + s[hi][0]
    for wi in range(1, w):
        dp[hi][wi] = min(dp[hi-1][wi], dp[hi][wi-1]) + s[hi][wi]
if dp[h-1][w-1] != 0:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        cnt += s[hi][wi]
print(h*w - ((h-1) + (w-1) + 1) - cnt)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[1 if s == "#" else 0 for s in input()] for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
for wi in range(1, w):
    dp[0][wi] = dp[0][wi-1] + s[0][wi]
for hi in range(1, h):
    dp[hi][0] = dp[hi-1][0] + s[hi][0]
    for wi in range(1, w):
        dp[hi][wi] = min(dp[hi-1][wi], dp[hi][wi-1]) + s[hi][wi]
if dp[h-1][w-1] != 0:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        cnt += s[hi][wi]
print(h*w - ((h-1) + (w-1) + 1) - cnt)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[1 if s == "#" else 0 for s in input()] for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
dp[0][0] = s[0][0]
for wi in range(1, w):
    dp[0][wi] = dp[0][wi-1] + s[0][wi]
for hi in range(1, h):
    dp[hi][0] = dp[hi-1][0] + s[hi][0]
    for wi in range(1, w):
        dp[hi][wi] = min(dp[hi-1][wi], dp[hi][wi-1]) + s[hi][wi]
if dp[-1][-1] != 0:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        cnt += s[hi][wi]
print(h*w - 2 - ((h-1) + (w-1) - 1) - cnt)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[1 if s == "#" else 0 for s in input()] for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
dp[0][0] = s[0][0]
for wi in range(1, w):
    dp[0][wi] = dp[0][wi-1] + s[0][wi]
for hi in range(1, h):
    dp[hi][0] = dp[hi-1][0] + s[hi][0]
    for wi in range(1, w):
        dp[hi][wi] = min(dp[hi-1][wi], dp[hi][wi-1]) + s[hi][wi]
if dp[-1][-1] != 0:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        cnt += s[hi][wi]
print(h*w - ((h-1) + (w-1) + 1) - cnt)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[1 if s == "#" else 0 for s in input()] for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
dp[0][0] = s[0][0]
for wi in range(1, w):
    dp[0][wi] = dp[0][wi-1] + s[0][wi]
for hi in range(1, h):
    dp[hi][0] = dp[hi-1][0] + s[hi][0]
    for wi in range(1, w):
        dp[hi][wi] = min(dp[hi-1][wi], dp[hi][wi]) + s[hi][wi]
if dp[-1][-1] != 0:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        cnt += s[hi][wi]
print(h*w - ((h-1) + (w-1) + 1) - cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W=map(int, input().split(" "))
field=[list(input()) for _ in range(H)]
dist=[[-1]*W for _ in range(H)]
que=deque([[0,0]])
dist[0][0]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
cnt=0
#BFS

while que:
    y, x=que.popleft()
    if [y, x]==[H-1, W-1]:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0<=nx<W and 0<=ny<H and field[ny][nx]=="." and dist[ny][nx]==-1):
            dist[ny][nx]=dist[y][x]+1
            que.append([ny, nx])
    result=False
if result:
    for j in range(H):
        for k in range(W):
            if field[j][k]=="#":
                cnt+=1
    print(H*W-dist[H-1][W-1]-cnt-2+1)
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W=map(int, input().split(" "))
field=[list(input()) for _ in range(H)]
dist=[[-1]*W for _ in range(H)]
que=deque([[0,0]])
dist[0][0]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
cnt=0
#BFS

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

for j in range(H):
    for k in range(W):
        if field[j][k]=="#":
            cnt+=1
print(H*W-dist[H-1][W-1]-cnt-2+1)

Submission status: Wrong Answer

Solution code:
from collections import deque 
H, W = map(int, input().split())
graph = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque([(0,0)])
dist[0][0] = 1
while q:
  x, y = q.popleft()
  if(x >= 1):
    if(dist[x-1][y] < 0 and graph[x-1][y] == '.'):
      dist[x-1][y] = dist[x][y] + 1
      q.append((x-1, y))
  if(x <= H-2):
    if(dist[x+1][y] < 0 and graph[x+1][y] == '.'):
      dist[x+1][y] = dist[x][y] + 1
      q.append((x+1, y))
  if(y >= 1):
    if(dist[x][y-1] < 0 and graph[x][y-1] == '.'):
      dist[x][y-1] = dist[x][y] + 1
      q.append((x, y-1))
  if(y <= W-2):
    if(dist[x][y+1] < 0 and graph[x][y+1] == '.'):
      dist[x][y+1] = dist[x][y] + 1
      q.append((x, y+1))
      
cnt = 0
for i in range(H):
  for j in range(W):
    if(graph[i][j] == '#'):
      cnt += 1
print(H*W-cnt-dist[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
s=[['#']*(W+2)for _ in range(H+2)]
count=0
for i in range(1,H+1):
  S=list(input())
  s[i]=['#']+S+['#']
  count+=S.count('.')
move=[(1,0),(-1,0),(0,1),(0,-1)]
que=[(1,1)]
s[1][1]=1
while que:
  a,b=que.pop()
  if (a,b)==(H,W):
    break
  for my,mx in move:
    ny=my+a
    nx=mx+b
    if s[ny][nx]=='#':
      continue
    elif s[ny][nx]=='.':
      que.append((ny,nx))
      s[ny][nx]=s[a][b]+1
ans=-1
if s[H][W]!='.':
  ans=count-s[H][W]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])

    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 not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == 'X':
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

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

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

cnt = 0

for i in range(H):
    cnt += Grid[i].count('.')

d = gridbfs(Grid,0,0)

if d[H-1][W-1] == 10**18:
    print(-1)
else:
    print(cnt - d[H-1][W-1] -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])

    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 not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == 'X':
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

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

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

cnt = 0

for i in range(H):
    cnt += Grid[i].count('.')

d = gridbfs(Grid,0,0)

print(max(-1, cnt - d[H-1][W-1] -1))

Submission status: Wrong Answer

Solution code:
h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

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

i, j = (1, 1)
INF = 10**18
dist = [[INF] * w for _ in range(h)]
dist[i][j] = 1
next_v = [(i, j)]
while next_v:
    i, j = next_v.pop()
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for di, dj in direction:
        x, y = i+di, j+dj
        if MAZE[x][y] == "#":
            continue
        if dist[x][y] <= dist[i][j] + 1:
            continue
        dist[x][y] = dist[i][j] + 1
        next_v.append((x, y))
    last = dist[h-2][w-2]

ans = total - last
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
black=0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      black+=1
s=[0,0,1]
g=[h-1,w-1]
queue=[s]
go=[[0,1],[0,-1],[1,0],[-1,0]]
ans=-1
check=[[True for i in range(w)] for j in range(h)]
while len(queue)>0:
  p=queue.pop(0)
  for i in range(4):
    x=p[0]+go[i][0]
    y=p[1]+go[i][1]
    count=p[2]
    if x>-1 and x<h and y>-1 and y<w and check[x][y] and maze[x][y]=='.':
      if x==g[0] and y==g[1]:
        ans=count+1
        break
      else:
        count+=1
        check[x][y]=False
        queue.append([x,y,count])
  if ans>0:
    break
if ans<0:
  print(ans,'no')
else:
  print(h*w-black-ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
black=0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      black+=1
s=[0,0,1]
g=[h-1,w-1]
queue=[s]
go=[[0,1],[0,-1],[1,0],[-1,0]]
ans=-1
check=[[True for i in range(w)] for j in range(h)]
while len(queue)>0:
  p=queue.pop(0)
  for i in range(4):
    x=p[0]+go[i][0]
    y=p[1]+go[i][1]
    count=p[2]
    if x>-1 and x<h and y>-1 and y<w and check[x][y] and maze[x][y]=='.':
      if x==g[0] and y==g[1]:
        ans=count+1
        break
      else:
        count+=1
        check[x][y]=False
        queue.append([x,y,count])
if ans<0:
  print(ans)
else:
  print(h*w-black-ans)

Submission status: Wrong Answer

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

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

for i in range(H):
    for j in range(W):
        if s[i][j] == '#':  # 黒マスだった場合
            dist[i][j] = -1
        else:
            count += 1
dist[0][0] = 1  # スタートを１に更新

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

def bfs(move, dist):
    while move:
        y,x = move.popleft()
        d = dist[y][x]
        for dy,dx in ((0,1), (0,-1), (1,0), (-1,0)):
            new_y = y + dy
            new_x = x + dx
            if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
                continue
            if dist[new_y][new_x] == 0:  # セルが未到達のとき
                dist[new_y][new_x] = d+1
                move.append((new_y,new_x))
    return dist[H-1][W-1]
print(count - bfs(move,dist))

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = list(map(int, input().split(' ')))
FIELD = list()
for _ in range(H):
    FIELD.append(input())
white_cell_set = set()
for h in range(H):
    for w in range(W):
        if FIELD[h][w] == '.':
            white_cell_set.add((h, w))
class Node:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.parent = None
sh, sw = 0, 0  # start
gh, gw = H - 1, W - 1  # goal
# We can get the maximum score
# when we change colors of cells which are not on the shortest path.
frontier = deque()
frontier.append(Node(sh, sw))
explored_flag = [[0 for _ in range(W)] for _ in range(H)]
node = None
while len(frontier) > 0:
    node = frontier.popleft()
    if node.h == gh and node.w == gw:  # reach goal
        break
    explored_flag[node.h][node.w] = 1
    for dh, dw in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = node.h + dh, node.w + dw  # next
        if (nh < 0) or (H - 1 < nh) or (nw < 0) or (W - 1 < nw):
            continue
        if FIELD[nh][nw] == '#':
            continue
        if explored_flag[nh][nw] == 1:
            continue
        next_node = Node(nh, nw)
        next_node.parent = node
        frontier.append(next_node)
while True:
    white_cell_set.remove((node.h, node.w))
    if node.parent is None:
        break
    node = node.parent
print(len(white_cell_set))

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = '#' * (W + 2)
for _ in range(H):
    grid += '#' + input() + 'X'
grid += '#' * (W + 2)

root = list(i for i in range(len(grid)) if grid[i] == '.')
start = root[0]
goal = root[-1]

def bfs():
    move = [1, -1, W + 2, -(W + 2)]
    se = set([start])
    q = deque([start])
    T = [-1] * len(grid)
    T[start] = 0
    while q:
        x = q.popleft()
        for dx in move:
            y = x + dx
            if grid[y] == '#':
                continue
            if y in se:
                continue
            if y == goal:
                return T[x] + 1
            T[y] = T[x] + 1
            se.add(y)
            q.append(y)
    return T[goal]

ret = bfs()
print(len(root[1:]) - ret if ret != -1 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = '#' * (W + 2)
for _ in range(H):
    grid += '#' + input() + 'X'
grid += '#' * (W + 2)

root = list(i for i in range(len(grid)) if grid[i] == '.')
start = root[0]
goal = root[-1]

def bfs(grid_):
    move = [1, -1, W + 2, -(W + 2)]
    se = set([start])
    q = deque([start])

    T = [-1] * len(grid)
    T[start] = 0
    while q:
        x = q.popleft()
        for dx in move:
            y = x + dx
            if grid_[y] == '#':
                continue
            if y in se:
                continue
            T[y] = T[x] + 1
            se.add(y)
            q.append(y)
    return T[goal]

time = bfs(grid)
print(len(root[1:]) - time if time != -1 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = '#' * (W + 2)
for _ in range(H):
    grid += '#' + input() + 'X'
grid += '#' * (W + 2)

root = list(i for i in range(len(grid)) if grid[i] == '.')
start = root[0]
goal = root[-1]

def bfs(grid_):
    move = [1, -1, W + 2, -(W + 2)]
    se = set([start])
    q = deque([start])

    T = [-1] * len(grid)
    T[start] = 0
    while q:
        x = q.popleft()
        for dx in move:
            y = x + dx
            if grid_[y] == '#':
                continue
            if y in se:
                continue
            T[y] = T[x] + 1
            se.add(y)
            q.append(y)
    return T[goal]

print(len(root[1:]) - bfs(grid))

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = '#' * (W + 2)
for _ in range(H):
    grid += '#' + input() + 'X'
grid += '#' * (W + 2)

root = list(i for i in range(len(grid)) if grid[i] == '.')
start = root[0]
goal = root[-1]

def bfs(grid_):
    move = [1, -1, W + 2, -(W + 2)]
    se = set([start])
    q = deque([start])

    T = [-1] * len(grid)
    T[start] = 0
    while q:
        x = q.popleft()
        for dx in move:
            y = x + dx
            if grid_[y] == '#':
                continue
            if y in se:
                continue
            T[y] = T[x] + 1
            se.add(y)
            q.append(y)
    return T[goal] >= 0

ans = 0
for i in root[1:-1]:
    grid_ = grid[:i] + '#' + grid[i+1:]
    if bfs(grid_):
        ans += 1
        grid = grid_
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(200000)
H,W=map(int,input().split())
G=[input() for i in range(H)]
F=[[0]*W for i in range(H)]

def judge(p0,p1,res):
  res=copy.deepcopy(res)
  F[p0][p1]=1
  if p0==H-1 and p1==W-1:
    return res
  
  a=float("inf")
  if p0<H-1 and F[p0+1][p1]==0 and G[p0+1][p1]==".":
    m=judge(p0+1,p1,res+1)
    if m!=False:
      a=min(a,m)
  
  if p1<W-1 and F[p0][p1+1]==0 and G[p0][p1+1]==".":
    m=judge(p0,p1+1,res+1)
    if m!=False:
      a=min(a,m)
      
  if p0>0 and F[p0-1][p1]==0 and G[p0-1][p1]==".":
    m=judge(p0-1,p1,res+1)
    if m!=False:
      a=min(a,m)
   
  if p1>0 and F[p0][p1-1]==0 and G[p0][p1-1]==".":
    m=judge(p0,p1-1,res+1)
    if m!=False:
      a=min(a,m)
    
  if a!=float("inf"):
    return a
    
  return False
k=judge(0,0,0)
if k!=False:
  ans=W*H-(k+1)
  for i in range(H):
    ans-=G[i].count("#")
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
G=[input() for i in range(H)]

def judge(p0,p1):
  if p0==H-1 and p1==W-1:
    return True
  
  if p0<H-1 and G[p0+1][p1]==".":
    m=judge(p0+1,p1)
    if m==True:
      return True
  
  if p1<W-1 and G[p0][p1+1]==".":
    n=judge(p0,p1+1)
    if n==True:
      return True
    
  return False

if judge(0,0):
  ans=W*H-(W+H-1)
  for i in range(H):
    ans-=G[i].count("#")
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
    d = [[float("inf") for i in range(W)] for j in range(H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-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<W and 0<=ny<H and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
    return d[H-1][W-1]

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

cnt = 1

for i in range(H):
    cnt += maze[i].count("#")

print(H*W-bfs()-cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
def dfs(maze,visited,sh,sw):
  stack=deque([[sh,sw]])
  visited[sh][sw]=1
  while stack:
    y,x=stack.pop()
    if y==h-1 and x==w-1:
      return visited[y][x]
    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      n_y,n_x=y+j,x+k
      if not (0<=n_y<h and 0<=n_x<w):
        continue
      if maze[n_y][n_x]=='.' and visited[n_y][n_x]==0:
        visited[n_y][n_x]=visited[y][x]+1
        stack.append([n_y,n_x])
  return -1
cnt=0
for i in s:
  cnt+=i.count('#')
visited=[[0]*w for _ in range(h)]
route=dfs(s,visited,0,0)
print(-1 if route<0 else h*w-cnt-route)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze,visited,start_h,start_w,goal_h,goal_w):
  queue=deque([[start_h,start_w]])
  visited[start_h][start_w]=0
  while queue:
    h,w=queue.popleft()
    if [h,w]==[goal_h,goal_w]:
      return visited[goal_h][goal_w]
    for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
      new_h,new_w=h+i,w+j
      if new_h<0 or new_h>=H or new_w<0 or new_w>=W:
        continue
      if maze[new_h][new_w]=='.' and visited[new_h][new_w]==-1:
        visited[new_h][new_w]=visited[h][w]+1
        queue.append([new_h,new_w])

H,W=map(int,input().split())
maze=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]

cost=bfs(maze,visited,0,0,H-1,W-1)
if cost==None:
  print(-1,cost)
else:
  cnt=-1
  for i in range(H):
    cnt+=maze[i].count('.')
  print(cnt-cost)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
def dfs(maze,visited,sh,sw):
  stack=deque([[sh,sw]])
  visited[sh][sw]=1
  while stack:
    y,x=stack.pop()
    if y==h-1 and x==w-1:
      return visited[y][x]
    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      n_y,n_x=y+j,x+k
      if not (0<=n_y<h and 0<=n_x<w):
        continue
      if maze[n_y][n_x]=='.' and visited[n_y][n_x]==0:
        visited[n_y][n_x]=visited[y][x]+1
        stack.append([n_y,n_x])
  return -1
cnt=0
for i in s:
  cnt+=i.count('#')
visited=[[0]*w for _ in range(h)]
print(h*w-cnt-dfs(s,visited,0,0))

Submission status: Wrong Answer

Solution code:
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    cnt_white = sum(row.count('.') for row in grid)
    
    dist = [[-1] * w for _ in range(h)]
    q = deque([(0,0)])
    dist[0][0] = 1
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if y < 0 or y >= h:
                continue
            if x < 0 or x >= w:
                continue
            if dist[y][x] < 0 and grid[y][x] == '.':
                dist[y][x] = dist[i][j] + 1
                q.append((y,x))

    ans = cnt_white - dist[-1][-1]
    print(ans)          
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue

h,w=map(int,input().split())
s=[]
dist=[]
cnt=0
for i in range(h):
  s.append(input())
  dist.append([5000]*w)
  cnt+=s[i].count("#")
que=queue.Queue()
que.put([0,0])
dist[0][0]=0
d=[[0,1],[0,-1],[1,0],[-1,0]]
while not que.empty():
  place=que.get()
  for p in d:
    if -1<place[0]+p[0]<h and -1<place[1]+p[1]<w:
      if s[place[0]+p[0]][place[1]+p[1]] and dist[place[0]][place[1]]+1<dist[place[0]+p[0]][place[1]+p[1]]:
        dist[place[0]+p[0]][place[1]+p[1]] = dist[place[0]][place[1]]+1
        que.put([place[0]+p[0],place[1]+p[1]])
if dist[h-1][w-1]<5000:
  print(h*w-cnt-dist[h-1][w-1]-1)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
r,c =map(int,input().split())
G = [input() for _ in range(r)]
black = 0
for i in range(r):
    for j in range(c):
        if G[i][j] == "#":
            black += 1
# print(black)

M = [[10*7 for _ in range(c)] for i in range(r)]
queue = deque([(0,0)])
M[0][0] = 0
while len(queue) != 0:
    now = queue.popleft()
    dxy = [(0,1),(0,-1),(1,0),(-1,0)]
    for p in dxy:
        nexte = (now[0]+p[0],now[1]+p[1])
        if nexte[0]<0 or nexte[0]>=r or nexte[1]<0 or nexte[1]>=c:
            continue
        else:
            if G[nexte[0]][nexte[1]] == ".":
                if M[nexte[0]][nexte[1]] > M[now[0]][now[1]] + 1:
                    M[nexte[0]][nexte[1]] = M[now[0]][now[1]] + 1
                    queue.append(nexte)
if M[r-1][c-1] == 10**7:
    print(-1)
else:
    print(r*c-1 - M[r-1][c-1] - black)

Submission status: Wrong Answer

Solution code:
from collections import deque
r,c =map(int,input().split())
G = [input() for _ in range(r)]
black = 0
for i in range(r):
    for j in range(c):
        if G[i][j] == "#":
            black += 1
# print(black)

M = [[10*9 for _ in range(c)] for i in range(r)]
queue = deque([(0,0)])
M[0][0] = 0
while len(queue) != 0:
    now = queue.popleft()
    dxy = [(0,1),(0,-1),(1,0),(-1,0)]
    for p in dxy:
        nexte = (now[0]+p[0],now[1]+p[1])
        if nexte[0]<0 or nexte[0]>=r or nexte[1]<0 or nexte[1]>=c:
            continue
        else:
            if G[nexte[0]][nexte[1]] == ".":
                if M[nexte[0]][nexte[1]] > M[now[0]][now[1]] + 1:
                    M[nexte[0]][nexte[1]] = M[now[0]][now[1]] + 1
                    queue.append(nexte)
if M[r-1][c-1] == 10**9:
    print(-1)
else:
    print(r*c-1 - M[r-1][c-1] - black)

Submission status: Wrong Answer

Solution code:
from collections import deque
r,c =map(int,input().split())
G = [input() for _ in range(r)]
black = 0
for i in range(r):
    for j in range(c):
        if G[i][j] == "#":
            black += 1
# print(black)

M = [[10*9 for _ in range(c)] for i in range(r)]
queue = deque([(0,0)])
M[0][0] = 0
while len(queue) != 0:
    now = queue.popleft()
    dxy = [(0,1),(0,-1),(1,0),(-1,0)]
    for p in dxy:
        nexte = (now[0]+p[0],now[1]+p[1])
        if nexte[0]<0 or nexte[0]>=r or nexte[1]<0 or nexte[1]>=c:
            continue
        else:
            if G[nexte[0]][nexte[1]] == ".":
                if M[nexte[0]][nexte[1]] > M[now[0]][now[1]] + 1:
                    M[nexte[0]][nexte[1]] = M[now[0]][now[1]] + 1
                    queue.append(nexte)
print(r*c-1 - M[r-1][c-1] - black)