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

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = []
maze.append('#' * (w+2))
for i in range(h):
    maze.append('#' + input() + '#')
cnt = 0
for i in maze:
    cnt += i.count('.')
maze.append('#' * (w+2))
i, j = 1, 1
seen = {(1, 1)}
d = 0
stack = deque([[(i, j), d]])
while stack:
    pos, d = stack.popleft()
    i, j = pos
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if (i+di, j+dj) not in seen and maze[i + di][j + dj] == '.':
            if (i + di, j + dj) == (h, w):
                print(cnt - d -2)
                exit()
            stack.append([(i + di, j + dj), d + 1])
            seen.add((i + di, j + dj))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
INF = 10000

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

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

vx = [-1,1,0,0]
vy = [0,0,1,-1]

def bfs():
    while(q):
        x,y = q.popleft()
        for i in range(4):
            nx = x + vx[i]
            ny = y + vy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] == '.' and dist[nx][ny] == INF:
                q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1
                if (nx, ny) == (gx, gy): return

q = deque()
q.append((0,0))
gx = H-1
gy = W-1
dist[0][0] = 1
bfs()
if dist[gx][gy] == INF: print(-1)
else:
    tmp = 0
    for h in range(H):
        tmp += S[h].count('#')
    print(H*W - dist[gx][gy] - tmp)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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]
    
    if goal == -1:
        print(-1)
    else:
        print(cnt - goal - 1)

Submission status: Accepted

Solution code:
from collections import deque
 
h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("#")
    ma.append(kar)
 
 
ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]
 
while q:
    x , y = q.popleft()
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1 and ans[nx][ny] == -1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
        if nx == h-1 and ny == w-1:
            break
 
if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])

Submission status: Accepted

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 if D!=inf else -1)

Submission status: Accepted

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

if minD == -1:
    print(-1)
else:
    print(count-minD)

Submission status: Accepted

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 != 0:
    print(whole - result - defoB)
else:
    print(-1)

Submission status: Accepted

Solution code:
# solution
import io
from queue import Queue

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

white=sum([1 if s[y][x]=='.' else 0 for x in range(mike) for y in range(nim)])
used=[[False for x in range(mike)] for y in range(nim)]
q=Queue()
q.put((0,0,1))
while True:
    if q.empty():
        print(-1)
        break
    x,y,l=q.get()
    if used[y][x]:
        continue
    if x==mike-1 and y==nim-1:
        print(white-l)
        break
    used[y][x]=True
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx=x+d[0]
        ny=y+d[1]
        if ny>=0 and ny<nim and nx>=0 and nx<mike:
            if s[ny][nx]=='.':
                q.put((nx,ny,l+1))

Submission status: Accepted

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

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)

    if todo == []:
        finishflag = False

    i += 1

print("-1")

Submission status: Accepted

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 k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            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)
path = visit[gx][gy] + 1
if visit[gx][gy] == -1:
    print(-1)
else:
    print(h * w - path - cnt)

Submission status: Accepted

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.popleft()
    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: Accepted

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
    if min_n_white_of_path == 0:
        print(-1)
    else:
        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: Accepted

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
ans = bfs(1,1)[-2][-2]
if ans != -1:
    print(H*W-bfs(1,1)[-2][-2]-1-black)
else:
    print(-1)

Submission status: Accepted

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

if not(found):
    print(-1)
    exit()
res -= (step+1)
print(res)

Submission status: Accepted

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])
      
if d[H][W] == -1:
  print(-1)
else:
  print(cnt-d[H][W])

Submission status: Accepted

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 mp[h + dh][w + dw] == '#' or 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: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

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

def bfs():
    d = [[float("inf")] * w for i in range(h)]

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

    que = deque([])
    que.append((0, 0))
    d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break
        for i in range(4):
            n_row = p[0] + dx[i]
            n_col = p[1] + dy[i]

            if 0 <= n_row < h and 0 <= n_col < w and s[n_row][n_col] != "#" and d[n_row][n_col] == float("inf"):
                que.append((n_row, n_col))
                d[n_row][n_col] = d[p[0]][p[1]] + 1

    return d[h-1][w-1]

