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
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


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)
print(r*c-1 - M[r-1][c-1] - black)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = [input() for _ in range(H)]
num = sum([n.count('#') for n in C])
ans = H * W - (num + H + W - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
# H, W = map(int, input().split())
# C = [input() for _ in range(H)]
# num = sum([n.count('#') for n in C])
# ans = H * W - (num + H + W - 1)
# print(ans)

from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(S, G):

    visited = [[False] * W for _ in range(H)]
    c = 0

    visited[S[0]][S[1]] = True
    que = deque([(S[0], S[1], 0)])

    while que:
        ci, cj, c = que.popleft()

        if ci == G[0] and cj == G[1]:
            return c

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and C[ni][nj] != '#':
                visited[ni][nj] = True
                que.append((ni, nj, c+1))
    return 0


sg = [[0, 0], [H-1, W-1]]
ans = 0
ans += bfs(sg[0], sg[1])

if ans == 0:
    print('-1')
else:
    num = sum([n.count('#') for n in C])
    result = H * W - (num + H + W - 1)
    print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(S, G):

    visited = [[False] * W for _ in range(H)]
    c = 0

    visited[S[0]][S[1]] = True
    que = deque([(S[0], S[1], 0)])

    while que:
        ci, cj, c = que.popleft()

        if ci == G[0] and cj == G[1]:
            return c

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and C[ni][nj] != '#':
                visited[ni][nj] = True
                que.append((ni, nj, c+1))
    return 0


sg = [[0, 0], [H-1, W-1]]
ans = 0
ans += bfs(sg[0], sg[1])

if not ans:
    print(-1)
else:
    num = sum([n.count('#') for n in C])
    result = H * W - (num + H + W - 1)
    print(result)

Submission status: Wrong Answer

Solution code:
r, c = map(int, input().split())
cc = [input() for i in range(r)]
 
from collections import deque
 
 
# 縦がｙ 横がx　だから座標はy,xて書く
 
 
# 保留スタックtodoにスタートの位置情報を入れる
todo=deque([[0,0]])
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]
 
# 黒を数える
bcount=0
for i in range(r):
    bcount+=cc[i].count("#")
 
# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
seen[0][0]=0
 
# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]
 
f=0
# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.pop() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
    if seen[r-1][c-1]!=-1:
        f=1
        break
if f==1: #到達可能
    # 面積-ゴールまでの最短手数-1(スタートのマス分)-元々あった黒のマス
    print(r*c-seen[r-1][c-1]-1-bcount)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
r, c = map(int, input().split())
cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く


# 保留スタックtodoにスタートの位置情報を入れる
todo=deque([[0,0]])
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# 黒を数える
bcount=0
for i in range(r):
    bcount+=cc[i].count("#")

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
seen[0][0]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]

# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
    if seen[r-1][c-1]!=-1:
        break
# 面積-ゴールまでの最短手数-1(スタートのマス分)-元々あった黒のマス
print(r*c-seen[r-1][c-1]-1-bcount)

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(start):
    Q = deque()
    child = deque()
    Q.append(start)
    dist[start[1] - 1][start[0] - 1] = 0

    while Q:
        x, y = Q.popleft()
        x = x - 1
        y = y - 1

        for i in range(4):
            child.clear()
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] != -1:
                continue

            child.append((nx + 1, ny + 1))

            if len(child) > 0:
                for c in child:
                    dist[c[1] - 1][c[0] - 1] = dist[y][x] + 1
                    Q.append(c)


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

kuro = 0
for i in range(H):
    G[i] = list(input())
    kuro += G[i].count('#')

dist = [[-1 for _ in range(W)] for _ in range(H)]
dx = [1, 0, -1, 0]  # 斜めも含むならその方向もプラス
dy = [0, 1, 0, -1]

start = (1, 1)
bfs(start)

# for i in range(H):
#     print(dist[i])

res = H * W - (dist[H - 1][W - 1] + 1) - kuro
print(res)

Submission status: Wrong Answer

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

def bfs(sx, sy):
    ans = 10**9
    dire = ((0, -1), (-1, 0), (1, 0), (0, 1))
    dist = [[-1]*W for _ in range(H)] # 未訪問は-1,訪問済みは距離
    dist[sx][sy] = 1
    que = deque([(sx, sy)]) # (sx, sy)からスタート
    while que:
        x, y = que.popleft()
        d = dist[x][y]
        for dx, dy in dire:
            nx,ny = x+dx,y+dy
            if nx==H-1 and ny==W-1:
                ans = min(d+1,ans)
            # 内部で、通行可能('.')で、未訪問なら距離を更新し、dequeに入れる
            if 0<=nx<H and 0<=ny<W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                dist[nx][ny] = d+1
                que.append((nx, ny))
    return ans # これは(sx,sy)からの最長距離
