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())
sx,sy=1,1
gx,gy=h,w
w+=2

grh=[list('#')*w]
res=0
for i in range(h):
    tmp=input()
    res+=tmp.count('.')    
    grh+=[list('#'+tmp+'#')]
grh+=[list('#')*w]
h+=2




def bfs():
    que=deque()
    g=[[float('inf')]*w for i in range(h)]
    g[sx][sy]=1
    xy=[(-1,0),(0,-1),(0,1),(1,0)]
    que.append((sx,sy))

    while que:
        x,y=que.popleft()
        if x==gx and y==gy:break
        
        for dx,dy in xy:
            nx=x+dx
            ny=y+dy
            if grh[nx][ny]=='.' and g[nx][ny]==float('inf'):
                que.append((nx,ny))
                g[nx][ny]=g[x][y]+1

    return g[gx][gy]


res-=bfs()
print(res)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

H, W = LI()
c = SR(H)
sy, sx = 0, 0
gy, gx = H-1, W-1

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

def bfs(sy, sx, gy, gx, c, road=".", blocks=["#"]):
    H = len(c)
    W = len(c[0])
    dire = [(1,0), (0,1), (-1,0), (0,-1)]
    dist = [[107]*W for i in range(H)]
    dist[sy][sx] = 0

    q = deque()
    q.append((sy, sx))

    while q:
        y, x = q.popleft()
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (y+dy==gy) and (x+dx==gx):
                        return (dist[y][x]+1)
                    elif (dist[y+dy][x+dx] > dist[y][x]+1):
                        dist[y+dy][x+dx] = dist[y][x]+1
                        q.append((y+dy, x+dx))

    return -1

print(white_counts-bfs(sy, sx, gy, gx, c)-1)

Submission status: Wrong Answer

Solution code:
from queue import Queue

H, W = map(int, input().split())
N = H * W
field = []

dxy_list = [(-1, 0), (0, 1), (1, 0), (0, -1)]

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

for _ in range(H):
    field.append(list(input()))

n_black = 0
for r in field:
    for c in r:
        if c == '#':
            n_black += 1

que = Queue()
que.put((0,0))
cost[0][0] = 1

while not que.empty():
    x, y = que.get()

    if x == H-1 and y == W-1:
        break

    for dxy in dxy_list:
        nx = x + dxy[0]
        ny = y + dxy[1]

        if 0 <= nx < H and 0 <= ny < W and field[nx][ny] != '#' and cost[nx][ny] == INF:
            que.put((nx, ny))
            cost[nx][ny] = cost[x][y] + 1    