if bfs() == float("inf"):
    print(-1)
else:
    print(w_cnt-bfs()-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

def main():
    H, W = map(int, input().split())
    
    field = "#" * (W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#" * (W+2)

    move = [-1, 1, -(W+2), W+2]
    cost = [0] * (H+2) * (W+2)

    def bfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft
        cost[s] = 1
        enqueue(s)

        while q:
            now = dequeue()
            for dx in move:
                nv = now + dx
                if field[nv] != "#" and cost[nv] <= 0:
                    cost[nv] = cost[now] + 1
                    enqueue(nv)
        
    start = (W+2) + 1
    goal = H*(W+2) + W

    bfs(start)
    white = field.count(".")
    if cost[goal]:
        print(white - cost[goal])
    else:
        print(-1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
S=[input() for i in range(H)]
black=0
for i in range(H):
    black+=S[i].count("#")

C=[[0 for _ in range(W)] for j in range(H)]
F=[[False for _ in range(W)] for j in range(H)]

def bfs():
    q=deque([[0,0]])
    F[0][0]=True
    d=[[0,1],[1,0],[-1,0],[0,-1]]
    while q:
        y,x=q.popleft()
        for a,b in d:
            ny=y+a
            nx=x+b
            if 0<=ny<H and 0<=nx<W:
                if S[ny][nx]=="." and F[ny][nx]!=True:
                    q.append([ny,nx])
                    C[ny][nx]=C[y][x]+1
                    F[ny][nx]=True
bfs()
if F[H-1][W-1]==False:
    print(-1)
    exit()

ans=H*W-C[H-1][W-1]-1-black
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s_tmp = [input() for i in range(H)]
s = [[0] * W for i in range(H)]
b = 0
for i in range(H):
    for j in range(W):
        if s_tmp[i][j] == '#':
            s[i][j] = -1
            b += 1
c = [(0, 0)]
i = 0
while (H - 1, W - 1) not in c:
    c_tmp = []
    i += 1
    for h, w in c:
        if h > 0 and s[h - 1][w] == 0:
            s[h - 1][w] = i
            c_tmp.append((h - 1, w))
        if h < H - 1 and s[h + 1][w] == 0:
            s[h + 1][w] = i
            c_tmp.append((h + 1, w))
        if w > 0 and s[h][w - 1] == 0:
            s[h][w - 1] = i
            c_tmp.append((h, w - 1))
        if w < W - 1 and s[h][w + 1] == 0:
            s[h][w + 1] = i
            c_tmp.append((h, w + 1))
    if len(c_tmp) == 0:
        break
    c = c_tmp
if len(c_tmp) == 0:
    print(-1)
else:
    print(H * W - b - i - 1)

Submission status: Accepted

Solution code:
from queue import Queue
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,1,0,-1]
cnt = 0
INF = 10 ** 8
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
d = [[INF for i in range(W)] for j in range(H)]
q = Queue()
q.put([0,0])
d[0][0] = 1
flag = 1
while not q.empty():
    x, y = q.get()
    if x == H - 1 and y == W - 1:
        flag = 0
        break
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and MAP[nx][ny] == '.' and d[nx][ny] == INF:
            d[nx][ny] = d[x][y] + 1
            q.put([nx,ny])
if flag:
    print(-1)
else:
    ans = H * W - d[H-1][W-1] - cnt
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [[0 for i in range(W)]for j in range(H)]
ans = -1
for i in range(H):
    S = input()
    for j in range(W):
        maze[i][j] = S[j]
        if maze[i][j] == '.':
            ans += 1

q = deque()
q.append([0, 0])
maze[0][0] = 0
while len(q) != 0:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x + [0, 1, 0, -1][i], y + [1, 0, -1, 0][i]
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        elif maze[ny][nx] == '#':
            continue
        elif maze[ny][nx] == '.':
            maze[ny][nx] = maze[y][x] + 1
            q.append([nx, ny])
if maze[H-1][W-1] == '.':
    print(-1)
else:
    print(ans - maze[H-1][W-1])

Submission status: Accepted

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

mat=[]
mat.append([False]*(W+2))
for i in range(H):
  array=[False]+[x=="." for x in input()]+[False]
  mat.append(array)
mat.append([False]*(W+2))
#print(mat)

true_num=0
for i in range(1,H+1):
  for j in range(1,W+1):
    if mat[i][j]:
      true_num+=1

if not mat[1][1] or not mat[H][W]:
  print(-1)
  sys.exit(0)

visited_dic={}
dist=0
queue={(1,1)}
while(len(queue)>0):
  new_queue=set()
  
  for q in queue:
    visited_dic[q]=dist
    if q==(H,W):
      break
    
    x,y=q
    if mat[x-1][y] and not (x-1,y) in visited_dic:
      new_queue.add((x-1,y))
    if mat[x+1][y] and not (x+1,y) in visited_dic:
      new_queue.add((x+1,y))
    if mat[x][y-1] and not (x,y-1) in visited_dic:
      new_queue.add((x,y-1))
    if mat[x][y+1] and not (x,y+1) in visited_dic:
      new_queue.add((x,y+1))
      
  queue=new_queue
  dist+=1
  
if not (H,W) in visited_dic:
  print(-1)
else:
  #print(visited_dic)
  print(true_num-visited_dic[(H,W)]-1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

A = [[-1]*W for i in range(H)]  #(sy,sx)からの最短距離
A[0][0] = 0

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

while q:
    y,x = q.pop()
    for dy,dx in directions:
        if not (0<= y+dy < H and 0 <= x+dx < W):
            continue
        elif s[y+dy][x+dx] == '#':
            continue
        elif A[y+dy][x+dx] != -1:
            continue
        else:
            A[y+dy][x+dx] = A[y][x] + 1
            q.appendleft([y+dy,x+dx])
if A[H-1][W-1] == -1:
    print(-1)
    exit()

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

print(a-A[H-1][W-1]-1)

Submission status: Accepted

Solution code:
import heapq

H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
nodes = []
nodedict = {}
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            nid = len(nodes)
            nodedict[(i,j)] = nid
            nodes.append((i,j))

N = len(nodes)
INF = H*W
edges = [[False]*N for _ in range(N)]

def link(i1,j1,i2,j2):
    n1 = nodedict[(i1,j1)]
    n2 = nodedict[i2,j2]
    edges[n1][n2] = edges[n2][n1] = True

for i in range(H):
    for j in range(W):
        if maze[i][j] != '.': continue
        if i > 0 and maze[i-1][j]=='.': link(i,j,i-1,j)
        if i < H-1 and maze[i+1][j]=='.': link(i,j,i+1,j)
        if j > 0 and maze[i][j-1]=='.': link(i,j,i,j-1)
        if j < W-1 and maze[i][j+1]=='.': link(i,j,i,j+1)

dist = [INF] * len(nodes)

def solve():
    dist[0] = 0
    n0 = nodedict[(0, 0)]
    pq = [(0, n0)]
    determined = {n0}
    while pq:
        d, nid = heapq.heappop(pq)
        for i, linked in enumerate(edges[nid]):
            if linked and i not in determined:
                dist[i] = min(dist[i], d+1)
                determined.add(i)
                heapq.heappush(pq, (d+1, i))
    goal = nodedict[(H-1, W-1)]
    if dist[goal] == INF:
        return -1
    return len(nodes) - dist[goal] - 1

print(solve())

Submission status: Accepted

Solution code:
import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
dxdy = ((-1,0), (1,0), (0,-1), (0,1))
H, W = map(int,input().split())
maze = []
visited = [ [0]*W for _ in range(H)]
black = 0
for h in range(H):
    s = input()
    maze.append(s)
    for c in s:
        if c=='#':
            black += 1
q = queue.Queue()
q.put((0,0,0))
cost = -1
while(not q.empty()):
    y, x, d = q.get()
    if x == W-1 and y == H-1:
        cost = d
        break
    if visited[y][x] == 1:
        continue
    else:
        visited[y][x] = 1
        for dx, dy in  dxdy:
            if (0<= x+dx < W) and (0<= y+dy < H):                
                if visited[y+dy][x+dx] == 0 and maze[y+dy][x+dx]=='.':
                    q.put((y+dy,x+dx,d+1))
if cost==-1:
    print (-1)
else:
    print (H*W-cost-1-black)

Submission status: Accepted

Solution code:
import queue
h,w = map(int,input().split())
sij = [input() for i in range(h)]

if sij[0][0] == '#' or sij[h-1][w-1] == '#':
    print(-1)
    exit()

q = queue.Queue()

q.put([0,0])

vx = [0,1,0,-1]
vy = [1,0,-1,0]

check = [0]*(h*w)
check[0] = 1

while not q.empty():
    x,y = q.get()
    for i in range(4):
        nx = x+vx[i]
        ny = y+vy[i]
        if nx >= 0 and nx <= w-1 and ny >= 0 and ny <= h-1:
            if check[ny*w+nx] == 0 and sij[ny][nx] == '.':
                q.put([nx,ny])
                check[ny*w+nx] = check[y*w+x] + 1
                if ny == h-1 and nx == w-1:
                    check[ny*w+nx] = check[y*w+x] + 1
                    break
kuro = 0

for i in range(h):
    for j in range(w):
        if sij[i][j] == '#':
            kuro += 1
if check[-1] == 0:
    print(-1)
    exit()
print(h*w-kuro-check[-1])

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
C_Count = [[1 for _ in range(W)] for _ in range(H)]
num = 0
goal_flag = False

def bfs(x,y,S):
    que = deque()
    que.append((x,y))

    while que:
        x,y = que.popleft()
        if S[x][y] == "#":
            continue
        if x == (H - 1) and y == (W - 1):
            return C_Count[x][y]
        S[x][y] = "#"
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            sx = x + dx
            sy = y + dy
            if sx < 0 or sx >= H or sy < 0 or sy >= W:
                continue
            que.append((sx,sy))
            C_Count[sx][sy]=C_Count[x][y] + 1
    return -1

for i in S:
    num += i.count("#")

tmp = bfs(0,0,S)
if tmp == -1:
    print(tmp)
else:
    print(H * W - tmp - num)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
count=0
S=[['#']*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    S_comp=list(str(input()))
    for j in range(1,W+1):
        if S_comp[j-1]=='.':
            count+=1
        S[i][j]=S_comp[j-1]


def sur(v):  #v is tuple
    vx=v[0]
    vy=v[1]
    preE=[(vx-1,vy),(vx+1,vy),(vx,vy-1),(vx,vy+1)]
    E=[]
    for nv in preE:
        if 1<=nv[0]<=H and 1<=nv[1]<=W:
            if S[nv[0]][nv[1]]=='.':
                E.append(nv)
    return E

q=deque()
s=(1,1)
g=(H,W)
q.append(s)
dist=[[-1]*(W+1) for k in range(H+1)]
dist[s[0]][s[1]]=0

while q:
    now=q.popleft()
    for next in sur(now):
        if dist[next[0]][next[1]]!=-1:
            continue
        q.append(next)
        dist[next[0]][next[1]]=dist[now[0]][now[1]]+1
        if next==g:
            ans=dist[g[0]][g[1]]
            print(count-1-ans)
            break
    else:
        continue
    break
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
map_a = [[] for _ in range(h)]
for i in range(h):
    for c in input():
            map_a[i].append(0 if c == "#" else 1)
d = [(1,0),(0,1),(-1,0),(0,-1)]

area = 0
stack = deque()
stack.append((0,0))

while stack:
    x,y = stack.popleft()
    for u,v in d:
        m = x + u; n = y + v
        if 0<=m<h and 0<=n<w:
            if map_a[m][n]==1:
                map_a[m][n] = map_a[x][y]+1
                stack.append((m,n))
                area += 1
if map_a[-1][-1] == 1:
    print(-1);exit()

pound = 0
for i in range(h):
    for c in map_a[i]:
        if c == 1:
            pound += 1
print(area-map_a[-1][-1]+pound)