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:
h, w = map(int, input().split())
cell = []
for _ in range(h):
    cell.append(input())

dist = [[float('inf') for _ in range(w)] for _ in range(h)]
dist[0][0] = 0
next_move = [[0, 0]]
x = [1, 0, -1, 0]
y = [0, 1, 0, -1]

while len(next_move):
    if next_move[0] == [h-1, w-1]:
        break
    
    for i in range(4):
        nx = next_move[0][1] + x[i]
        ny = next_move[0][0] + y[i]
        if (nx >= 0 and nx < w and ny >= 0 and ny < h and 
            cell[ny][nx] != '#' and dist[ny][nx] == float('inf')):
            dist[ny][nx] = dist[next_move[0][0]][next_move[0][1]] + 1
            next_move.append([ny, nx])
    next_move.pop(0)

cnt = 0
for i in range(h):
    for t in range(w):
        
        if cell[i][t] == '#':
            cnt += 1
            
if dist[h-1][w-1] == float('inf'):
    print(-1)
else:
    print((h*w) - (dist[h-1][w-1] + 1) - cnt)

Submission status: Accepted

Solution code:
class Queue:
    class Node:
        def __init__(self, item):
            self.item=item
            self.next=None
    def __init__(self):
        self.head=None
        self.tail=None
    def enqueue(self, item):
        node=Queue.Node(item)
        if self.head:
            assert self.tail is not None
            self.tail.next=node
            self.tail=node
        else:
            assert self.tail is None
            self.head=node
            self.tail=node
    def dequeue(self):
        assert self.head is not None
        node=self.head
        if self.head==self.tail:
            self.head=None
            self.tail=None
        else:
            self.head=node.next
        return node.item
    def empty(self):
        if self.head: return False
        else: return True

h, w=[int(word) for word in input().split()]
map=[["#" for hi in range(h+2)] for wi in range(w+2)]
visited=[[False for hi in range(h+2)] for wi in range(w+2)]
num_white=0
for hi in range(1, h+1):
    l=input()
    for wi in range(1, w+1):
        map[wi][hi]=l[wi-1]
        if l[wi-1]==".": num_white+=1
queue=Queue()
queue.enqueue((1, 1, 0))
length=None
while not queue.empty():
    wi, hi, l=queue.dequeue()
    if wi==w and hi==h:
        length=l
        break
    if visited[wi][hi]: continue
    if map[wi][hi]==".":
        visited[wi][hi]=True
        queue.enqueue((wi-1, hi, l+1))
        queue.enqueue((wi+1, hi, l+1))
        queue.enqueue((wi, hi-1, l+1))
        queue.enqueue((wi, hi+1, l+1))