print(N - n_black - cost[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from queue import Queue

H, W = map(int, input().split())
N = H * W
field = []

dxy_list = [(-1, 0), (0, 1), (1, 0), (0, -1)]

for _ in range(H):
    field.append(list(input()))

n_black = 0
for r in field:
    for c in r:
        if c == '#':
            n_black += 1

que = Queue()
que.put((0,0,1))

min_c = H * W

while not que.empty():
    x, y, c = que.get()

    field[x][y] = '#'

    if x == H-1 and y == W-1:
        min_c = min(min_c, c)
        continue

    for dxy in dxy_list:
        nx = x + dxy[0]
        ny = y + dxy[1]

        if 0 <= nx < H and 0 <= ny < W and field[nx][ny] == '.':
            que.put((nx, ny, c+1))
    

print(N - n_black - min_c)

Submission status: Wrong Answer

Solution code:
from queue import Queue

H, W = map(int, input().split())
N = H * W
field = []

dxy_list = [(-1, 0), (0, 1), (1, 0), (0, -1)]

for _ in range(H):
    field.append(list(input()))

n_black = 0
for r in field:
    for c in r:
        if c == '#':
            n_black += 1

que = Queue()
que.put((0,0,1))

min_c = H * W

while not que.empty():
    x, y, c = que.get()

    field[x][y] = '#'

    if x == H-1 and y == W-1:
        min_c = min(min_c, c)

    for dxy in dxy_list:
        nx = x + dxy[0]
        ny = y + dxy[1]

        if 0 <= nx < H and 0 <= ny < W and field[nx][ny] == '.':
            que.put((nx, ny, c+1))
    

print(N - n_black - min_c)

Submission status: Wrong Answer

Solution code:
H, W = [int(hw) for hw in input().split()]
S = ""
for h in range(H):
  S += input()
S_nm = S.count("#")
ans = (H-1)*(W-1) - S_nm
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
 
H,W  = map(int, input().split())
sx, sy = 1,1
gx, gy = W,H
count=-1
maze=[0]*(H+2)
maze[0] = list("#"*(W+2))
for i in range(1,H+1):
    maze[i] = list("#"+input()+"#")
    count+=maze[i].count('.')
maze[H+1] = list("#"*(W+2))
ans = [[-1 for i in range(W+2)] for j in range(H+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append((sx, sy))
ans[sx][sy] = 0
 
while q:
    cx, cy = q.popleft()
    if cx == gx and cy == gy:
        print(count-ans[gy][gx])
        break
    for i in range(4):
        nx, ny = cx + dx[i], cy + dy[i]
        if ans[ny][nx] == -1 and maze[ny][nx] != "#":
            q.append((nx, ny))
            ans[ny][nx] = ans[cy][cx] + 1

Submission status: Wrong Answer

Solution code:
from collections import deque
 
H,W  = map(int, input().split())
sx, sy = 1,1
gx, gy = W,H
count=-1
maze=[0]*(H+2)
maze[0] = list("#"*(W+2))
for i in range(1,H+1):
    maze[i] = list("#"+input()+"#")
    count+=maze[i].count('.')
maze[H+1] = list("#"*(W+2))
ans = [[-1 for i in range(W+2)] for j in range(H+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append((sx, sy))
ans[sx][sy] = 0
 
while q:
    cx, cy = q.popleft()
    if cx == gx and cy == gy:
        print(count-ans[gx][gy])
        break
    for i in range(2):
        nx, ny = cx + dx[i], cy + dy[i]
        if ans[nx][ny] == -1 and maze[nx][ny] != "#":
            q.append((nx, ny))
            ans[nx][ny] = ans[cx][cy] + 1

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[-1]*(W) for _ in range(H)]

def check(h,w):
    if dp[h][w] >= 0:
        return dp[h][w]
    elif not(grid[h][w]):
        dp[h][w] = 0
        return dp[h][w]
    elif h == H -1 and w == W - 1 and grid[h][w]:
         dp[h][w] =  1
         return dp[h][w]
    elif h == H - 1:
        for ww in range(w,W):
            if not(grid[h][ww]):
                dp[h][w] = 0
                return dp[h][w]
        dp[h][w] = 1
        return dp[h][w]
    elif w == W - 1:
        for hh in range(h,H):
            if not(grid[hh][w]):
                dp[h][w] = 0
                return dp[h][w]
        dp[h][w] = 1
        return dp[h][w]
    else:
        return check(h+1,w) or check(h,w+1)

black = 0

for gg in grid:
    for ggg in gg:
        if not(ggg):
            black += 1
if check(0,0) and grid[0][0]:
    print(H*W - (H+W-1) - black)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]

def check(h,w):
    if not(grid[h][w]):
        return False
    elif h == H -1 and w == W - 1 and grid[h][w]:
         return True
    elif h == H - 1:
        for ww in range(w,W):
            if not(grid[h][ww]):
                return False
        return True
    elif w == W - 1:
        for hh in range(h,H):
            if not(grid[hh][w]):
                return False
        return True
    else:
        return check(h+1,w) or check(h,w+1)

black = 0

for gg in grid:
    for ggg in gg:
        if not(ggg):
            black += 1
if check(0,0) and grid[0][0]:
    print(H*W - (H+W-1) - black)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
point = -1
kabe = 0
for i in range(H):
    maze.append(input())
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            kabe += 1

def bfs(sy,sx,gy,gx,h,w):
    jikan = 0
    q = deque([sy*w + sx])
    saitan = [1000000]*h*w
    saitan[sy*w + sx] = 0
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and saitan[gy*w +gx] == 1000000:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if maze[my][mx] == 'X':
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
    jikan = saitan[gy*w +gx]
    return jikan

    #print(sg_list[0][0],sg_list[0][1],sg_list[1][0],sg_list[1][1])
    #print('test')
time = bfs(0,0,H-1,W-1,H,W) + 1
if time == 1000000:
    time = H*W
point = point + 1 + (H * W - time - kabe)
print(point)

Submission status: Wrong Answer

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

visit = [[False for j in range(W)] for i in range(H)]


queue = [[0,0]]
count = 0
while len(queue) > 0:
    count += 1
    next = []
    for now in queue:
        visit[now[0]][now[1]] = True
        for i, j in [[0,-1], [1,0], [0,1], [-1,0]]:
            if 0 <= now[0]+i <= H-1 and 0 <= now[1]+j <= W-1:
                if not visit[now[0]+i][now[1]+j]:
                    if grid[now[0]+i][now[1]+j] == ".":
                        next.append([now[0]+i, now[1]+j])
    if visit[-1][-1]:
        break
    queue = next[:]

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

print(H*W-black)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(grid, sy, sx, target, wall):
    grid[sy][sx] = wall
    queue = deque([])
    queue.append([sy, sx, 0])
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if [y_, x_] == target:
                return cnt+1
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_,cnt+1])
            grid[y_][x_] = wall
    return False

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

edges = ['#' for i in range(W+2) ]
grid = [edges]
white = 0
for i in range(H):
    s = input()
    grid.append(['#'])
    for j in range(W):
        grid[i+1].append(s[j])
        white += 1 if s[j] == '.' else 0
    grid[i+1].append('#')
grid.append(edges)

ans = bfs(grid, 1, 1, [H,W], '#')

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

Submission status: Wrong Answer

Solution code:
import math
import queue
R,C = list(map(int,input().split(" ")))


gx=C -1
gy=R - 1
mass = [input() for _ in range(R)]
tejun =[ [-1 for i in range(C)] for j in range(R)]
xy = [(1,0),(0,1),(-1,0),(0,-1)]
q = queue.Queue()
q.put((0,0))
tejun[0][0] = 0
while True:
    if q.empty():
        break
    x,y = q.get()
    if x == gx and y == gy:
        break
    for go in xy:
        xmove,ymove = go
        if 0<=x + xmove < C and 0<=y + ymove < R and mass[y + ymove][x+xmove] != "#":
           if tejun[y + ymove ][x + xmove ] == -1:
               tejun[y + ymove][x + xmove]  = tejun[y][x] + 1
               q.put((x + xmove,y + ymove))
sharp = 0
for temp in mass:
    sharp+= temp.count("#")
ans = R*C -(sharp + (tejun[gy][gx] + 1))
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1
 
def bfs():
    que = Queue()
    que.put((0,0))
    while que.qsize():
        h,w = que.get()
        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0<=h+dh<H and 0<=w+dw<W:
                if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] == INF:
                    cost[h+dh][w+dw] = cost[h][w]+1
                    que.put((h+dh,w+dw))

if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1

def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                bfs(h+dh,w+dw)
bfs(0,0)
if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
d=[(0,1),(1,0),(0,-1),(-1,0)]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s):
    rt=0
    q=deque([(t,s)])
    v[t][s]=1
    while q:
        y,x=q.popleft()
        if (y,x)==(h-1,w-1):  # condtion for finish
            return
        for dx,dy in d:
            if 0<=y+dy<h and 0<=x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    q.append((y+dy,x+dx))
                    v[y+dy][x+dx]=v[y][x]+1
    return -1

