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

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

print(score - bfs(1,1) - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
INF = float("inf")
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

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

dist = 0 
while que:
    dist += 1
    flag = False

    for i in range(len(que)):
        x, y = que.popleft()
        if x == w-1 and y == h-1:
            flag = True
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and done[ny][nx] == 0:
                que.append((nx, ny))
                done[ny][nx] == 1
    if flag:
        break

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

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(sy,sx):
    dis=[[0]*W for i in range(H)]
    q=deque()
    q.append([sy,sx])
    while(len(q)!=0):
        y=q[0][0]
        x=q[0][1]
        q.popleft()
        for dy,dx in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if field[ny][nx]=="#":
                continue
            if dis[ny][nx]!=0:
                continue
            dis[ny][nx]=dis[y][x]+1
            q.append([ny,nx])
    return dis[H-1][W-1]


H,W=map(int,input().split())
field=[input() for i in  range(H)]
O=0
for i in range(H):
    O+=field[i].count(".")
ans=O-1-bfs(0,0)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]
def bfs(y, x):
    for i in range(4):
        next_y = y + dir_y[i]
        next_x = x + dir_x[i]
        if 0 <= next_y < H and 0 <= next_x < W and maze[next_y][next_x] == "." and dist[next_y][next_x] == -1:
            que.append((next_y, next_x))
            dist[next_y][next_x] = dist[y][x] + 1


H, W = map(int, input().split())
sy, sx = 0, 0
maze = []
empty_count = 0
for i in range(H):
    maze.append(input())
    empty_count += maze[i].count(".")

dist = [[-1]*(W+1) for _ in range(H+1)]
dist[sy][sx] = 0
que = deque([(sy, sx)])

while len(que) > 0:
    y, x = que.popleft()
    bfs(y, x)

print(empty_count - (dist[H-1][W-1] + 1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]

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

while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))

ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')

if maze[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]

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

while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))

black_num = 0
for m in maze:
    black_num += m.count('#')

print(w*h - black_num - dis[h-1][w-1])

Submission status: Wrong Answer

Solution code:
# 経路復元

from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10 ** 9)

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

field = [list(input()) for i in range(H)]

queue = deque([])
seen = [[0] * W for i in range(H)]
prev_x = [[0] * W for i in range(H)]
prev_y = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(y, x):
    queue.append([y, x])
    seen[y][x] = 1
    prev_x[y][x] = -1
    prev_y[y][x] = -1

    while len(queue) != 0:
        y, x = queue.popleft()

        for dy, dx in direction:
            next_x = x + dx
            next_y = y + dy

            if next_x < 0 or next_x >= W or next_y < 0 or next_y >= H:
                continue
            elif field[next_y][next_x] == "#":
                continue
            elif seen[next_y][next_x] != 0:
                continue
            else:
                seen[next_y][next_x] = 1
                prev_x[next_y][next_x] = x
                prev_y[next_y][next_x] = y
                queue.append([next_y, next_x])


shortest_path = [[0] * W for i in range(H)]


def path_restoration(y, x):
    shortest_path[y][x] = 1

    if prev_x[y][x] == -1 and prev_y[y][x] == -1:
        return
    else:
        next_y = prev_y[y][x]
        next_x = prev_x[y][x]
        path_restoration(next_y, next_x)


bfs(0, 0)
path_restoration(H - 1, W - 1)

ans = 0

for i in range(H):
    for j in range(W):
        if field[i][j] == "." and shortest_path[i][j] == 0:
            field[i][j] = "#"
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
visited = [[-1] * w for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

sy, sx= 0, 0
gy, gx = h-1, w-1

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

while queue:
    y, x, dist = queue.popleft()
    for dy, dx in move:
        if maze[y+dy:y+dy+1] and maze[y+dy][x+dx:x+dx+1]:
            if maze[y+dy][x+dx] == "." and visited[y+dy][x+dx] == -1:
                visited[y+dy][x+dx] = dist + 1
                queue.append((y+dy, x+dx, dist+1))
shortest_distance = visited[gy][gx]

white_count = 0
for row in maze:
    for cell in row:
        if cell == ".":
            white_count += 1

score = white_count - shortest_distance - 1
print(score)

Submission status: Wrong Answer

Solution code:
def main():
    height, width = map(int, input().split())
    grid = []
    initial_white = 0
    for _ in range(height):
        g = input()
        initial_white += g.count(".")
        grid.append(list(g))
    count = [[0 for _ in range(width)] for _ in range(height)]
    next_search = [(0, 0)]
    grid[0][0] = "#"
    while not next_search == []:
        now = next_search.pop(0)
        for d in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            next_index = (now[0] + d[0], now[1] + d[1])
            if next_index[0] < 0 or height <= next_index[0] or next_index[1] < 0 or width <= next_index[1]:
                continue
            elif grid[next_index[0]][next_index[1]] == ".":
                grid[next_index[0]][next_index[1]] = "#"
                count[next_index[0]][next_index[1]] = count[now[0]][now[1]] + 1
                next_search.append(next_index)
    print(initial_white - count[-1][-1] - 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

que = deque([[0,0]])
seen = [[-1]*W for _ in range(H)]
seen[0][0] = 0
count = 0
for i in range(H):
    for j in range(W):
        if map[i][j]=="#":
            seen[i][j] = -2
        else:
            count +=1

while que:
    y, x = que.popleft()
    if y == H-1 and x == W-1:
        break
    for dy, dx in ([0,1],[1,0],[0,-1],[-1,0]):
        ny, nx = y+dy, x+dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1 and map[ny][nx] != "#":
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny, nx])

