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:
INF = 1e10

H, W = list(map(int, input().split()))
c = []
cnt = 0
for y in range(H):
    c.append(input())
    for s in c[-1]:
        if s=='.':
            cnt+=1
    
def search(syx, gyx):
    sy,sx = syx
    gy,gx = gyx
    visited = [[INF]*W for _ in range(H)]
    q = [[sy,sx]]
    visited[sy][sx]=0
    while len(q)>0:
        tmp_q = []
        for one in q:
            cy,cx = one
            for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ny, nx = cy+dy, cx+dx
                if 0 <= nx < W and 0 <= ny < H and c[ny][nx] == '.' and visited[ny][nx]> visited[cy][cx]+1:
                    visited[ny][nx] = visited[cy][cx]+1
                    tmp_q.append([ny,nx])
        q = tmp_q
        if visited[gy][gx]!=INF:
            break
    return visited[gy][gx]

print(cnt-search([0,0],[H-1,W-1])-1)

Submission status: Wrong Answer

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    from collections import deque
    dist = [[-1]*W for i in range(H)]

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    bfs(0, 0)
    ans = -(dist[H-1][W-1]+1)
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                ans -= 1
    ans += H*W
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from _collections import deque


def bfs(field, field_info, starting_y, starting_x, goal_y, goal_x):
    queue = deque([[starting_y, starting_x]])
    field_info[starting_y][starting_x] = 1

    while queue:
        y, x = queue.popleft()
        if [y, x] == [goal_y, goal_x]:
            return field_info[y][x]
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + dy, x + dx
            if 0 <= new_y <= goal_y and 0 <= new_x <= goal_x and field[new_y][new_x] == "." and field_info[new_y][new_x] == -1:
                field_info[new_y][new_x] = field_info[y][x] + 1
                queue.append([new_y, new_x])


def solve():
    number_of_rows, number_of_columns = list(map(int, input().split()))  # Row, Column数
    field = [input() for _ in range(number_of_rows)]
    field_info = [[-1] * number_of_columns for _ in range(number_of_rows)]
    starting_y, starting_x = 0, 0
    goal_y, goal_x = number_of_rows - 1, number_of_columns - 1
    bfs(field, field_info, starting_y, starting_x, goal_y, goal_x)

    # # BFSの結果をチェック
    # for field_info_line in field_info:
    #     print(field_info_line)

    if field_info[goal_y][goal_x] == -1:
        print(-1)
        return
    else:   # 到達できる場合
        number_of_black_cell = 0
        for row_i in range(number_of_rows):
            for column_i in range(number_of_columns):
                if field[row_i][column_i] == "#":
                    number_of_black_cell += 1
        point = number_of_columns * number_of_rows - field_info[goal_y][goal_x] - number_of_black_cell
        print(point)

Submission status: Wrong Answer

Solution code:
from collections import deque


H,W = map(int, input().split())
S = [""] * H
b = 0

for i in range(H):
    s = input()
    b += s.count("#")
    S[i] = s

cost = [[10**6 for _ in range(W)] for _ in range(H)]
cost[0][0] = 1




q = deque()
q.append((0,0))
while q:
    y,x = q.popleft()

    if 0 <= x - 1 <= W - 1 and cost[y][x-1] > cost[y][x] + 1:
        cost[y][x-1] = cost[y][x] + 1
        q.append((y, x-1))
    if 0 <= x + 1 <= W - 1 and cost[y][x+1] > cost[y][x] + 1:
        cost[y][x+1] = cost[y][x] + 1
        q.append((y, x+1))

    if 0 <= y - 1 <= H - 1 and cost[y-1][x] > cost[y][x] + 1:
        cost[y-1][x] = cost[y][x] + 1
        q.append((y-1, x))

    if 0 <= y + 1 <= H - 1 and cost[y+1][x] > cost[y][x] + 1:
        cost[y+1][x] = cost[y][x] + 1
        q.append((y+1, x))

if cost[H-1][W-1] == 0:
    print(-1)