if length is not None:
    print(num_white-length-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
maze=['#'*(w+2)]
white=0
for i in range(h):
    r=input()
    maze.append('#'+r+'#')
    white+=r.count('.')
maze.append('#'*(w+2))
dxy=((1,0),(-1,0),(0,1),(0,-1))
dist=[[-1] *(w+2) for i in range(h+2)]
def bfs():
    queue=[]
    queue.insert(0,(1,1))
    dist[1][1]=0
    while len(queue):
        x,y=queue.pop()
        if x==w and y==h:
            break
        for (dx,dy) in dxy:
            nx, ny= x+dx, y+dy
            if maze[ny][nx]=='.' and dist[ny][nx]==-1:
                queue.insert(0,(nx,ny))
                dist[ny][nx]=dist[y][x]+1
    return dist

bfs()
if dist[h][w]==-1:
    print(-1)
else:
    print(white-dist[h][w]-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
counter = 0
space = [[-1 for i in range(w+2)]]
for i in range(1,h+1):
    r = input()
    s = list("#"+r+"#")
    counter += r.count("#")
    space.append([])
    for j,moji in enumerate(s):
        if moji == ".":
            space[i].append(0)
        elif moji =="#":
            space[i].append(-1)
space.append([-1 for i in range(w+2)])

sx,sy = 1,1
ex,ey = h,w

watch_space = [[sx,sy]]
decided_space = [[sx,sy]]
flag = 0
while(True):
    tmp = list()
    for [i,j] in watch_space:
        if [i-1,j] not in decided_space and space[i-1][j] == 0:
            space[i-1][j] = space[i][j]+ 1
            decided_space.append([i-1,j])
            tmp.append([i-1,j])
        if [i+1,j] not in decided_space and space[i+1][j] == 0:
            space[i+1][j] = space[i][j]+ 1
            decided_space.append([i+1,j])
            tmp.append([i+1,j])
        if [i,j+1] not in decided_space and space[i][j+1] == 0:
            space[i][j+1] = space[i][j]+ 1
            decided_space.append([i,j+1])
            tmp.append([i,j+1])
        if [i,j-1] not in decided_space and space[i][j-1] == 0:
            space[i][j-1] = space[i][j]+ 1
            decided_space.append([i,j-1])
            tmp.append([i,j-1])
    watch_space = tmp
    if [ex,ey] in decided_space:
        break
    elif len(watch_space) < 1:
        flag = -1
        break
if flag == 0:
    ans = (w*h)-(space[ex][ey]+1) - counter
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
h, w = [int(x) for x in input().split()]
maze = []
whitesum = 0
for i in range(h):
  m = input()
  whitesum += m.count('.') 
  maze.append(m)
dist = [[-1]*w for i in range(h)]
dxy = ((1,0),(-1,0),(0,1),(0,-1))

def bfs():
  queue = []
  queue.insert(0,(1,1))
  dist[0][0] = 0
  while(len(queue)):
    x, y = queue.pop()
    if x == w and y == h:
      break
    for (dx, dy) in dxy:
      nx, ny = x+dx, y+dy
      
      if(nx>0 and nx<=w and ny>0 and ny<=h and maze[ny-1][nx-1] == '.' and dist[ny-1][nx-1] == -1):
        queue.insert(0, (nx, ny))
        dist[ny-1][nx-1] = dist[y-1][x-1] + 1
        
bfs()
if dist[h-1][w-1] == -1:
  print(-1)
else:
  print(whitesum-dist[h-1][w-1]-1)

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
s = [list(input()) for i in range(H)]
num_of_point = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            num_of_point += 1
 
counter = 0
position = [[0,0]]
while True:
    counter += 1
    new_position =[]
    for i,j in position:
        for i_,j_ in [[-1,0],[1,0],[0,1],[0,-1]]:
            i_new = i+i_
            j_new = j+j_
            if i_new >=0 and i_new <= H-1 and j_new >= 0 and j_new <= W-1:
                if s[i_new][j_new] == '.':
                    new_position.append([i_new,j_new])
                    s[i_new][j_new] = counter
    if [H-1,W-1] in new_position:
        print(num_of_point-counter-1)
        break
    if counter >= H*W:
      	print(-1)
      	break
    position = new_position

Submission status: Accepted

Solution code:
tmp = list(map(int,input().split()))
h, w = tmp[0],tmp[1]
maze = []
for i in range(h):
    maze.append([i for i in input()])
maze[0][0] = 0
i = 0
def change(data,p,q,i):
    if data[p][q] == ".":
        data[p][q] = i+1

def makechange(data,j,k,i):
    if j != h-1:
        change(data,j+1,k,i)
    if k != w-1:
        change(data,j,k+1,i)
    if j != 0:
        change(data,j-1,k,i)
    if k != 0:
        change(data,j,k-1,i)

while(True):
    ifhenka = False
    newmaze = [i for i in maze]
    for j in range(h):
        for k in range(w):
            if maze[j][k] == i:
                makechange(maze,j,k,i)
    if maze[h-1][w-1] != ".":
        break
    if i == 2500:
        print(-1)
        quit()
    i += 1

ans = 0
for i in maze:
    ans += i.count("#")
print(h*w - ans - maze[h-1][w-1] - 1)

Submission status: Accepted

Solution code:
from collections import deque

h,w=[int(i) for i in input().split() ]

graph=[[None for i in range(w+2)] for j in range(h+2)]
wnum=0
for i in range(w+2):
    graph[0][i]=['#',None]
    graph[h+1][i]=['#',None]
for j in range(h+2):
    graph[j][0]=['#',None]
    graph[j][w+1]=['#',None]
for i in range(h):
    a=input()
    for j in range(w):
        if a[j]=='.':
            wnum+=1
        graph[i+1][j+1]=[a[j],None]

q=deque([])
q.append((1,1))
graph[1][1][1]=0
d_min=None
while len(q)!=0:
    x,y=q.popleft()
    for cx,cy in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):
        if graph[cx][cy][0]=='.':
            if graph[cx][cy][1]==None:
                graph[cx][cy][1]=graph[x][y][1]+1
                if (cx,cy)==(h,w):
                    d_min=graph[cx][cy][1]
                    break
                q.append((cx,cy))
if d_min!=None:
   print(wnum-d_min-1)
else:
   print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def solve():
    H, W = map(int, input().split())

    num_white = 0
    field = []
    for _ in range(H):
        field.append(list(input()))
        num_white += field[-1].count(".")

    memo = [[INF] * W for _ in range(H)]
    memo[0][0] = 1

    que = deque()
    que.append((0, 0))
    while que:
        y, x = que.popleft()
        c = memo[y][x]

        for i in range(len(dy4)):
            ny, nx = y + dy4[i], x + dx4[i]

            if inside(ny, nx, H, W) and memo[ny][nx] > c + 1 and field[ny][nx] == '.':
                memo[ny][nx] = c + 1
                que.append((ny, nx))

    if memo[-1][-1] == INF:
        return -1
    else:
        return num_white - memo[H - 1][W - 1]


def main():
    print(solve())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
grid = [[0 for j in range(0,w)] for i in range(0,h)]
black = 0
for i in range(0,h):
    c = list(input())
    grid[i] = c
for j in range(0,h):
    for i in range(0,w):
        if grid[j][i] == "#":
            black += 1
#幅探索
point = [[0 for j in range(0,w)] for i in range(0,h)]
q = [(0,0)]
def haba(y,x):
    nextPoint = [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]
    for ny,nx in nextPoint:
        if ny >= 0 and ny < h and nx >= 0 and nx < w:
            if grid[ny][nx] == "." and point[ny][nx] == 0:
                point[ny][nx] = point[y][x] + 1
                q.append((ny,nx))
while len(q)>0:
    (y,x) = q.pop(0)
    haba(y,x)
if point[h-1][w-1] == 0:
    print("-1")
else:
    print((h*w) - point[h-1][w-1] - 1 - black)

Submission status: Accepted

Solution code:
h, w =map(int, input().split())

a=['#'*(w+2)]
for i in range(h):
    b='#'+input()+'#'
    a.append(b)
a.append('#'*(w+2))
#print(a)

from collections import Counter

n=[(1,1)]
route={(1,1):0}
p=[[1,0],[0,1],[-1,0],[0,-1]]
count=1
while route.get((h,w),0)==0 and count != 10000:
    n2=[]
    #print(n,route)
    for i in n:
        for j in p:
            np=(i[0]+j[0],i[1]+j[1])
            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                n2.append(np)
                if route.get(np,1000)>count:
                    route[np]=count
    n=n2
    #print(n,route)
    count+=1

    
a2=[]
for i in a:
    for j in range(len(i)):
        a2.append(i[j])
con=Counter(a2)


if count==10000:
    print('-1')
else:
    print(con['.']-route[(h,w)]-1)

Submission status: Accepted

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

import heapq

f = []
count = 0
for _ in range(H):
    line = list(input())
    f.append(line)
    count += sum([1 if x == '.' else 0 for x in line])

v = [[2501 for i in range(W)] for j in range(H)]
v[0][0] = 0

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

heap = [(0,0,0)]
while len(heap) > 0:
    w, x, y = heapq.heappop(heap)
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if (nx >= 0 and nx < W and ny >= 0 and ny < H):
            if nx == W-1 and ny == H-1:
                print(count - w -2)
                exit()
            elif f[ny][nx] == '#':
                pass
            else:
                if v[ny][nx] > w+1:
                    v[ny][nx] = w+1
                    heapq.heappush(heap, (w+1, nx, ny))

print(-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
walls = 0
S = [0] * H
for i in range(H):
    L = input()
    walls += L.count('#')
    S[i] = '#' + L + '#'
S = ['#' * (W+2)] + S + ['#' * (W+2)]
V = [[0] * (W+2) for _ in range(H+2)]

q = [(1, 1, 1)]
while q:
    x, y, c = q.pop(0)

    if (x, y) == (H, W):
        # 最短経路と元々の壁以外を数える
        print(H * W - walls - c)
        break

    for m, n in {(0, 1), (0, -1), (1, 0), (-1, 0)}:
        i, j = x+m, y+n
        if S[i][j] == '#' or V[i][j]:
            continue
        q.append((i, j, c+1))
        V[i][j] = 1

else:
    print(-1)

Submission status: Accepted

Solution code:
#これはBFSの練習である。なので記述を丁寧に行う

from collections import deque

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

#今後座標を記述する際に(y,x)の順であることに気を付ける

dy,dx=[1,0,-1,0],[0,1,0,-1]
#すべての地点をスタート位置からの距離infとして初期化する
d=[[float("inf") for i in range(w)] for j in range(h)] 
d[0][0]=0 #スタート位置はスタート位置からの距離0
queue=deque([]) 
queue.append([0,0]) #まず初めに、スタート地点をqueueに入れる

#ここから
while len(queue): #queueが空になるまで操作を行う
    p=queue.popleft() #queueの先頭を取り出す
    if p==[h-1,w-1]: break #取り出したものがゴールなら、探索終了
    for i in range(4): #調べているマスの上下左右4方向の状態を調べる
        ny=p[0]+dy[i]
        nx=p[1]+dx[i]
        #そのマスが移動可能、かつ訪れたことがあるかを判定する
        if (0<=ny<h and 0<=nx<w and s[ny][nx]=="." and d[ny][nx]==float("inf")):
            queue.append([ny,nx]) #訪れたことがないならqueueに追加
            d[ny][nx]=d[p[0]][p[1]]+1 #訪れたことがないなら移動前の地点の距離+1で確定
#ここまでがBFS(この問題の主要部)

if d[h-1][w-1]==float("inf"): #ゴールにたどり着けないのならば
    print(-1)
else: #たどり着けたのならば
    tot=0
    for i in range(h): # "#"がいくつあるか数える
        for j in range(w):
            if s[i][j]=="#": tot+=1
    print(h*w-((d[h-1][w-1]+1)+tot))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

field = []
visited = {(1, 1)}

white_count = 0

field.append("#" * (w+2))


for i in range(h):
    row = input()
    field.append("#"+row+"#")
    white_count += row.count(".")

field.append("#" * (w+2))


def is_movable(x, y):
    state = (x, y)

    # 通った道であればFalseを返す
    if state in visited:
        return False

    if field[y][x] == "#":
        return False
    else:
        return True


def breadth_search(field):
    # x, y, count
    queue = [(1, 1, 1)]

    while queue:
        x, y, count = queue.pop(0)

        if(x == w and y == h):
            return count

        if(is_movable(x+1, y)):
            visited.add((x+1, y))
            queue.append((x+1, y, count+1))

        if(is_movable(x, y+1)):
            visited.add((x, y+1))
            queue.append((x, y+1, count+1))

        if(is_movable(x-1, y)):
            visited.add((x-1, y))
            queue.append((x-1, y, count+1))

        if(is_movable(x, y-1)):
            visited.add((x, y-1))
            queue.append((x, y-1, count+1))

    return 0


count = breadth_search(field)

if count == 0:
    print(-1)
else:
    print(white_count-count)

Submission status: Accepted

Solution code:
from collections import deque
import sys
INF = 500000000000
sys.setrecursionlimit(2147483647)

def bfs(posit):
    y,x = posit
    n = [(y - 1, x), (y  + 1, x), (y, x - 1), (y, x + 1)]
    for ny, nx in n:
        if 0 <= ny < H and 0 <= nx < W and s[ny][nx] != "#":
            temp = dist[ny][nx]
            dist[ny][nx] = min(temp, dist[y][x] + 1)
            if temp != dist[ny][nx]:
                route.append((ny, nx))
            if (ny, nx) == (H - 1, W - 1):
                return
    if len(route) > 0:
        bfs(route.popleft())

H,W = [int(i) for i in input().split()]
s = []
route = deque()
black = 0
for i in range(H):
    po = list(input())
    black += po.count("#")
    s.append(po)
dist = [[INF for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
bfs((0, 0))
if 0 < dist[H - 1][W - 1] < INF:
    print(H * W - black - dist[H - 1][W - 1] - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

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

board = [0 for i in range(H)]
for i in range(H):
    board[i] = list(input())
INF = 100000
dis = [[INF for i in range(H)] for j in range(W)]
queue = []
queue.insert(0, (0, 0))
dis[0][0] = 0
while len(queue):
    x, y = queue.pop()

    if x == W - 1 and y == H - 1:
        count = 0
        for i in range(W):
            for j in range(H):
                if board[j][i] == "#":
                    count += 1
        print(H*W - count - dis[W-1][H-1] -1)
        sys.exit()
        break

    for i in range(0, 4):
        nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
        if 0 <= nx < W and 0 <= ny < H and board[ny][nx] != "#":
            if dis[nx][ny] == INF:
                queue.insert(0, (nx, ny))
                dis[nx][ny] = dis[x][y] + 1

print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w = (int(i) for i in input().split())

M = [input() for i in range(h)]
N = [[False]*w for i in range(h)]

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


que = deque([[0,0,1]])
while que:
    x,y,c = que.popleft()

    if M[y][x] == "#":
        continue
    elif N[y][x]:
        continue
    elif x == w-1 and y == h-1:
        
        print(h*w-(c+cnt))
        quit()

    else:
        N[y][x]=True
        A = [[x+1,y,c+1],[x-1,y,c+1],[x,y+1,c+1],[x,y-1,c+1]]
        for a in A:
            if 0<=a[0]<=w-1 and 0<=a[1]<=h-1:
                que.append(a)
                
print(-1)

Submission status: Accepted

Solution code:
#abc088d

H,W=map(int,raw_input().split())
maze=[]
for i in xrange(H):
 maze.append(list(raw_input()))
d=[[-1 for i in xrange(W+1)] for j in xrange(H+1)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
 q=[]
 q.insert(0,(0,0))
 d[sx][sy]=0
 while len(q):
  x,y=q.pop()
  if x==gx and y==gy:
   break
  for i in xrange(4):
   nx,ny=x+dx[i],y+dy[i]
   if 0<=nx<H and 0<=ny<W and maze[nx][ny]!='#' and d[nx][ny]==-1:
    q.insert(0,(nx,ny))
    d[nx][ny]=d[x][y]+1
 return d[gx][gy]
sx,sy=0,0
gx,gy=H-1,W-1

def cntsharp():
 cnt=0
 for i in xrange(H):
  cnt+=maze[i].count('#')
 return cnt
if bfs()==-1:
 print -1
else:
 print H*W-(bfs()+cntsharp())-1

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
table = []
for _ in range(H):
    table.append(input())
w = sum(v.count(".") for v in table)    
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
import queue
qu = queue.Queue()
qu.put((0,0))
while not qu.empty():
    x,y = qu.get()
    for dx,dy in ((1,0), (0,1), (-1,0), (0,-1)):
        nx,ny = dx + x , dy + y
        if nx >= 0 and nx < H and ny >= 0 and ny < W:            
            if table[nx][ny] == "." and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                qu.put((nx,ny))
if dist[-1][-1] == -1:
    print(-1)
else :
    print(w - (dist[-1][-1] + 1))

Submission status: Accepted

Solution code:
import copy
h,w = (int(i) for i in input().split())
x = [input() for i in range(h)]
cf,list1,num = [[0,0]],[[0,0]],1
while [h-1,w-1] not in cf and len(list1) != 0:
	list2 = []
	for j in list1:
		list3 = [[j[0]+1,j[1]],[j[0]-1,j[1]],[j[0],j[1]+1],[j[0],j[1]-1]]
		for j2 in list3:
			if (-1<j2[0]<h) and (-1<j2[1]<w) and (j2 not in cf) and (x[j2[0]][j2[1]]=="."):
				cf.append(j2)
				list2.append(j2)
	num += 1
	list1 = copy.deepcopy(list2)
num2 = 0
for k in x: num2 += k.count(".")
if [h-1,w-1] not in cf: answer = -1
else: answer = num2-num
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import queue
h,w=map(int,input().split())
m=[]
block=0
for i in range(h):
    m.append(list(input()))
    block+=m[-1].count('#')
q=queue.Queue()
q.put((0,0))
m[0][0]=0
while not q.empty():
    i,j=q.get()
    if i+1<h and m[i+1][j]=='.':
        m[i+1][j]=m[i][j]+1
        q.put((i+1,j))
    if i-1>=0 and m[i-1][j]=='.':
        m[i-1][j]=m[i][j]+1
        q.put((i-1,j))
    if j+1<w and m[i][j+1]=='.':
        m[i][j+1]=m[i][j]+1
        q.put((i,j+1))
    if j-1>=0 and m[i][j-1]=='.':
        m[i][j-1]=m[i][j]+1
        q.put((i,j-1))
if m[h-1][w-1]=='.':
    print(-1)
else:
    print(h*w-m[h-1][w-1]-block-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
List = [input() for i in range(H)]
queue = [(0, 0, 1)]
cout = sum([row.count("#") for row in List])
used = [(0, 0)]


def check(x, y, c):
    if x > W - 1 or y > H - 1 or x < 0 or y < 0:
        return
    if List[y][x] == '#':
        return
    if (x, y) in used:
        return
    queue.append((x, y, c))
    used.append((x, y))

f = -1
final =  0
while queue:
    x, y, c = queue.pop(0)
    if x == W - 1 and y == H - 1:
        f = 1
        final = c
        break
    check(x + 1, y, c + 1)
    check(x, y + 1, c + 1)
    check(x - 1, y, c + 1)
    check(x, y - 1, c + 1)

print(f if f == -1 else(H * W - final - cout))

Submission status: Accepted

Solution code:
import sys
import heapq as hp

def eval(x, y, c):
    return c + (w - 1 - x + h - 1- y)

h, w = [int(x) for x in input().rstrip().split()]
matrix = [list(input().rstrip()) for _ in range(h)]
open = [[False for _ in range(w)] for _ in range(h)]

x, y, cost = 0, 0, 0
open[y][x] = True
queue = []
hp.heappush(queue, (eval(x, y, 1), x, y, 1))
while [x, y] != [w-2, h-1] and [x, y] != [w-1, h-2]:
    e, x, y, c = hp.heappop(queue)
    for dx, dy in [[1,0], [-1,0], [0,1], [0,-1]]:
        if 0 <= x+dx <= w-1 and 0 <= y+dy <= h-1 and matrix[y+dy][x+dx] == "." and not open[y+dy][x+dx]:
            hp.heappush(queue, (eval(x+dx, y+dy, c+1), x+dx, y+dy, c+1))
            open[y+dy][x+dx] = True
    cost = c+1
    
    if not queue:
        print(-1)
        sys.exit()
print(sum(list(map(lambda x: x.count("."), matrix))) - cost)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, raw_input().split())
maze = [raw_input() for _ in xrange(h)]
visited = [[False] * w for _ in xrange(h)]
que = deque([(0, 0, 0)])  # prepare for bfs.
dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
dis = flag = False
while que:
    x, y, d = que.popleft()
    if (x, y) == (h - 1, w - 1):
        dis, flag = d, True
        break
    for i in xrange(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < h and 0 <= ny < w:
            if not visited[nx][ny] and maze[nx][ny] == '.':
                que.append((nx, ny, d + 1))
                visited[nx][ny] = True
print h * w - dis - 1 - sum([_.count('#') for _ in maze]) if flag else -1

Submission status: Accepted

Solution code:
tmp=input().split()
H,W=int(tmp[0]),int(tmp[1])
map = [['a' for x in range(W)] for y in range(H)]
countroad = 0
for i in range(H):
    tmp = input()
    for j in range(W):
        map[i][j] = tmp[j]
        if tmp[j] =='.':
            countroad += 1
count = 0
queue = [0]
check = [0]
dx,dy=0,0

def walkmap(pos1,pos2):
    if 0<=pos1 and pos1<H and 0<=pos2 and pos2<W:
        if map[pos1][pos2] == '.':
            mapIndex=pos1*W+pos2
            if mapIndex not in check:
                queue.append(mapIndex)
                check.append(mapIndex)
minstep = -1
while len(queue) > 0:
    count += 1
    #judge Goal
    if (H*W-1) in queue:
        minstep = count
        break
    target = len(queue)
    for j in range(target):
        #next walk
        dx = int(queue[0]/W)
        dy = int(queue[0]%W)
        queue.pop(0)
        walkmap(dx-1,dy)
        walkmap(dx+1,dy)
        walkmap(dx,dy-1)
        walkmap(dx,dy+1)
if minstep > 0:
    print(countroad-minstep)
else:
    print(minstep)

Submission status: Accepted

Solution code:
from queue import Queue

H, W = [int(x) for x in input().split()]
realH = H + 2
realW = W + 2
s = ["#" + input() + "#" for x in range(H)]
wall = "#" * (realW)
s.insert(0, wall)
s.append(wall)
dxy = [0, 1, 0, -1, 0]
inf = float("inf")

visited = [[False] * realW for x in range(realH)]
depth = [[inf] * realW for x in range(realH)]
depth[1][1] = 1
q = Queue()
q.put((1,1))

while not q.empty():
    place = q.get()
    if place == (H, W):
        break
    for i in range(4):
        nxt = (place[0] + dxy[i], place[1] + dxy[i+1])
        if s[nxt[0]][nxt[1]] == "." and not visited[nxt[0]][nxt[1]]:
            q.put(nxt)
            depth[nxt[0]][nxt[1]] = depth[place[0]][place[1]] + 1
            visited[nxt[0]][nxt[1]] = True

if depth[H][W] == inf:
    print(-1)
else:
    print(realH * realW - sum(map(lambda x: x.count("#"), s)) - depth[H][W])

Submission status: Accepted

Solution code:
from collections import deque

INF = 10101010

def main():
    h,w = map(int,input().split())
    s = []
    for i in range(h):
        s.append(input())

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

    d = [[INF for j in range(w)] for i in range(h)]
    d[0][0] = 0
    que = deque()
    que.append((0,0))
    while que:
        y,x = que.pop()
        if (y,x) == (h-1,w-1):
            return ans - (d[h-1][w-1]+1)

        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny = x+dx, y+dy
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] != '#' and d[ny][nx]>d[y][x]+1:
                    d[ny][nx] = d[y][x]+1
                    que.appendleft((ny,nx))

    return -1

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import deque

INF = 10101010

def main():
    h,w = map(int,input().split())
    s = []
    for i in range(h):
        s.append(input())

    d = [[INF for j in range(w)] for i in range(h)]
    d[0][0] = 0
    que = deque()
    que.append((0,0))
    while len(que):
        y,x = que.pop()
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny = x+dx, y+dy
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] != '#' and d[ny][nx]>d[y][x]+1:
                    d[ny][nx] = d[y][x]+1
                    que.append((ny,nx))

    if d[h-1][w-1] == INF:
        return -1

    ans = -(d[h-1][w-1]+1)
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                ans += 1
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import deque

INF = 10101010

def main():
    h,w = map(int,input().split())
    s = []
    for i in range(h):
        s.append(input())



    d = [[INF for j in range(w)] for i in range(h)]
    d[0][0] = 0
    que = deque()
    que.append((0,0))
    while len(que):
        y,x = que.pop()
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny = x+dx, y+dy
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] != '#' and d[ny][nx]>d[y][x]+1:
                    d[ny][nx] = d[y][x]+1
                    que.append((ny,nx))

    if d[h-1][w-1] == INF:
        return -1

    ans = -(d[h-1][w-1]+1)
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                ans += 1
    return ans

if __name__ == '__main__':
    print(main())