#print(*seen, sep="\n")
#print("\n")
max = seen[H-1][W-1]

cnt = count-max-1

print(cnt)

Submission status: Wrong Answer

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

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

for i in range(H):
    for j in range(W):
        if map[i][j]=="#":
            seen[i][j] = -2

while que:
    y, x = que.popleft()
    if y == H-1 and x == W-1:
        break
    for dy, dx in ([0,1],[1,0],[0,-1],[-1,0]):
        ny, nx = y+dy, x+dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1 and map[ny][nx] != "#":
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny, nx])

#print(*seen, sep="\n")
#print("\n")
max = seen[H-1][W-1]
cnt = 0
for num in range(H*W+1):
    count = 0
    for y in range(H):
        for x in range(W):
            if seen[y][x] == num-1:
                count += 1
    if 0<=num-1 <= max:
        cnt += count-1
    else:
        cnt += count

print(cnt)

Submission status: Wrong Answer

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

from collections import deque
def bfs(maze, sy, sx, gy, gx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    #print(que)
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w  and 0 <= ny < h  and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    return d[gy][gx]
#bfs()

gx, gy = w - 1, h - 1
def counting(maze, h, w, aim):
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == aim:
                cnt += 1
    return cnt
a = bfs(maze, 0, 0, gy, gx)

print(h * w - (counting(maze, h, w, '#') + (a + 1)))

Submission status: Wrong Answer

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


q = deque([[0,0]])
visit[0][0] = 1
while q:
    px, py = q.popleft()
    for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
        if px+i >= 0 and px+i < h and py+j > 0 and py+j < w:
            if bord[px+i][py+j] == "." and visit[px+i][py+j] < 0:
                visit[px+i][py+j] = visit[px][py]+1
                q.append([px+i, py+j])
if visit[h-1][w-1] < 0:
    print(-1)
else:
    c = [i.count(".") for i in bord]
    print(sum(c)-visit[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
H, W = [int(x) for x in input().split()]
s = []
W_count = 0
for _ in range(H):
    tmp = list(input().rstrip())
    s.append(tmp)
    W_count += tmp.count('.')

from collections import deque
D = [[-1] * W for _ in range(H)]

def bfs():
    queue = deque([(0, 0, 0, 0)])
    D[0][0] = 0
    while queue:
        u = queue.popleft()
        x = u[0]
        y = u[1]
        D[x][y] = D[u[2]][u[3]] + 1
        for i in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if 0 <= i[0] < H and 0 <= i[1] < W and D[i[0]][i[1]] < 0 and s[i[0]][i[1]] == ".":
                queue.append((i[0], i[1], x, y))
    return D

D = bfs()

print(W_count - D[-1][-1])

Submission status: Wrong Answer

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

def bfs():
    q = deque([[0, 0]])
    visited = [[0]*W for _ in range(H)]
    visited[0][0] = 1
    dist[0][0] = 0

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

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

print(ans-dist[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
S = []
for _ in range(h):
    s = str(input())
    S.append(s)

deque = deque()
deque.append([0,0])
Visited=[[-1 for _ in range(w)] for _ in range(h)]
Visited[0][0] = 0

while deque:
    now = deque.popleft()
    x_now = now[0]
    y_now = now[1]

    Cands = []
    For_cands = [-1,0,1]
    for i in For_cands:
        for j in For_cands:
            if i == j or i == j*-1:
                continue
            if x_now + i < w and x_now +i >=0 and y_now +j < h and y_now + j >=0:
                if S[y_now+j][x_now+i] == '.':
                    Cands.append([x_now+i, y_now+j])
    for cands in Cands:
        if Visited[cands[1]][cands[0]] != -1:
            continue
        deque.append(cands)
        Visited[cands[1]][cands[0]] = Visited[y_now][x_now] + 1

goal_dist = Visited[h-1][w-1]

white = 0
for i in range(h):
    white += S[i].count('.')

ans = white - goal_dist -1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def mbfs(S,H,W,sh,sw):
    dist=[[-1]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(dist[nh][nw]!=-1 or S[nh][nw]=='#'):
                continue
            dist[nh][nw]=dist[h][w]+1
            S[nh][nw]=='#'
            d.append([nh,nw])
    return dist

H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(input())
cnt=0
for i in range(H):
    for j in range(W):
        if(S[i][j]=='#'):
            cnt+=1


li=mbfs(S,H,W,0,0)
print(H*W-cnt-(li[H-1][W-1]+1))

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [input() for i in range(H)]
T = [[False]*W for i in range(H)]
Q = [(1,0,0)]
cnt = 0
while Q:
    q = Q.pop(0)
    if min(q)<0 or q[1]>=H or q[2]>=W:continue
    if S[q[1]][q[2]]=="#" or T[q[1]][q[2]]:continue
    if q[1]==H-1 and q[2]==W-1:
        cnt = q[0]
        break
    T[q[1]][q[2]]=True
    Q.append((q[0]+1,q[1]+1,q[2]))
    Q.append((q[0]+1,q[1]-1,q[2]))
    Q.append((q[0]+1,q[1],q[2]+1))
    Q.append((q[0]+1,q[1],q[2]-1))
ans = 0
for s in S:ans+=s.count(".")
print(ans-cnt)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [input() for i in range(H)]
T = [[False]*W for i in range(H)]
Q = [(1,0,0)]
cnt = 0
while Q:
    q = Q.pop(0)
    if min(q)<0 or q[1]>=H or q[2]>=W:continue
    if S[q[1]][q[2]]=="#" or T[q[1]][q[2]]:continue
    if q[1]==H-1 and q[2]==W-1:
        cnt = q[0]
        break
    T[q[1]][q[2]]=True
    Q.append((q[0]+1,q[1]+1,q[2]))
    Q.append((q[0]+1,q[1]-1,q[2]))
    Q.append((q[0]+1,q[1],q[2]+1))
    Q.append((q[0]+1,q[1],q[2]-1))
    print(q)
ans = 0
for s in S:ans+=s.count(".")
print(ans-cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
import sys

H,W=map(int,input().split())
maze=[[0]*W for _ in range(H)]
b=0                  # ブロックの数
for i in range(H):
  a=str(input())
  for j in range(W):
    if a[j]=='#':
      b+=1
    maze[i][j]=a[j]
def BFS(maze,s,g):
  que=deque()
  sy,sx=s[0],s[1]
  gy,gx=g[0],g[1]
  que.append([sx,sy])
  dist=[[0]*W for _ in range(H)]
  seen=[]
  seen.append([sx,sy])   
  Next=[[-1,0],[1,0],[0,1],[0,-1]]
  while len(que)!=0:
    l=que.popleft()
    for n in Next:
      x,y=l[0]+n[0],l[1]+n[1]
      if (x<0 or x>=W or y<0 or y>=H) or maze[y][x]=='#':
        pass
      else:
        if [x,y] not in seen:
          seen.append([x,y])
          que.append([x,y])
          dist[y][x]=dist[l[1]][l[0]]+1
  return dist[gy][gx]

d=BFS(maze,[0,0],[H-1,W-1])
if d==1:
  print(-1)    # このときたどり着けない
else:
  print(H*W-(d+1)-b)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
import sys

H,W=map(int,input().split())
maze=[[0]*W for _ in range(H)]
b=0                  # ブロックの数
for i in range(H):
  a=str(input())
  for j in range(W):
    if a[j]=='#':
      b+=1
    maze[i][j]=a[j]
def BFS(maze,s,g):
  que=deque()
  sy,sx=s[0],s[1]
  gy,gx=g[0],g[1]
  que.append([sx,sy])
  dist=[[0]*W for _ in range(H)]
  seen=[]
  seen.append([sx,sy])   
  Next=[[-1,0],[1,0],[0,1],[0,-1]]
  while len(que)!=0:
    l=que.popleft()
    for n in Next:
      x,y=l[0]+n[0],l[1]+n[1]
      if (x<0 or x>=W or y<0 or y>=H) or maze[y][x]=='#':
        pass
      else:
        if [x,y] not in seen:
          seen.append([x,y])
          que.append([x,y])
          dist[y][x]=dist[l[1]][l[0]]+1
  return dist[gy][gx]

d=BFS(maze,[0,0],[H-1,W-1])
print(H*W-(d+1)-b)

Submission status: Wrong Answer

Solution code:
from collections import deque


h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
dist=[[0 for i in range(w)] for j in range(h)]
que=deque([])
que.append([0,0])
dyx=[[1,0],[0,-1],[-1,0],[0,1]]
ndot=0
for i in range(h):
  for j in range(w):
    if s[i][j]==".":
      ndot+=1
s[0][0]="#"

while que:
  y,x=que.popleft()
  for dy,dx in dyx:
    nx=x+dx
    ny=y+dy
    if (nx<0 or nx>w-1 or ny<0 or ny>h-1):
      continue
    if s[ny][nx]==".":
      dist[ny][nx]=dist[y][x]+1
      que.append([ny,nx])
      s[ny][nx]="#"

ans=ndot-dist[h-1][w-1]-1
if ans<0:
  ans=-1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

[H, W] = [int(i) for i in input().split()]

gh = H - 1
gw = W - 1

S = []
for h in range(H):
    S.append(list(input()))

# 最短経路を求める
queue = [(0, 0, 0)]
min_route = 0
while len(queue) > 0:
    (y, x, r) = queue.pop(0)
    if S[y][x] == 'X':
        continue
    S[y][x] = 'X'
    r += 1

    if y == gh and x == gw:
        min_route = r
        break

    # 上下左右の移動可能マスをqueueにpush
    for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ny = y + dy
        nx = x + dx
        if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == '.':
            queue.append((ny, nx, r))

# 最短経路分以外の白マスの数を回答
white_square = 0
for h in range(H):
    white_square += S[h].count('.')
    white_square += S[h].count('X')

ans = white_square - min_route
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
area = [list(input()) for i in range(H)]
def calc(area):
    count = 0
    for i in range(H):
        for j in range(W):
            if area[i][j] == '#':
                count += 1
    
    return count

dist = [[-1 for i in range(W)] for i in range(H)]
dist[0][0] = 0
que = [[0,0]]

dh = [1,0,-1,0]
dw = [0,1,0,-1]

while len(que) != 0:
    idx = que.pop(0)
    
    for i in range(4):
        h = idx[0] + dh[i]
        w = idx[1] + dw[i]
        
        if h >= 0 and h < H and w >= 0 and w < W and dist[h][w] == -1 and area[h][w] != '#':
            que.append([h, w])
            dist[h][w] = dist[idx[0]][idx[1]] + 1
    
print(H*W - dist[H-1][W-1] - calc(area) -1)

Submission status: Wrong Answer

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

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

q = deque([(0, 0)])
d = [[0]*w for _ in range(h)]
visited = set([])
while q:
    i, j = q.popleft()
    visited.add(str(i)+str(j))
    for k in range(4):
        ni = i + dx[k]
        nj = j + dy[k]
        if ni < 0 or h <= ni:
            continue
        if nj < 0 or w <= nj:
            continue
        if mass[ni][nj] == "#":
            continue
        if not "{}{}".format(ni, nj) in visited:
            q.append((ni, nj))
            d[ni][nj] = d[i][j] + 1
        if ni == h-1 and nj == w-1:
            break
    else:
        continue
    break

if d[h-1][w-1] == 0:
    print(-1)
else:
    print(ans - d[h-1][w-1] - 1)

Submission status: Wrong Answer

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

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

q1 = deque([0])
q2 = deque([0])
d = [[0]*w for _ in range(h)]
visited = [[0]*w for _ in range(h)]

Submission status: Wrong Answer

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

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

q1 = deque([0])
q2 = deque([0])
d = [[0]*w for _ in range(h)]
visited = [[0]*w for _ in range(h)]
while q1:
    i = q1.popleft()
    j = q2.popleft()
    visited[i][j] = 1
    for k in range(4):
        ni = i + dx[k]
        nj = j + dy[k]
        if ni < 0 or h <= ni:
            continue
        if nj < 0 or w <= nj:
            continue
        if mass[ni][nj] == "#":
            continue
        if not visited[ni][nj]:
            q1.append(ni)
            q2.append(nj)
            d[ni][nj] = d[i][j] + 1

Submission status: Wrong Answer

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

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

q1 = deque([0])
q2 = deque([0])
d = [[0]*w for _ in range(h)]
visited = [[0]*w for _ in range(h)]
while q1:
    i = q1.popleft()
    j = q2.popleft()
    visited[i][j] = 1
    for k in range(4):
        ni = i + dx[k]
        nj = j + dy[k]
        if ni < 0 or h <= ni:
            continue
        if nj < 0 or w <= nj:
            continue

        if mass[ni][nj] == "#":
            continue
        if not visited[ni][nj]:
            q1.append(ni)
            q2.append(nj)
            d[ni][nj] = d[i][j] + 1

if d[h-1][w-1] == 0:
    print(-1)
else:
    ans = 0
    for i in visited:
        ans += sum(i)
    print(ans - d[h-1][w-1] - 1)

Submission status: Wrong Answer

Solution code:
# 迷路読み込み
h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]

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

for i in range(h):
    maze[i]=['#']+maze[i]+['#']
maze=[['#' for i in range(w+2)]]+maze+[['#' for i in range(w+2)]]
# 迷路　BFS
import collections
from collections import deque
def clear_maze(sx, sy, gx, gy):

    INF=-10**9
    distance = [[INF for i in range(w+1)] for j in range(h+1)]
    #    distance = [[None]*field_x_length]*field_y_length
    def bfs():
        d = deque()
        d.appendleft((sx, sy))
        distance[sx][sy] = 0

        while len(d):
            x, y = d.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and  0 <= ny  and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    d.appendleft ((nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

        return distance[gx][gy]

    return bfs()
v=clear_maze(1,1,h,w)
print(ans-v-1)

Submission status: Wrong Answer

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

from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '#': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))
w = sum(row.count('.') for row in S)
print(w - 1 - dist[-1][-1])

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('.')
    s.append(['#'] + h + ['#'])
s = [['#'] * (W+2)] + s + [['#'] * (W+2)]
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]

ans, que, already = count + 1, queue.Queue(), set([1 + H])
que.put([1, 1, 1])
while not que.empty():
    q = que.get()
    if q[0] == W and q[1] == H:
        ans = q[2]
        Goal = True
        break
    else:
        for a in around:
            nextx, nexty = q[0] + a[0], q[1] + a[1]
            if nextx + H*nexty not in already and s[nexty][nextx] == '.':
                que.put([nextx, nexty, q[2] + 1])
                already.add(nextx + H*nexty)

print(count - ans)

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('.')
    s.append(['#'] + h + ['#'])
s = [['#'] * (W+2)] + s + [['#'] * (W+2)]
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]

ans, que, already = count + 1, queue.Queue(), set([1 + H])
que.put([1, 1, 1])
while not que.empty():
    q = que.get()
    if q[0] == W and q[1] == H:
        ans = q[2]
        Goal = True
        break
    elif q[0] + H*q[1] not in already:
        for a in around:
            nextx, nexty = q[0] + a[0], q[1] + a[1]
            if s[nexty][nextx] == '.':
                que.put([nextx, nexty, q[2] + 1])
                already.add(nextx + H*nexty)

print(count - ans)

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('.')
    s.append(['#'] + h + ['#'])
s = [['#'] * (W+2)] + s + [['#'] * (W+2)]
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]

ans, que, already, Goal = count + 1, queue.Queue(), set(), False
que.put([1, 1, 1])
while not que.empty():
    q = que.get()
    if q[0] == W and q[1] == H:
        ans = q[2]
        Goal = True
        break
    elif q[0] + H*q[1] in already:
        continue
    else:
        already.add(q[0] + H*q[1])

    for a in around:
        nextx, nexty = q[0] + a[0], q[1] + a[1]
        if s[nexty][nextx] == '.':
            que.put([nextx, nexty, q[2] + 1])
if Goal:
    print(count - ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('.')
    s.append(['#'] + h + ['#'])
s = [['#'] * (W+2)] + s + [['#'] * (W+2)]
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]

ans, que, already = count + 1, queue.Queue(), set()
que.put([1, 1, 1])
while not que.empty():
    q = que.get()
    if q[0] == W and q[1] == H:
        ans = q[2]
        break
    elif q[0] + H*q[1] in already:
        continue
    else:
        already.add(q[0] + H*q[1])

    for a in around:
        nextx, nexty = q[0] + a[0], q[1] + a[1]
        if s[nexty][nextx] == '.':
            que.put([nextx, nexty, q[2] + 1])

print(count - ans)

Submission status: Wrong Answer

Solution code:

from pprint import pprint
INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]
# 入力
h, w = map(int, input().split())
maze = []
wallcount = 0
for i in range(h):
    l = list(input())
    maze.append(l)
    wallcount += l.count("#")

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx and nx < w and -1 < ny and ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
import itertools
res = list(itertools.chain(*dp))# 二次元配列を一次元にして
needstep = dp[0][-1]
res = h * w
res -= wallcount
res -= needstep + 1
print(res)