black = 0
ans = bfs(0,0)

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

print(H*W-ans-black)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(maze, sy, sx):
    h = len(maze)
    w = len(maze[0])
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    d = deque([[sy, sx]])
    visited[sy][sx] = 0
    while d:
        y, x = d.popleft()
        
        for k, l in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + k, x + l
            if new_y < 0 or h <= new_y or new_x < 0 or w <= new_x:
                continue
            elif visited[new_y][new_x] != -1:
                continue
            elif maze[new_y][new_x] == '#':
                continue
            
            d.append([new_y, new_x])
            visited[new_y][new_x] = visited[y][x] + 1
    
    return visited

if __name__ == "__main__":
    h, w = map(int, input().split())
    maze = []
    cnt = 0
    for i in range(h):
        maze.append(input())
        cnt += maze[i].count('.')
        
    visited = bfs(maze, 0, 0)
    goal = visited[h - 1][w - 1]
    
    print(cnt - goal - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h , w = map(int,input().split())
ma = [["#"]*(w+2)]
cou = 0
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    cou += kar.count(".")
    kar.append("#")
    ma.append(kar)
ma.append(["#"]*(w+2))

ans = [[-1 for i in range(w+2)] for j in range(h+2)]
ans[1][1] = 1
q = deque([(1,1)])

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    if ma[x-1][y] == ".":
        q.append((x-1,y))
        ans[x-1][y] = ans[x][y] + 1
    if ma[x+1][y] == ".":
        q.append((x+1,y))
        ans[x+1][y] = ans[x][y] + 1        
    if ma[x][y-1] == ".":
        q.append((x,y-1))
        ans[x][y-1] = ans[x][y] + 1        
    if ma[x][y+1] == ".":
        q.append((x,y+1))
        ans[x][y+1] = ans[x][y] + 1

print(cou - ans[h][w])

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=10**3


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]

    D[0][0]=1
    color[0][0]="gray"
    queue=deque([[0,0]])
    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=a+c,b+d
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and color[X][Y]=="white":
                    D[X][Y]=min(D[X][Y],D[a][b]+1)
                    color[X][Y]="gray"
                    queue.append([X,Y])
        color[a][b]="black"

    return D[-1][-1]


h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]
D=BFS()
black=sum([S[i].count("#") for i in range(h)])
print(h*w-D-black)

Submission status: Wrong Answer

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

M = [[-1] * W for _ in range(H)]


q = deque()
q.append((0, 0))
M[0][0] = 1

while q:
    p = q.popleft()

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    for d in directions:
        x = p[0] + d[0]
        y = p[1] + d[1]

        if 0 <= x and x < W and 0 <= y and y < H:
            if M[y][x] == -1 and S[y][x] == ".":
                M[y][x] = M[p[1]][p[0]] + 1
                q.append((x, y))

minD = M[H-1][W-1]
count = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            count += 1

print(count-minD)

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import sys
from collections import deque
inf = 10**15
mod = 10**9+7
R, C = map(int, input().split())
maps = [input() for i in range(R)]
whole = R*C
defoB = 0
for s in maps:
    for c in s:
        if c == '#':
            defoB+=1
dis = [[-1 for j in range(C)] for i in range(R)]

def bfsC(init_y, init_x, goal_y, goal_x):
    q = deque([[init_y, init_x]])
    dis[init_y][init_x] = 0
    while q:
        y, x = q.popleft()
        if y == goal_y and x == goal_x:
            return dis[y][x]
        distance = dis[y][x]+1
        for dy, dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0 <= y+dy < R and 0 <= x+dx < C and maps[y+dy][x+dx] != '#' and dis[y+dy][x+dx] == -1:
                q.append([y+dy, x+dx])
                dis[y+dy][x+dx] = distance
    return -1 # (見つからなかった)

result = bfsC(0, 0, R-1, C-1) + 1
if result != -1:
    print(whole - result - defoB)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys #sys.exit()に使う。
from collections import deque

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

p = [str(input()) for _ in range(H)]