else:
    print(H*W - b - cost[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque


H,W = map(int, input().split())
S = [""] * H
b = 0

for i in range(H):
    s = input()
    b += s.count("#")
    S[i] = s

cost = [[0 for _ in range(W)] for _ in range(H)]
cost[0][0] = 1

q = deque()
q.append((0,0))
while q:
    y,x = q.popleft()

    if 0 <= x - 1 <= W - 1 and cost[y][x-1] == 0:
        cost[y][x-1] = cost[y][x] + 1
        q.append((y, x-1))
    if 0 <= x + 1 <= W - 1 and cost[y][x+1] == 0:
        cost[y][x+1] = cost[y][x] + 1
        q.append((y, x+1))

    if 0 <= y - 1 <= H - 1 and cost[y-1][x] == 0:
        cost[y-1][x] = cost[y][x] + 1
        q.append((y-1, x))

    if 0 <= y + 1 <= H - 1 and cost[y+1][x] == 0:
        cost[y+1][x] = cost[y][x] + 1
        q.append((y+1, x))

if cost[H-1][W-1] == 0:
    print(-1)
else:
    print(H*W - b - cost[H-1][W-1])

Submission status: Wrong Answer

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

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

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

from collections import deque
que = deque([])
# スタート地点を追加する
que.append((0, 0))
d[0][0] = 0

while que:
    x, y = que.popleft()
    if x == h-1 and y == w-1:
        break
    for i in range(4):
        dx, dy = directions[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and field[nx][ny] =='.' and d[nx][ny] == -1:
            que.append((nx, ny))
            d[nx][ny] = d[x][y] + 1   
            
white = sum(field, []).count('.')
print(white - (d[h-1][w-1] + 1))

Submission status: Wrong Answer

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

def calcDist(startIdx, area):
     que = [startIdx]
     dist = [[-1 for i in range(W)] for i in range(H)]
     dist[startIdx[0]][startIdx[1]] = 0
     
     while len(que) != 0:
         idx = que.pop(0)
         
         if idx[0]-1 >= 0 and area[idx[0]-1][idx[1]] != '#' and dist[idx[0]-1][idx[1]] == -1:
             que.append([idx[0]-1, idx[1]])
             dist[idx[0]-1][idx[1]] = dist[idx[0]][idx[1]] + 1
         
         if idx[0]+1 < H and area[idx[0]+1][idx[1]] != '#' and dist[idx[0]+1][idx[1]] == -1:
             que.append([idx[0]+1, idx[1]])
             dist[idx[0]+1][idx[1]] = dist[idx[0]][idx[1]] + 1
             
         if idx[1]-1 >= 0 and area[idx[0]][idx[1]-1] != '#' and dist[idx[0]][idx[1]-1] == -1:
             que.append([idx[0], idx[1]-1])
             dist[idx[0]][idx[1]-1] = dist[idx[0]][idx[1]] + 1
             
         if idx[1]+1 < W and area[idx[0]][idx[1]+1] != '#' and dist[idx[0]][idx[1]+1] == -1:
             que.append([idx[0], idx[1]+1])
             dist[idx[0]][idx[1]+1] = dist[idx[0]][idx[1]] + 1
     
     return dist
     
def searchWhiteNum(area):
    ans = 0
    for i in range(H):
        for j in range(W):
            if area[i][j] == '.':
                ans += 1
    
    return ans

dist = calcDist([0,0], area)
neededWhiteNum = dist[H-1][W-1] + 1
ans = searchWhiteNum(area)
print(ans - neededWhiteNum)

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

dots = sum(row.count('.') for row in S)
print(dots - dist[-1][-1] - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(h, w, S):
    cands = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque(maxlen = h * w)
    q.append((1, 1, 1))
    s = {(1, 1)}
    min_len = -1
    while len(q) > 0:
        x, y, d = q.popleft()
        for dx, dy in cands:
            if x + dx == w and y + dy == h:
                min_len = d + 1
                q.clear()
            if (x + dx, y + dy) not in s \
                and 1 <= x + dx <= w \
                and 1 <= y + dy <= h \
                and S[y + dy - 1][x + dx - 1] == '.':
                q.append((x + dx, y + dy, d + 1))
                s.add((x + dx, y + dy))
    return (sum(l == '.' for s in S for l in s) - min_len) if min_len >= 0 else -1

_h, _w = map(int, input().split())
_S = [input() for _ in range(_h)]
print(solve(_h, _w, _S))

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(h, w, S):
    cands = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque(maxlen = h * w)
    q.append((1, 1, 1))
    s = {(1, 1)}
    min_len = -1
    while len(q) > 0:
        x, y, d = q.popleft()
        for dx, dy in cands:
            if x + dx == w and y + dy == h:
                min_len = d + 1
                q.clear()
            if (x + dx, y + dy) not in s \
                and 1 <= x + dx <= w \
                and 1 <= y + dy <= h \
                and S[y + dy - 1][x + dx - 1] == '.':
                q.append((x + dx, y + dy, d + 1))
                s.add((x + dx, y + dy))
    return sum(l == '.' for s in S for l in s) - min_len

_h, _w = map(int, input().split())
_S = [input() for _ in range(_h)]
print(solve(_h, _w, _S))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

dy = [0,1,0,-1]
dx = [1,0,-1,0]
def bfs():
    que = deque([])
    que.append((0,0))
    visited[0][0]=0

    while que:
        p = que.popleft()

        if p[0]==h-1 and p[1]==w-1:
            break

        for i in range(4):
            ny = p[0]+dy[i]
            nx = p[1]+dx[i]

            if 0<=ny<h and 0 <=nx<w and maze[ny][nx]=='.' and visited[ny][nx]==0:
                visited[ny][nx]=visited[p[0]][p[1]]+1
                que.append((ny,nx))

    return visited[h-1][w-1]

ans = bfs()
if ans == 0:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j]=='#':
                cnt +=1

    print(h*w-cnt-ans+1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
    cnt += s[i].count("#")
ans = (H-1)*(W-1) - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# 単純にスタートとゴールが固定（1,1) (h,w)のBFSで
# 最短経路を求めたら、h*w - cnt - 最初の黒マスの数　を返す
# inputで黒マスを数える
h,w = map(int,input().split())
board = [["#"]*(w+2) for _ in range(h+2)]
num_black = 0
for i in range(h):
    s = input()
    for j in range(w):
        board[i+1][j+1] = str(s[j])
        if s[j] == "#":
            num_black += 1
path = 0 # 最短経路のパス数
from collections import deque
mv = ((1,0),(-1,0),(0,1),(0,-1))
visit = deque()
start_pos = (1,1)
visit.append(start_pos)
cnt = [[-1]*(w+2) for _ in range(h+2)] # -1埋め
cnt[1][1] = 0 #スタート地点は0
while visit:
    point = visit.popleft()
    #print(point[0], point[1])
    for k in mv:
        pos = (point[0]+k[0],point[1]+k[1])
        #print(pos)
        if board[pos[0]][pos[1]] == ".":
            if cnt[pos[0]][pos[1]] == -1: #unvisited
                #print(i,j,"yes")
                cnt[pos[0]][pos[1]] = cnt[point[0]][point[1]] + 1
                visit.append((pos[0],pos[1]))
                if pos[0] == h and pos[1] == w:
                    path = cnt[pos[0]][pos[1]]
                    break
if path == 0: print(0)
else: print(h*w - path - num_black -1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# 単純にスタートとゴールが固定（1,1) (h,w)のBFSで
# 最短経路を求めたら、h*w - cnt - 最初の黒マスの数　を返す
# inputで黒マスを数える
h,w = map(int,input().split())
board = [["#"]*(w+2) for _ in range(h+2)]
num_black = 0
for i in range(h):
    s = input()
    for j in range(w):
        board[i+1][j+1] = str(s[j])
        if s[j] == "#":
            num_black += 1
path = 0 # 最短経路のパス数
from collections import deque
mv = ((1,0),(-1,0),(0,1),(0,-1))
visit = deque()
start_pos = (1,1)
visit.append(start_pos)
cnt = [[-1]*(w+2) for _ in range(h+2)] # -1埋め
cnt[1][1] = 0 #スタート地点は0
while visit:
    point = visit.popleft()
    #print(point[0], point[1])
    for k in mv:
        pos = (point[0]+k[0],point[1]+k[1])
        #print(pos)
        if board[pos[0]][pos[1]] == ".":
            if cnt[pos[0]][pos[1]] == -1: #unvisited
                #print(i,j,"yes")
                cnt[pos[0]][pos[1]] = cnt[point[0]][point[1]] + 1
                visit.append((pos[0],pos[1]))
                if pos[0] == h and pos[1] == w:
                    path = cnt[pos[0]][pos[1]]
                    break
print(h*w - path - num_black -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
w = 0
for i in range(H):
    w += maze[i].count(".")
inf = 10**9
d = np.array([[inf]*W for _ in range(H)])
d[0][0] = 0
q = deque([])
q.append([0, 0])
nx, ny = [0, 0]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while len(q) > 0:
    p = q.pop()
    if p[0] == H and p[1] == W:
        break
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H and d[ny][nx] == inf and maze[ny][nx]==".":
            q.append([nx, ny])
            d[ny][nx] = d[p[1]][p[0]] + 1
if d[H-1][W-1] == inf:
	print(-1)
else:
	print(w-(d[H-1][W-1]+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
w = 0
for i in range(H):
    w += maze[i].count(".")
inf = 10**9
d = np.array([[inf]*W for _ in range(H)])
d[0][0] = 0
q = deque([])
q.append([0, 0])
nx, ny = [0, 0]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while len(q) > 0:
    p = q.pop()
    if p[0] == H and p[1] == W:
        break
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H and d[ny][nx] == inf and maze[ny][nx]==".":
            q.append([nx, ny])
            d[ny][nx] = d[p[1]][p[0]] + 1
print(w-(d[H-1][W-1]+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
black = 0
v = [""] * h
for i in range(h):
    v[i] = input()
    for c in v[i]:
        black += c == '#'

d = [[(10 ** 18)]*w for j in range(h)]
d[0][0] = 0

q = deque()
q.append((0, 0))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while len(q):
    y, x = q.popleft()
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if not (0 <= ny and ny < h and 0 <= nx and nx < w):
            continue
        if v[ny][nx] == '#':
            continue
        if d[ny][nx] < (10 ** 18):
            continue
        d[ny][nx] = d[y][x] + 1
        q.append((ny, nx))

print(h*w-black-d[h-1][w-1]-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

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

si, sj = 0, 0
gi, gj = H-1, W-1

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


di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

dis = [[INF]*W for _ in range(H)]
dis[si][sj] = 0

dq = deque([])
dq.append([si,sj])

while dq:
    p = dq.popleft()
    if p[0] == gi and p[1] == gj:
        break
    for i in range(4):
        ni = p[0] + di[i]
        nj = p[1] + dj[i]
        if 0 <= ni < H and 0 <= nj < W and field[ni][nj] != '#' and dis[ni][nj] == INF:
            dq.append([ni,nj])
            dis[ni][nj] = dis[p[0]][p[1]]+1

path_length = dis[gi][gj]
shiro = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            shiro += 1
ans = shiro - path_length - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

def bfs(si, sj, ei, ej):
    q = collections.deque()
    q.append([si, sj, 0])
    used = set()
    used.add((si, sj))
    while len(q) > 0:
        prvi, prvj, cost = q.popleft()
        for i, j in [[prvi + 1, prvj], [prvi - 1, prvj], [prvi, prvj + 1], [prvi, prvj - 1]]:
            if i < 0 or j < 0 or W <= i or H <= j or (i, j) in used:
                continue
            elif grids[j][i] == '#':
                continue
            else:
                if [i, j] == [ei, ej]:
                    return cost + 1
                else:
                    q.append([i, j, cost + 1])
                    used.add((i, j))
    return -1


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

res = bfs(0, 0, W - 1, H - 2)
if res != -1:
    black_num = sum([row.count('#') for row in grids])
    print( H * W - black_num - 2 - res)
else:
    print(res)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

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

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

for i in range(H):
    for j in range(W-1):
        if s[i][j] == s[i][j+1] == ".":
            graph[j+(W*i)][j+(W*i)+1] = 1
            graph[j+(W*i)+1][j+(W*i)] = 1

for i in range(H-1):        
    for j in range(W):
        if s[i][j] == s[i+1][j] == ".":
            graph[j+(W*i)][j+(W*(i+1))] = 1
            graph[j+(W*(i+1))][j+(W*i)] = 1
            
d = dijkstra(graph)

cnt = 0
for i in s:
    for j in range(W):
        if i[j] == ".":
            cnt += 1
      
if d[0][H*W-1] == float("inf"):
    print(-1)
else:
    print(cnt-d[0][H*W-1]-1)

Submission status: Wrong Answer

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

def bfs():
  dist = [[f_inf] * W for _ in range(H)]
  D = ((1,0), (0,1), (-1,0), (0,-1))
  
  que = deque([])
  que.append((0,0))
  dist[0][0] = 0
  
  while que:
    p = que.popleft()
    for d in D:
      nx = p[0] + d[0]
      ny = p[1] + d[1]
      print(nx, ny)
      if H > nx >= 0 and W > ny >= 0 and C[nx][ny] != '#' and dist[nx][ny] == f_inf:
        que.append((nx,ny))
        dist[nx][ny] = dist[p[0]][p[1]]+1
  return dist[H-1][W-1]



cnt = 0
for c in C:
  cnt += c.count('.')
  
ans = bfs()
if ans == f_inf:
  print(-1)
else:
  print(cnt - 1 - ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
numdot = sum([line.count('.') for line in m])

q = deque([[0, 0, 1]])
m[0][0] = '#'
while q:
    i, j, score = q.popleft()
    if i == H-1 and j == W-1:
        break

    for movei, movej in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        ni = i + movei; nj = j + movej
        if ni < 0 or H <= ni or nj < 0 or W <= nj or m[ni][nj] == '#':
            continue
        m[ni][nj] = '#'
        q.append([ni, nj, score+1])

print(numdot - score)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() for _ in range(H)]
white = sum(s.count(".") for s in S)
visited = [[-1] * W for _ in range(H)]
deq = deque([(0,0)])
visited[0][0] = 1
dia = [1, 0, -1, 0, 1]
while deq:
    i, j = deq.popleft()
    if i == H - 1 and j == W - 1:
        break
    d = visited[i][j]
    for x, y in zip(dia, dia[1:]):
        ii, jj = i + x, j + y
        if 0 <= ii < H and 0 <= jj < W and visited[ii][jj] < 0:
            visited[ii][jj] = d + 1
            deq.append((ii, jj))
white -= visited[H-1][W-1]
print(white if white > 0 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() for _ in range(H)]
white = sum(s.count(".") for s in S)
visited = [[-1] * W for _ in range(H)]
deq = deque([(0,0)])
visited[0][0] = 1
dia = [1, 0, -1, 0, 1]
while deq:
    i, j = deq.popleft()
    if i == H - 1 and j == W - 1:
        break
    d = visited[i][j]
    for x, y in zip(dia, dia[1:]):
        ii, jj = i + x, j + y
        if 0 <= ii < H and 0 <= jj < W and visited[ii][jj] < 0:
            visited[ii][jj] = d + 1
            deq.append((ii, jj))
print(white - visited[H-1][W-1] if visited[H-1][W-1] > 0 else -1)

Submission status: Wrong Answer

Solution code:
H,W=[int(x) for x in input().split()]
import heapq
A=[]
temp=0
for i in range(H):
	s=input()
	A.append(s)
	for j in range(W):
		if s[j]==".":
			temp+=1


B=[[100000000 for i in range(W)] for j in range(H)]

#print(A)

queue=[]
heapq.heapify(queue)
heapq.heappush(queue,[1,0,0])
#print(queue)
ans=100000000000000000000
B[0][0]=1
while queue:
	#print(queue)
	count,x,y=heapq.heappop(queue)
	#print(count,x,y)
	if x==H-1 and y==W-1:
		ans=min(ans,count)
	else:
		if (x+1<=H-1 and A[x+1][y]==".") and B[x+1][y]>count+1:
			heapq.heappush(queue,[count+1,x+1,y])
			B[x+1][y]=count+1
		if (0<=x-1 and A[x-1][y]==".") and B[x-1][y]>count+1:
			heapq.heappush(queue,[count+1,x-1,y])
			B[x-1][y]=count+1
		if (y+1<=W-1 and A[x][y+1]==".") and B[x][y+1]>count+1:
			heapq.heappush(queue,[count+1,x,y+1])
			B[x][y+1]=count+1
		if (0<=y-1 and A[x][y-1]==".") and B[x][y-1]>count+1:
			heapq.heappush(queue,[count+1,x,y-1])
			B[x][y-1]=count+1

print(temp-ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
m = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]

cnt = 0
for hi in range(1,h+1):
    for wi in range(1,w+1):
        if m[hi][wi]==".":
            cnt += 1

d = [[10**9]*(w+2) for _ in range(h+2)]
q = deque([(1,1,1)])
while len(q):
    ch,cw,r = q.popleft()
    d[ch][cw] = r

    for hi,wi in [[ch+1,cw],[ch,cw+1],[ch-1,cw],[ch,cw-1]]:
        if m[hi][wi]=="." and d[hi][wi]>r+1:
            q.append((hi,wi,r+1))

print(cnt-d[h][w])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
MAP=[input() for i in range(h)]
black=sum([[j[i] for i in range(w)].count("#") for j in MAP])
ans=h*w-(h+w-1)-black
if ans < 0 or MAP[0][0]=="#":
  print(-1)
now=[0,0]
branch=[]
while now != [h-1,w-1]:
  c=0
  if now[0]==h-1 and MAP[now[0]][now[1]+1]=="#" and branch==[]:
    #一番下まで来てて右に行けず，選択肢もない
    print(-1)
    exit()
  elif now[0]==h-1 and MAP[now[0]][now[1]+1]=="#" and branch!=[]:
    #一番下まで来てて右に行けないが，選択肢はある
    now=branch[-1]
    del branch[-1]
    c=1
  elif now[0]==h-1 and MAP[now[0]][now[1]+1]=="." and c==0:
    #一番下まで来てて右に行ける
    now[1]+=1
    c=1
  elif now[1]==w-1 and MAP[now[0]+1][now[1]]=="#" and branch==[] and c==0:
    #一番右に来てて下に行けず選択肢もない
    print(-1)
    exit()
  elif now[1]==w-1 and MAP[now[0]+1][now[1]]=="#" and branch!=[] and c==0:
    #一番右に来てて下に行けないが，選択肢はある
    now=branch[-1]
    del branch[-1]
    c=1
  elif now[1]==w-1 and MAP[now[0]+1][now[1]]=="." and c==0:
    #一番右に来てて下に行ける
    now[0]+=1
    c=1
  elif MAP[now[0]+1][now[1]]=="#" and MAP[now[0]][now[1]+1]=="." and c==0:
    now[1]+=1
    c=1
  elif MAP[now[0]+1][now[1]]=="." and MAP[now[0]][now[1]+1]=="#" and c==0:
    now[0]+=1
    c=1
  elif MAP[now[0]+1][now[1]]=="." and MAP[now[0]][now[1]+1]=="." and c==0:
    branch.append(now)
    now[1]+=1
    c=1
  elif MAP[now[0]+1][now[1]]=="#" and MAP[now[0]][now[1]+1]=="#" and c==0:
    if len(branch)==0:
      print(-1)
      exit()
    else:
      now = branch[-1]
      now[0]+=1
      del branch[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
meiro=['#'+input()+'#' for i in range(h)]
h+=2
w+=2
top=list('#'*w)
bot=list('#'*w)
meiro.insert(0,top)
meiro.append(bot)

def bfs(a,b):
    dist=[[-1]*w for i in range(h)]
    dist[b][a]=0
    q=deque([(a,b)])
    ans=-1
    flag=0
    while q:
        x,y=q.popleft()
        kyori=dist[y][x]
        dx=[0,1,0,-1]
        dy=[1,0,-1,0]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx==w-2 and ny==h-2:
                return kyori +1
            if dist[ny][nx]==-1 and meiro[ny][nx]=='.':
                dist[ny][nx]=kyori+1
                ans=max(ans,kyori+1)
                q.append((nx,ny))
    return -1
saitan = bfs(1,1)
if saitan=='-1':
    print(-1)
else:
    cnt=0
    for i in range(h):
        cnt+=str(meiro[i]).count('.')
    ans=cnt-saitan-1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
meiro=['#'+input()+'#' for i in range(h)]
h+=2
w+=2
top=list('#'*w)
bot=list('#'*w)
meiro.insert(0,top)
meiro.append(bot)

def bfs(a,b):
    dist=[[-1]*w for i in range(h)]
    dist[b][a]=0
    q=deque([(a,b)])
    ans=-1
    flag=0
    while q:
        x,y=q.popleft()
        kyori=dist[y][x]
        dx=[0,1,0,-1]
        dy=[1,0,-1,0]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx==w-2 and ny==h-2:
                return kyori +1
            if dist[ny][nx]==-1 and meiro[ny][nx]=='.':
                dist[ny][nx]=kyori+1
                ans=max(ans,kyori+1)
                q.append((nx,ny))
    return -1
saitan = bfs(1,1)
cnt=0
for i in range(h):
    cnt+=str(meiro[i]).count('.')
ans=cnt-saitan-1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

H,W=[int(x) for x in input().split()]
A=[]
temp=0
for i in range(H):
  s=input()
  A.append(s)
  for j in range(W):
    if s[j]==".":
      temp+=1
#print(H,W)

visited=[[10000000000000000 for j in range(W)] for i in range(H)]
visited[0][0]=1
pointer=0
ans=10000000000000000000
def bfs(i,j,count):
  global ans
  global pointer
  #print(i,j,count)
  if j+1<=W-1:
    if A[i][j+1]=="." and visited[i][j+1]>count+1:
      visited[i][j+1]=count+1
      bfs(i,j+1,count+1)
  if 0<=j-1:
    if A[i][j-1]=="." and visited[i][j-1]>count+1:
      visited[i][j-1]=count+1
      bfs(i,j-1,count+1)
  if i+1<=H-1:
    #print(i+1,H-1,100000)
    if A[i+1][j]=="." and visited[i+1][j]>count+1:
      visited[i+1][j]=count+1
      bfs(i+1,j,count+1)
  if 0<=i-1:
    if A[i-1][j]=="." and visited[i-1][j]>count+1:
      visited[i-1][j]=1
      bfs(i-1,j,count+1)
  if i==H-1 and j==W-1:
    #print(ans)
    pointer=1
bfs(0,0,1)
#print(A)
#print(visited)
if (pointer==0):
  print("-1")
else:
  print(temp-visited[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

H,W=[int(x) for x in input().split()]
A=[]
temp=0
for i in range(H):
  s=input()
  A.append(s)
  for j in range(W):
    if s[j]==".":
      temp+=1
#print(H,W)

visited=[[10000000000000000 for j in range(W)] for i in range(H)]
visited[0][0]=1
pointer=0
ans=10000000000000000000
def bfs(i,j,count):
  global ans
  global pointer
  #print(i,j,count)
  if j+1<=W-1:
    if A[i][j+1]=="." and visited[i][j+1]>count+1:
      visited[i][j+1]=count+1
      bfs(i,j+1,count+1)
  if 0<=j-1:
    if A[i][j-1]=="." and visited[i][j-1]>count+1:
      visited[i][j-1]=count+1
      bfs(i,j-1,count+1)
  if i+1<=H-1:
    #print(i+1,H-1,100000)
    if A[i+1][j]=="." and visited[i+1][j]>count+1:
      visited[i+1][j]=count+1
      bfs(i+1,j,count+1)
  if 0<=i-1:
    if A[i-1][j]=="." and visited[i-1][j]>count+1:
      visited[i-1][j]=1
      bfs(i-1,j,count+1)
  if i==H-1 and j==W-1:
    #print(ans)
    pointer=1
bfs(0,0,1)
#print(A)
print(visited)
if (pointer==0):
  print("-1")
else:
  print(temp-visited[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

H,W=[int(x) for x in input().split()]
A=[]
temp=0
for i in range(H):
  s=input()
  A.append(s)
  for j in range(W):
    if s[j]==".":
      temp+=1
#print(H,W)

visited=[[10000000000000000 for j in range(W)] for i in range(H)]
visited[0][0]=1
pointer=0
ans=10000000000000000000
def bfs(i,j,count):
  global ans
  global pointer
  #print(i,j,count)
  if j+1<=W-1:
    if A[i][j+1]=="." and visited[i][j+1]>count+1:
      visited[i][j+1]=count+1
      bfs(i,j+1,count+1)
  if 0<=j-1:
    if A[i][j-1]=="." and visited[i][j-1]>count+1:
      visited[i][j-1]=count+1
      bfs(i,j-1,count+1)
  if i+1<=H-1:
    #print(i+1,H-1,100000)
    if A[i+1][j]=="." and visited[(i+1)][j]>count+1:
      visited[(i+1)][j]=count+1
      bfs(i+1,j,count+1)
  if 0<=i-1:
    if A[i-1][j]=="." and visited[(i-1)][j]>count+1:
      visited[(i-1)][j]=1
      bfs(i-1,j,count+1)
  if i==H-1 and j==W-1:
    ans=min(ans,count)
    #print(ans)
    pointer=1
bfs(0,0,1)
#print(A)
#print(visited)
if (pointer==0):
  print("-1")
else:
  print(temp-ans)