bfs(0,0)
dis=v[-1][-1]
ans=wh-dis if dis>=0 else -1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
d=[(0,1),(1,0),(0,-1),(-1,0)]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s):
    rt=0
    q=deque([(t,s)])
    v[t][s]=1
    while q:
        y,x=q.popleft()
        if (y,x)==(h-1,w-1):  # condtion for finish
            return
        for dx,dy in d:
            if 0<=y+dy<h and 0<=x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    q.append((y+dy,x+dx))
                    v[y+dy][x+dx]=v[y][x]+1
    return -1

bfs(0,0)
dis=v[-1][-1]
ans=wh-dis if dis>=0 else dis
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graph = [[float('inf')] * W for _ in range(H)]
offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def bfs(x, y):
    graph[x][y] = 0

    deq = deque()
    deq.append((x, y))
    
    while deq:
        x, y = deq.popleft()
        
        for i, j in offsets:
            if (not 0 <= x + i < H) or (not 0 <= y + j < W):
                continue
                
            if graph[x + i][y + j] < float('inf'):
                continue
                
            if grid[x + i][y + j] == '#':
                continue
                
            graph[x + i][y + j] = graph[x][y] + 1
            deq.append((x + i, y + j))
            

bfs(0, 0)
black = sum(s.count('#') for s in grid)
print(H * W - graph[-1][-1] - black - 1)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

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

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

count = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            if i!=H-1:
                if s[i+1][j]==".":
                    e_list[i*W+j].append((i+1)*W+j)
                    e_list[(i+1)*W+j].append(i*W+j)
            if j!=W-1:
                if s[i][j+1]==".":
                    e_list[i*W+j].append(i*W+j+1)
                    e_list[i*W+j+1].append(i*W+j)
            count+=1

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
N=H*W
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
if min_path_list[H*W-1]<10**9:
    print(count-(1+min_path_list[H*W-1]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

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

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

count = 0
for i in range(H-1):
    for j in range(W-1):
        if s[i][j]==".":
            if i!=H-1:
                if s[i+1][j]==".":
                    e_list[i*W+j].append((i+1)*W+j)
                    e_list[(i+1)*W+j].append(i*W+j)
            if j!=W-1:
                if s[i][j+1]==".":
                    e_list[i*W+j].append(i*W+j+1)
                    e_list[i*W+j+1].append(i*W+j)
            count+=1

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
N=H*W
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
if min_path_list[H*W-1]<10**9:
    print(count-(1+min_path_list[H*W-1]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

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

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

count = 0
for i in range(H-1):
    for j in range(W-1):
        if s[i][j]==".":
            if i!=H-1:
                if s[i+1][j]==".":
                    e_list[i*W+j].append((i+1)*W+j)
                    e_list[(i+1)*W+j].append(i*W+j)
            if j!=W-1:
                if s[i][j+1]==".":
                    e_list[i*W+j].append(i*W+j+1)
                    e_list[i*W+j+1].append(i*W+j)
            count+=1

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
N=H*W
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
if min_path_list[H*W-1]<10**9:
    print(count-(1+min_path_list[H*W-1]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

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

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

count = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            if i!=0:
                if s[i-1][j]==".":
                    e_list[i*W+j].append((i-1)*W+j)
            if i!=H-1:
                if s[i+1][j]==".":
                    e_list[i*W+j].append((i+1)*W+j)
            if j!=0:
                if s[i][j-1]==".":
                    e_list[i*W+j].append(i*W+j-1)
            if j!=W-1:
                if s[i][j+1]==".":
                    e_list[i*W+j].append(i*W+j+1)
            count+=1

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
N=H*W
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
if min_path_list[H*W-1]<10**9:
    print(count-(1+min_path_list[H*W-1]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

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

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

count = 0
for i in range(H):
    for j in range(W):
        if i!=0:
            if s[i][j]=="." and s[i-1][j]==".":
                e_list[i*W+j].append((i-1)*W+j)
        if i!=H-1:
            if s[i][j]=="." and s[i+1][j]==".":
                e_list[i*W+j].append((i+1)*W+j)
        if j!=0:
            if s[i][j]=="." and s[i][j-1]==".":
                e_list[i*W+j].append(i*W+j-1)
        if j!=W-1:
            if s[i][j]=="." and s[i][j+1]==".":
                e_list[i*W+j].append(i*W+j+1)
        if s[i][j]=="#":
            count+=1

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
N=H*W
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
if min_path_list[H*W-1]<10**9:
    print(H*W-count-(1+min_path_list[H*W-1]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

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

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

count = 0
for i in range(H):
    for j in range(W):
        if i!=0:
            if s[i][j]=="." and s[i-1][j]==".":
                e_list[i*W+j].append((i-1)*W+j)
        if i!=H-1:
            if s[i][j]=="." and s[i+1][j]==".":
                e_list[i*W+j].append((i+1)*W+j)
        if j!=0:
            if s[i][j]=="." and s[i][j-1]==".":
                e_list[i*W+j].append(i*W+j-1)
        if j!=W-1:
            if s[i][j]=="." and s[i][j+1]==".":
                e_list[i*W+j].append(i*W+j+1)
        if s[i][j]=="#":
            count+=1

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
N=H*W
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
if min_path_list[H*W-1]<10**27:
    print(H*W-count-(1+min_path_list[H*W-1]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

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

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

count = 0
for i in range(H):
    for j in range(W):
        if i!=0:
            if s[i][j]=="." and s[i-1][j]==".":
                e_list[i*W+j].append((i-1)*W+j)
        if i!=H-1:
            if s[i][j]=="." and s[i+1][j]==".":
                e_list[i*W+j].append((i+1)*W+j)
        if j!=0:
            if s[i][j]=="." and s[i][j-1]==".":
                e_list[i*W+j].append(i*W+j-1)
        if j!=W-1:
            if s[i][j]=="." and s[i][j+1]==".":
                e_list[i*W+j].append(i*W+j+1)
        if s[i][j]=="#":
            count+=1

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
N=H*W
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
if min_path_list[H*W-1]<10**27:
    print(H*W-count-(1+min_path_list[H*W-1]))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
MAP=[["#"]*(W+2)] + [["#"]+list(input())+["#"] for i in range(H)] + [["#"]*(W+2)]
white=0
for line in MAP:
    white+=line.count('.')
from collections import deque
check=deque([(1,1,1)])
dist=float('inf')
while len(check)>0:
    d,x,y=check.popleft()
    for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
        if MAP[x+i][y+j]==".":
            if x+i==H and y+j==W:
                dist=d+1
                check=[]
                break
            check.append((d+1,x+i,y+j))
            MAP[x+i][y+j]="#"
print(white-dist)

Submission status: Wrong Answer

Solution code:
from collections import deque
d=[(0,1),(1,0),(0,-1),(-1,0)]
d=[d[0],d[1]]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s,u):
    rt=0
    q=deque([(t,s,u)])
    while q:
        y,x,depth=q.popleft()
        v[y][x]=1
        if (y,x)==(h-1,w-1):  # condtion for finish
            return depth
        for dx,dy in d:
            if 0<=y+dy<h and 0<=x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    q.append((y+dy,x+dx,depth+1))
    return -1

dis=bfs(0,0,1)
ans=wh-dis if dis>=0 else dis
print(ans)

Submission status: Wrong Answer

Solution code:
d=[(0,1),(1,0),(0,-1),(-1,0)]
d=[d[0],d[1]]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s,u):
    rt=0
    q=[(t,s,u)]
    while q:
        y,x,depth=q.pop()
        v[y][x]=1
        if (y,x)==(h-1,w-1):  # condtion for finish
            return depth
        for dx,dy in d:
            if y+dy<h and x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    rt+=1   # action for return value
                    q.append((y+dy,x+dx,depth+1))
                    #print(y,x)
    return -1

dis=bfs(0,0,1)
ans=wh-dis if dis>=0 else dis
print(ans)

Submission status: Wrong Answer

Solution code:
d=[(0,1),(1,0),(0,-1),(-1,0)]
d=[d[0],d[1]]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s,depth):
    rt=0
    q=[(t,s,depth)]
    while q:
        y,x,depth=q.pop()
        v[y][x]=1
        if (y,x)==(h-1,w-1):  # condtion for finish
            return depth
        for dx,dy in d:
            if y+dy<h and x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    rt+=1   # action for return value
                    q.append((y+dy,x+dx,depth+1))
                    #print(y,x)
    return -1

dis=bfs(0,0,1)
ans=wh-dis if dis>=0 else dis
print(ans)

Submission status: Wrong Answer

Solution code:
d=[(0,1),(1,0),(0,-1),(-1,0)]
d=[d[0],d[1]]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s,depth):
    rt=0
    q=[(t,s,depth)]
    while q:
        y,x,depth=q.pop()
        v[y][x]=1
        if (y,x)==(h-1,w-1):  # condtion for finish
            return depth
        for dx,dy in d:
            if y+dy<h and x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    rt+=1   # action for return value
                    q.append((y+dy,x+dx,depth+1))
                    #print(y,x)
    return rt

dis=bfs(0,0,1)
ans=wh-dis
print(ans)

Submission status: Wrong Answer

Solution code:
d=[(0,1),(1,0),(0,-1),(-1,0)]
d=[d[0],d[1]]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s):
    rt=0
    q=[(t,s)]
    while q:
        y,x=q.pop()
        v[y][x]=1
        if (y,x)==(h-1,w-1):  # condtion for finish
            return rt
        for dx,dy in d:
            if y+dy<h and x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    rt+=1   # action for return value
                    q.append((y+dy,x+dx))
                    #print(y,x)
    return rt

ans=wh-bfs(0,0)
print(ans)#,wh,a,d)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y,visit, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        global dist
        if n < dist:
            dist = n
        return 0
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y,visit, n+1)
        dfs(x, y+1, visit,n+1)
        dfs(x-1, y,visit,  n+1)
        dfs(x, y-1, visit, n+1)
dfs(0, 0,[[0]*W for _ in range(H)] ,1)
if dist == 10**9:
    print(-1)
else:
    print(white - dist)