reached = [[float("inf")]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
reached[0][0] = 1
queue = deque([[0,0]])

while queue:
  x,y = queue.popleft()
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    if 0<=nx<H and 0<=ny<W and p[nx][ny] != "#" and reached[nx][ny] > H*W:
      queue.append([nx,ny])
      reached[nx][ny] = reached[x][y] + 1
    if nx == H-1 and ny == W-1:
      reached[nx][ny] = reached[x][y] + 1
      break

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

ans = shiro - reached[H-1][W-1]
if ans >= 0:
  print(ans)
else:
  print("-1")

Submission status: Wrong Answer

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

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            cmap[l[0]]=cmap[l[0]][:l[1]] + "#" + cmap[l[0]][l[1]+1:]
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2
finishflag=True

while finishflag:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    todo.extend(nextlist)
    print(i)

    if todo == []:
        finishflag = False

    i += 1

print("-1")

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(sx, sy):
    queue = deque([[sx, sy]])
    visit[sx][sy] = 0
    while queue:
        x, y = queue.popleft()
        if [x, y] == [gx, gy]:
            return visit[x][y]
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or h <= nx or ny < 0 or w <= ny or graph[nx][ny] == "#":
                continue
            elif graph[nx][ny] == "." and visit[nx][ny] == -1:
                visit[nx][ny] = visit[x][y] + 1
                queue.append([nx, ny])

h, w = map(int, input().split())
graph = [list(input()) for _ in range(h)]
visit = [[-1 for _ in range(w)] for _ in range(h)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

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

cnt = 0
for i in range(h):
    for j in range(w):
        if graph[i][j] == "#":
            cnt += 1

bfs(sx, sy)
if visit[gx][gy] == -1:
    print(-1)
else:
    print(h * w - max(max(visit)) - cnt - 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

directions = [[1,0],
             [-1,0],
             [0,1],
             [0,-1]]

seen = [[False for _ in range(W)] for _ in range(H)]
answer = [[-10000 for _ in range(W)] for _ in range(H)]
answer[0][0] = 0

todo = deque([[0,0]])
seen[0][0] = True
while len(todo) > 0:
    checking = todo.pop()
    for direction in directions:
        moved = [checking[0] + direction[0], checking[1] + direction[1]]
        if moved[0] < 0 or moved[0] >= H or moved[1] < 0 or moved[1] >= W:
            continue
        if seen[moved[0]][moved[1]] == False and s[moved[0]][moved[1]] ==".":
            seen[moved[0]][moved[1]] = True
            answer[moved[0]][moved[1]] = answer[checking[0]][checking[1]] + 1
            todo.append([moved[0], moved[1]])

if answer[-1][-1] == -10000:
    print("-1")
else:
    print(root_num - (answer[-1][-1] + 1))

Submission status: Wrong Answer

Solution code:

from collections import deque

H, W = map(int, input().split())
s = [list(input().rstrip('\n')) for _ in range(H)]

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

directions = [[1,0],
             [-1,0],
             [0,1],
             [0,-1]]

seen = [[False for _ in range(W)] for _ in range(H)]
answer = [[-10000 for _ in range(W)] for _ in range(H)]
answer[0][0] = 0

todo = deque([[0,0]])
seen[0][0] = True
while len(todo) > 0:
    checking = todo.pop()
    for direction in directions:
        moved = [checking[0] + direction[0], checking[1] + direction[1]]
        if moved[0] < 0 or moved[0] >= H or moved[1] < 0 or moved[1] >= W:
            continue
        if seen[moved[0]][moved[1]] == False and s[moved[0]][moved[1]] ==".":
            seen[moved[0]][moved[1]] = True
            answer[moved[0]][moved[1]] = answer[checking[0]][checking[1]] + 1
            todo.append([moved[0], moved[1]])

if answer[-1][-1] == -10000:
    print("-1")
else:
    print(root_num - (answer[-1][-1] + 1))

Submission status: Wrong Answer

Solution code:

from collections import deque

H, W = map(int, input().split())
s = [list(input().rstrip('\n')) for _ in range(H)]

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

directions = [[1,0],
             [-1,0],
             [0,1],
             [0,-1]]

seen = [[False for _ in range(W)] for _ in range(H)]
answer = [[-10000 for _ in range(W)] for _ in range(H)]
answer[0][0] = 0

todo = deque([[0,0]])
seen[0][0] = True
while len(todo) > 0:
    checking = todo.pop()
    for direction in directions:
        moved = [checking[0] + direction[0], checking[1] + direction[1]]
        if moved[0] < 0 or moved[0] >= H or moved[1] < 0 or moved[1] >= W:
            continue
        if seen[moved[0]][moved[1]] == False and s[moved[0]][moved[1]] ==".":
            seen[moved[0]][moved[1]] = True
            answer[moved[0]][moved[1]] = answer[checking[0]][checking[1]] + 1
            todo.append([moved[0], moved[1]])


if root_num == answer[-1][-1]+1 or answer[-1][-1] == -10000:
    print("-1")
else:
    print(root_num - (answer[-1][-1] + 1))

Submission status: Wrong Answer

Solution code:

from collections import deque
H, W = map(int, input().split())
s = [list(input().rstrip('\n')) for _ in range(H)]

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

directions = [[1,0],
             [-1,0],
             [0,1],
             [0,-1]]

seen = [[False for _ in range(W)] for _ in range(H)]
answer = [[-10000 for _ in range(W)] for _ in range(H)]
answer[0][0] = 0

todo = deque([[0,0]])
seen[0][0] = True
while len(todo) > 0:
    checking = todo.pop()
    for direction in directions:
        moved = [checking[0] + direction[0], checking[1] + direction[1]]
        if moved[0] < 0 or moved[0] >= H or moved[1] < 0 or moved[1] >= W:
            continue
        if seen[moved[0]][moved[1]] == False and s[moved[0]][moved[1]] ==".":
            seen[moved[0]][moved[1]] = True
            answer[moved[0]][moved[1]] = answer[checking[0]][checking[1]] + 1
            todo.append([moved[0], moved[1]])

all_count = 0
for i in range(H):
    for j in range(W):
        if answer[i][j] != -10000:
            all_count+=1

if all_count == answer[-1][-1]+1 or answer[-1][-1] == -10000:
    print(-1)
else:
    print(root_num - (answer[-1][-1] + 1))

Submission status: Wrong Answer

Solution code:

from collections import deque

H, W = map(int, input().split())
s = [list(input().rstrip('\n')) for _ in range(H)]

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

directions = [[1,0],
             [-1,0],
             [0,1],
             [0,-1]]

seen = [[False for _ in range(W)] for _ in range(H)]
answer = [[0 for _ in range(W)] for _ in range(H)]

todo = deque([[0,0]])
seen[0][0] = True
while len(todo) > 0:
    checking = todo.pop()
    for direction in directions:
        moved = [checking[0] + direction[0], checking[1] + direction[1]]
        if moved[0] < 0 or moved[0] >= H or moved[1] < 0 or moved[1] >= W:
            continue
        if seen[moved[0]][moved[1]] == False and s[moved[0]][moved[1]] ==".":
            seen[moved[0]][moved[1]] = True
            answer[moved[0]][moved[1]] = answer[checking[0]][checking[1]] + 1
            todo.append([moved[0], moved[1]])
if answer[-1][-1] > 0:
    print(root_num - (answer[-1][-1] + 1))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:

from collections import deque

H, W = map(int, input().split())
s = [list(input().rstrip('\n')) for _ in range(H)]

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

directions = [[1,0],
             [-1,0],
             [0,1],
             [0,-1]]

seen = [[False for _ in range(W)] for _ in range(H)]
answer = [[0 for _ in range(W)] for _ in range(H)]

todo = deque([[0,0]])
seen[0][0] = True
while len(todo) > 0:
    checking = todo.pop()
    for direction in directions:
        moved = [checking[0] + direction[0], checking[1] + direction[1]]
        if moved[0] < 0 or moved[0] >= H or moved[1] < 0 or moved[1] >= W:
            continue
        if seen[moved[0]][moved[1]] == False and s[moved[0]][moved[1]] ==".":
            seen[moved[0]][moved[1]] = True
            answer[moved[0]][moved[1]] = answer[checking[0]][checking[1]] + 1
            todo.append([moved[0], moved[1]])

print(root_num - (answer[-1][-1] + 1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, maze, dist, sh, sw):
    queue = deque([[sh, sw]])
    dist[sh][sw] = 0
    while queue:
        h, w = queue.popleft()
        for i, j in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
            next_h, next_w = h + i, w + j
            if not ((0 <= next_h <= H - 1) and (0 <= next_w <= W - 1)):
                continue
            if (maze[next_h][next_w] == ".") and (dist[next_h][next_w] == -1):
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append([next_h, next_w])
    return dist

def main():
    H, W = map(int, input().split())
    s = [""] * H
    for i in range(H):
        s[i] = input().rstrip()

    dist = [[-1] * W for _ in range(H)]
    bfs(H, W, s, dist, 0, 0)
    min_n_white_of_path = dist[H-1][W-1] + 1
    n_white = 0
    for i in range(H):
        n_white += s[i].count(".")
    ans = n_white - min_n_white_of_path
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
black = 0
s = ["#" * (W+2)]
for _ in range(H):
    row = input()
    black += row.count("#")
    s.append("#" + row + "#")
s.append("#" * (W+2))

def bfs(x, y):
    if s[x][y] == "#":
        return 0
    queue = deque([(x, y)])
    dist = [[-1]*(W+2) for _ in range(H+2)]
    dist[x][y] = 0
    while queue:
        r, c = queue.popleft()
        d = dist[r][c]
        for i in [r-1, r+1]:
            if i >= 0 and i <= H:
                if s[i][c] == "." and dist[i][c] == -1:
                    dist[i][c] = d+1
                    queue.append((i, c))
        for j in [c-1, c+1]:
            if j >= 0 and j <= W:
                if s[r][j] == "." and dist[r][j] == -1:
                    dist[r][j] = d+1
                    queue.append((r, j))
    return dist

print(H*W-bfs(1,1)[-2][-2]-1-black)

Submission status: Wrong Answer

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

cnt = 0
for row in c:
    for chara in row:
        if chara == '#':
            cnt += 1
res = H*W - cnt

def check(ny, nx):
    if 0<=ny<=H-1 and 0<=nx<=W-1 and c[ny][nx]=='.':
        return True
    else:
        return False

deq = deque()
deq.append([(0, 0)]) # insert indices
ddy = [-1, 0, 1, 0]
ddx = [0, -1, 0, 1]
step = 0
found = False
while deq[0]:
    nqueue = []
    cqueue = deq.popleft()
    for val in cqueue:
        y, x = val
        if val==(H-1, W-1):
            found = True
            break
        for dy, dx in zip(ddy, ddx):
            ny, nx = y+dy, x+dx
            if check(ny, nx):
                c[ny][nx] = '#'
                nqueue.append((ny, nx))
    if found: break
    deq.append(nqueue)
    step += 1

res -= (step+1)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
field = ["#"*(W+2)]
field += ["#"+input()+"#" for _ in range(H)]
field += ["#"*(W+2)]
d = [[-1]*(W+2) for _ in range(H+2)]
q = deque()
q.append([1,1])
d[1][1] = 1
dmov = [(-1,0),(1,0),(0,-1),(0,1)]
cnt = 0
for i in range(W+2):
  for j in range(H+2):
    if field[j][i] == ".":
      cnt += 1

while len(q) > 0:
  node = q.popleft()
  x = node[0]
  y = node[1]
  c = d[y][x]
  for i,j in dmov:
    xx = x+i
    yy = y+j
    if d[yy][xx] == -1 and field[yy][xx] == ".":
      d[yy][xx] = c+1
      q.append([xx,yy])
      
print(cnt-d[H][W])

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split((" ")))
mp = []
for _ in range(H):
    mp.append(input())

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

que = collections.deque()
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 1
que.append((0, 0))

while que:
    h, w = que.popleft()
    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
            continue
        elif dist[h + dh][w + dw] != -1:
            continue
        dist[h + dh][w + dw] = dist[h][w] + 1
        que.append((h + dh, w + dw))

if dist[H - 1][W - 1] == -1:
    print(-1)
else:
    print(max(white - (dist[H - 1][W - 1]), 0))

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split((" ")))
mp = []
for _ in range(H):
    mp.append(input())

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

que = collections.deque()
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 1
que.append((0, 0))

while que:
    h, w = que.popleft()
    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
            continue
        elif dist[h + dh][w + dw] != -1:
            continue
        dist[h + dh][w + dw] = dist[h][w] + 1
        que.append((h + dh, w + dw))

if dist[H - 1][W - 1] == -1:
    print(-1)
else:
    print(min(white - (dist[H - 1][W - 1]), 0))

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split((" ")))
mp = []
for _ in range(H):
    mp.append(input())

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

que = collections.deque()
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 1
que.append((0, 0))

while que:
    h, w = que.popleft()
    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
            continue
        elif dist[h + dh][w + dw] != -1:
            continue
        dist[h + dh][w + dw] = dist[h][w] + 1
        que.append((h + dh, w + dw))

if dist[H - 1][W - 1] == -1:
    print(-1)
else:
    print(white - (dist[H - 1][W - 1]))

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split((" ")))
mp = []
for _ in range(H):
    mp.append(input())

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

que = collections.deque()
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
que.append((0, 0))

while que:
    h, w = que.popleft()
    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
            continue
        elif dist[h + dh][w + dw] != -1:
            continue
        dist[h + dh][w + dw] = dist[h][w] + 1
        que.append((h + dh, w + dw))

if dist[H - 1][W - 1] == -1:
    print(-1)
else:
    print(white - (dist[H - 1][W - 1] + 1))