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:
def main():
    H, W = [int(x) for x in input().strip().split()]
    tables = []
    white_count = 0
    for i in range(H):
        rows = [str(x) for x in list(input().strip())]
        white_count += rows.count(".")
        tables.append(rows)

    next_cells = [(0, 0, 1)]
    while(next_cells):
        _next_cells = []
        for next_cell in next_cells:
            y, x, step = next_cell
            if y == H-1 and x == W-1: #Goal
                tables[y][x] = str(min(step+1, int(tables[y][x])))
                continue

            if y != 0: # up OK
                if tables[y-1][x] != "#": # move OK
                    if tables[y-1][x] != ".": # 既に通った
                        if step+1 < int(tables[y-1][x]):
                            tables[y-1][x] = str(step+1)
                            _next_cells.append((y-1, x, step+1))
                    else: # 初めて通る
                        tables[y-1][x] = str(step+1)
                        _next_cells.append((y-1, x, step+1))

            if y != H-1: # down OK
                if tables[y+1][x] != "#": # move OK
                    if tables[y+1][x] != ".": # 既に通った
                        if step+1 < int(tables[y+1][x]):
                            tables[y+1][x] = str(step+1)
                            _next_cells.append((y+1, x, step+1))
                    else: # 初めて通る
                        tables[y+1][x] = str(step+1)
                        _next_cells.append((y+1, x, step+1))

            if x != 0: # left OK
                if tables[y][x-1] != "#": # move OK
                    if tables[y][x-1] != ".": # 既に通った
                        if step+1 < int(tables[y][x-1]):
                            tables[y][x-1] = str(step+1)
                            _next_cells.append((y, x-1, step+1))
                    else: # 初めて通る
                        tables[y][x-1] = str(step+1)
                        _next_cells.append((y, x-1, step+1))

            if x != W-1: # right OK
                if tables[y][x+1] != "#": # move OK
                    if tables[y][x+1] != ".": # 既に通った
                        if step+1 < int(tables[y][x+1]):
                            tables[y][x+1] = str(step+1)
                            _next_cells.append((y, x+1, step+1))
                    else: # 初めて通る
                        tables[y][x+1] = str(step+1)
                        _next_cells.append((y, x+1, step+1))
        # end for
        next_cells = list(set(_next_cells)) # 重複カット
    # end while
    if tables[H-1][W-1] == ".":
        return -1
    return white_count - int(tables[H-1][W-1])
    
if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = [[i for i in input()]for i in range(H)]
maze = [[False for i in range(W)] for i in range(H)]
bknum = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            maze[i][j]=True
        else:
            maze[i][j]=False
            bknum += 1


def ncell(i, j):
    tmp = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
    out = []
    for p in tmp:
        if 0<=p[0]<H and 0<=p[1]<W and maze[i][j]:
            out.append(p)
    return out

d = [[1000 for j in range(W)] for i in range(H)]
prev = [[-1 for j in range(W)] for i in range(H)]
d[0][0]=0
Q = set()
for i in range(H):
    for j in range(W):
        if maze[i][j]:
            Q.add(i*W+j)
while(len(Q)!=0):
    u = list(Q)[0]
    du = d[u//W][u%W]
    for v in Q:
        if d[v//W][v%W]<du:
            du = d[v//W][v%W]
            u=v
    Q -=set([u])
    for v in ncell(u//W, u%W):
        if d[v[0]][v[1]]>d[u//W][u%W]+1:
            d[v[0]][v[1]]=d[u//W][u%W]+1
            prev[v[0]][v[1]]=u
length=d[H-1][W-1]
if length != 1000:
    print(H*W-length-1-bknum)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    visited[1][1] = True
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            for t1, t2 in zip([-1,+1,0,0],[0,0,-1,1]):
                dx = x + t1
                dy = y + t2
                if S[dy][dx] != '#' and not visited[dy][dx]:
                    if dy == H and dx == W:
                        return dist
                    un.append((dx,dy))
                    visited[dy][dx] = True
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.append('#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
M=[input() for _ in range(H)]
dist=0
visited=[[False]*W for _ in range(H)]
q=deque([(0,0,0)])
visited[0][0]=True
while q:
    x,y,dist=q.popleft()
    for i in range(4):
        nx,ny=x+[-1,0,1,0][i],y+[0,-1,0,1][i]
        if 0<=nx and nx<W and 0<=ny and ny<H and M[ny][nx]=='.' and not visited[ny][nx]:
            q.append((nx,ny,dist+1))
            visited[ny][nx]=True
    if x==W-1 and y==H-1:
        c=0
        for m in M:
            c+=m.count('.')
        print(c-dist-1)
        exit()
print(-1)

Submission status: Accepted

Solution code:
import heapq

def change(i):
    if i == ".":
        return 500
    return -1

h, w = map(int, input().split())

maze = []

for _ in range(h):
    maze.append([change(i) for i in input()])

B = 0
for _ in maze:
    B += _.count(-1)

l = []

maze[0][0] = 1
heapq.heappush(l, (1, 0, 0))
while len(l) > 0:
    S, H, W = heapq.heappop(l)
    if (H, W) == (h-1, w-1):
        break
    
    for i in range(-1, 2, 2):
        y = H+i
        if y >= 0 and y < h:
            if maze[H][W]+1 < maze[y][W]:
                maze[y][W] = maze[H][W]+1
                heapq.heappush(l, (maze[H][W]-1+h-y+w-W,y, W))
    for i in range(-1, 2, 2):
        x = W+i
        if x >= 0 and x < w:
            if maze[H][W]+1 < maze[H][x]:
                maze[H][x] = maze[H][W]+1
                heapq.heappush(l, (maze[H][W]-1+h-H+w-x, H, x))

if maze[-1][-1] == 500:
    print(-1)
else:
    print(h*w-B-maze[-1][-1])

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = tuple(input() for _ in [0] * H)

    maze = ['#' * (W + 2)] * (H + 2)
    dot = 0
    for i, s in enumerate(S):
        dot += s.count('.')
        maze[i+1] = '#' + s + '#'

    before = deque([(1, 1)])
    step = [[None for i in range(W+2)] for j in range(H+2)]
    step[1][1] = 0
    while len(before) > 0:
        x, y = before.popleft()
        if (x, y) == (W, H):
            print(dot - (step[y][x] + 1))
            break
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            if '.' in maze[y+j][x+i] and step[y+j][x+i] == None:
                before.append((x+i, y+j))
                step[y+j][x+i] = step[y][x] + 1
    else:
        print(-1)

main()

Submission status: Accepted

Solution code:
# coding: UTF-8
#@document_it
from collections import deque
def document_it(func):
    def new_function(*args,**kwargs):
        print('Running function:', func.__name__)
        print('Positional arguments:', args)
        print('Kewword arguments:', kwargs)
        result = func(*args,**kwargs)
        print('Result:', result)
        return result
    return new_function
###########################

#@document_it
#O(1)のはず
def nb(i,j,H,W):
    ans = []
    a = i+1
    b = i-1
    c = j+1
    d = j-1
    if a >= 0 and a <= H-1:
        ans.append((a,j))
    if b >= 0 and b <= H-1:
        ans.append((b,j))
    if c >= 0 and c <= W-1:
        ans.append((i,c))
    if d >= 0 and d <= W-1:
        ans.append((i,d))
    return ans
        

def e():
    #入力データ整理
    dist={}
    white = {}
    wtotal = 0
    H,W = map(int,input().split())
    for i in range(H):
        row = input()
        for j in range(W):
            dist[(i,j)] = -1
            if row[j] == '.':
                white[(i,j)] = True
                wtotal += 1
            else:
                white[(i,j)] = False
    #リンク作成
    #tuple -> [tuple]
    #リンクの数は最大でも頂点の4倍なのでO(HW)
    link = {}
    for i in range(H):
        for j in range(W):
            link[(i,j)] = []
            if not white[(i,j)]:
                continue
            else:
                nlist = nb(i,j,H,W)
                for p in nlist:
                    if white[p]:
                        link[(i,j)].append(p)
    
    q = deque()
    dist[(0,0)] = 1
    q.append((0,0))
    while q:
        v = q.popleft()
        for w in link[v]:
            if dist[w] == -1:
                dist[w] = dist[v] + 1
                q.append(w)
                #print(w,dist[w])
    if dist[(H-1,W-1)] != -1:
        ans = wtotal - dist[(H-1,W-1)]
    else:
        ans = -1
    #print(wtotal)
    #print(dist[(H-1,W-1)])
                    
    print(ans)

###########################
if __name__ == '__main__':
    e()

Submission status: Accepted

Solution code:
from Queue import Queue
d = [0, 1, 0, -1]
h, w = map(int, raw_input().split())
m = list()
m.append(["#" for _ in xrange(w+2)])
for _ in xrange(h):
    m.append(["#"]+list(raw_input())+["#"])
m.append(["#" for _ in xrange(w+2)])
dat = len(filter(lambda x:x==".", [i for j in m for i in j]))

q = Queue()
q.put((1,1,1))

while not q.empty():
    xy = q.get()
    if not m[xy[0]][xy[1]] == ".":
        continue
    m[xy[0]][xy[1]] = xy[2]
    for i in xrange(4):
        e = (xy[0]+d[i], xy[1]+d[i+1&3], xy[2]+1)
        if m[xy[0]+d[i]][xy[1]+d[i+1&3]] == ".":
            q.put(e)

try:
    print dat-m[h][w]
except:
    print -1

Submission status: Accepted

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

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

dx = [0,0,1,-1,1,1,-1,-1]
dy = [1,-1,0,0,1,-1,1,-1]
dist = [[-1 for x in range(W)] for x in range(H)]

q = []
dist[0][0] = 0
q.append((0,0))

while len(q) != 0:
    current = q[0]
    del q[0]
    x = current[0]
    y = current[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0:
            continue
        if nx >= H or ny >= W:
            continue
        if dist[nx][ny] != -1:
            continue
        if grid[nx][ny] == "#":
            continue
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx,ny))

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

Submission status: Accepted

Solution code:
#幅優先探索
#参考↓
#https://abc007.contest.atcoder.jp/submissions/2107192

R,C = [int(i) for i in input().split()]
#sy,sx =  [int(i) for i in input().split()] #スタートの座標が入力で与えられる場合
#gy,gx =  [int(i) for i in input().split()] #ゴールの座標が入力で与えられる場合

#左上が(1,1)かつ周囲をシャープで囲むので、スタート地点は(2,2)となる
sy,sx = 2,2 
gy,gx = R+1, C+1

count=0 # .の数を数える

c_org = [ [ -1 if c_org == "#" else 9999 for c_org in input()] for r in range(R)]

#周囲をシャープ(というか-1)で囲む------------------------------
#c_org の左右を囲む
for i in range(R):
    c_org[i].append( -1)
    c_org[i].insert(0,-1)
    count=count+c_org[i].count(9999)
c_plus=[-1 for i in range(C+2)]

#上下も囲んだ配列をcとする
c=[]
c.append(c_plus)
for i in range(R):
    c.append(c_org[i])
c.append(c_plus)
#-------------------------------------------------------------------

#既にシャープで囲れている場合はこちら
#c=c_org[:]

c[sy - 1][sx - 1] = 0

neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]
check_list = [(sy - 1, sx - 1)]
index = 0

while index < len(check_list):
    check_rc = check_list[index]
    for neighbor in [ (check_rc[0] + n[0], check_rc[1] + n[1]) for n in neighbors]:
        if c[neighbor[0]][neighbor[1]] >= 0 and  c[neighbor[0]][neighbor[1]] > c[check_rc[0]][check_rc[1]] + 1:
            c[neighbor[0]][neighbor[1]] = c[check_rc[0]][check_rc[1]] + 1
            check_list.append(neighbor)
    index += 1


#---------------------------------------------------
#print(c[gy - 1][gx - 1]) #最短移動数
#print(count)
if c[gy - 1][gx - 1]!=9999:
    print(count-c[gy - 1][gx - 1]-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,raw_input().split())
c=[]
for i in range(H):
	s=list(raw_input())
	for j in s:
		if j=="#":
			c.append(1)
		else:
			c.append(0)


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

p0=[-1,1,W]
p1=[-W,1,W]
p2=[-W,-1,W]
p3=[-W,-1,1]
p4=[-W,-1,1,W]
for i in range(H*W):
	if c[i]==0:
		if i==0:
			if c[i+1]==0:nl[i].append(i+1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W-1:
			if c[i-1]==0:nl[i].append(i-1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W*(H-1):
			if c[i-W]==0:nl[i].append(i-W)
			if c[i+1]==0:nl[i].append(i+1)		
		elif i==W*H-1:
			if c[i-W]==0:nl[i].append(i-W)
			if c[i-1]==0:nl[i].append(i-1)
		elif i<W-1:
			for j in p0:
				if c[i+j]==0:nl[i].append(i+j)			
		elif i%W==0:
			for j in p1:
				if c[i+j]==0:nl[i].append(i+j)	
		elif i%W==W-1:
			for j in p2:
				if c[i+j]==0:nl[i].append(i+j)
		elif i>W*(H-1):
			for j in p3:
				if c[i+j]==0:nl[i].append(i+j)
		else:
			for j in p4:
				if c[i+j]==0:nl[i].append(i+j)


V=[ None for i in range(H*W)]
d=[ float("inf") for i in range(H*W) ]

def bfs(start):
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				d[i]=d[v]+1

bfs(0)

if V[H*W-1] is None:
	print -1
else:
	print H*W-(d[H*W-1]+1)-sum(c)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(H,W,S):
	V = [[False for i in range(W)] for j in range(H)]
	qu = deque([(0,0,1)])
	V[0][0] = True
	while(qu):
		p,q,r = qu.popleft()
		S[p][q] = '#'
		for d in [(-1,0), (0,-1), (1,0), (0,1)]:
			s = p+d[0]
			t = q+d[1]
			if s < 0 or t < 0 or s >= H or t >= W:
				continue
			if s == (H-1) and t == (W-1) and S[s][t] == '.':
				return r+1
			if S[s][t] == '.' and V[s][t] == False:
				V[s][t] = True
				qu.append((s,t,r+1))
	return -1

H, W = list(map(int, input().split()))
S = []
cnt = 0
for i in range(H):
	a = str(input())
	tmp = []
	for i in a:
		if (i == '.'):
			cnt += 1
		tmp.append(i)
	S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
	print(cnt - step)
else:
	print(step)

Submission status: Accepted

Solution code:
H,W = map(int, raw_input().split())
S = [raw_input() for _ in range(H)]
#solve by dycstra
#pad by max value
D = [[H*W]*W for _ in range(H)]
D[0][0] = 0
Q = [(0,0)]
while len(Q) > 0:
	cx,cy = Q.pop(0)
	for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
		x = cx + dx
		y = cy + dy
		if 0 <= x < W and 0 <= y < H and S[y][x] == "." and D[cy][cx] + 1 < D[y][x]: 
			D[y][x] = D[cy][cx] + 1
			Q.append((x, y))

if D[H-1][W-1] < H*W:
	print sum([s.count(".") for s in S]) - D[H-1][W-1] - 1
else:
	print -1

Submission status: Accepted

Solution code:
from collections import deque


def main():
    """
    ゲームの開始時点ではマス (1,1)
    上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す
    白いマスだけを通って (H,W) にたどり着けばゲームクリア

    マス (i,j) 最初
    白で塗られている場合 .
    黒で塗られている場合 #

    いくつかの白いマス目の色を黒に変えることができる
    ただし, マス (1,1) と (H,W) の色を変えることはできず
    -> ルートの変更は不可能

    ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる
    最大のスコアを求めなさい
    → 最短距離を求め,必要ない白マスを黒に変えれば高スコア(BFS?)
    → 経路を覚えておかないといけない
    """
    H, W = map(int, input().split())
    S = [
        input()
        for _ in range(H)
    ]

    bfs(S, H, W)


def bfs(S, H, W):
    # 距離を追加, 経路情報は必要ない
    q = deque([(0, 0, 0)])
    visited = [
        [False] * W
        for _ in range(H)
    ]
    visited[0][0] = True

    goal = False
    dist = 0
    while q:
        x, y, dist = q.popleft()
        if (x, y) == (W-1, H-1):
            goal = True
            break

        for dx in (-1, 1):
            nx = x+dx
            if 0 <= nx < W:
                if S[y][nx] == "." and not visited[y][nx]:
                    q.append((nx, y, dist+1))
                    visited[y][nx] = True
        for dy in (-1, 1):
            ny = y+dy
            if 0 <= ny < H:
                if S[ny][x] == "." and not visited[ny][x]:
                    q.append((x, ny, dist+1))
                    visited[ny][x] = True

    if goal:
        w_count = 0
        for s in S:
            w_count += s.count(".")
        # startは通ってないので距離に含まれない
        print(w_count - dist - 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
H, W = list(map(int, input().split()))
S = list()
for i in range(H) :
    S.append(input())
dist = [[3000 for j in range(W)] for i in range(H)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
q = queue.Queue()
dist[0][0] = 0
q.put([0, 0])
while q.empty() == False:
    x, y = q.get()
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H :
            if S[ny][nx] == '.' and dist[ny][nx] > dist[y][x] + 1 :
                dist[ny][nx] = dist[y][x] + 1
                q.put([nx, ny])
cnt = 0
for i in range(H) :
    for j in range(W) :
        if S[i][j] == '.' :
            cnt += 1
print(-1 if dist[H-1][W-1] == 3000 else cnt - dist[H-1][W-1] - 1)

Submission status: Accepted

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

A = []
whites = 0

for i in range(H):
    row_i = []
    for j in range(W):
        if lst[i][j] == '.':
            whites += 1
            tmp = []
            if i != 0:
                if lst[i-1][j] == '.':
                    tmp.append((i-1, j))
            if j != 0:
                if lst[i][j-1] == '.':
                    tmp.append((i, j-1))
            if i != H-1:
                if lst[i+1][j] == '.':
                    tmp.append((i+1, j))
            if j != W-1:
                if lst[i][j+1] == '.':
                    tmp.append((i, j+1))
            row_i.append(tmp)
        else:
            row_i.append([])
    A.append(row_i)

Q = [(0, 0, 0)]
visited = []

flag = False

while len(Q) != 0:
    x, y, path_length = Q.pop(0)
    if (x,y) == (H-1, W-1):
        flag = True
        break
    if (x,y) not in visited:
        visited.append((x,y))
        Q += [(i, j, path_length + 1) for (i, j) in A[x][y]]

if flag:
    print(whites - path_length - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

nNM = []
nNM = input().rstrip().split(' ')

nH = int(nNM[0])
nW = int(nNM[1])
nTmp = [0 for i in range(nW)]

graph = {}
kyori = {}
checked = {}

nWallCnt = 0

for i in range(nH):
    nTmp=input()
#    print(nTmp)
    
    for i2 in range(nW):

#        print(nTmp[i2]) 
        nPoi=('%d-%d' %(i,i2))
        graph[nPoi] = []
        kyori[nPoi] = float("inf")
        checked[nPoi] = 0
        
        if i==0 and i2==0:
            nStart = ('%d-%d' %(0,0))
            kyori[nPoi] = int (0)

        if i==nH - 1 and i2==nW - 1:
            nGoal = ('%d-%d' %(nH - 1, nW - 1))

        elif nTmp[i2]=='#':
            nWall = ('%d-%d' %(i,i2))
            nWallCnt += 1
            checked[nPoi] = 1

        else:
            if i - 1 >= 0:
                graph[nPoi].append('%d-%d' %(i - 1, i2))

            if i + 1 < nH :
                graph[nPoi].append('%d-%d' %(i + 1 , i2))

            if i2 - 1 >= 0:
                graph[nPoi].append('%d-%d' %(i , i2 - 1))

            if i2 + 1 < nW:
                graph[nPoi].append('%d-%d' %(i , i2 + 1))
        


root_queue = deque()
root_queue += graph[nStart]
nCount = len(graph[nStart])

for i in range(nCount):
    kyori[(graph[nStart][i])] = 1


nFlag = 0


while root_queue:
    nPoi2 = root_queue.popleft()

    if checked[nPoi2] == 0:
        if nPoi2 == nGoal:
            nFlag = 1
            break
        else:
            root_queue += graph[nPoi2]
            for i in range(len(graph[nPoi2])):
                nTmpCount = kyori[nPoi2] + 1
                if kyori[(graph[nPoi2][i])] > nTmpCount:
                    kyori[(graph[nPoi2][i])] = nTmpCount
            checked[nPoi2] = 1


if nFlag == 0:
    print('-1')
else:
    nTmp = kyori[nGoal] + 1
    nTotal = nH * nW
    nAns = nTotal - (nTmp + nWallCnt )
    print(nAns)

Submission status: Accepted

Solution code:
import queue
H, W = list(map(int, input().split()))
S = list()
for i in range(H) :
    t = input()
    S.append(t)
dist = [[3000 for j in range(W)] for i in range(H)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
q = queue.Queue()
dist[0][0] = 0
q.put([0, 0])
while q.empty() == False:
    x, y = q.get()
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H :
            if S[ny][nx] == '.' and dist[ny][nx] > dist[y][x] + 1 :
                dist[ny][nx] = dist[y][x] + 1
                q.put([nx, ny])
cnt = 0
for i in range(H) :
    for j in range(W) :
        if S[i][j] == '.' :
            cnt += 1
print(-1 if dist[H-1][W-1] == 3000 else cnt - dist[H-1][W-1] - 1)

Submission status: Accepted

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

   b = 0
   for i in range(H):
      for j in range(W):
         if s[i][j] == "#":
            b = b+1

   flag = [[0 for _ in range(W)] for _ in range(H)]
   Q = []
   Q.append((0,0,0))
   flag[0][0] = 1

   while Q != []:
      v = Q.pop(0)
      if v[0:2] == (H-1,W-1):
         return H*W - b - v[2] -1
      else:
         if v[0] != 0: # up
            if (flag[v[0]-1][v[1]]==0)and(s[v[0]-1][v[1]]=="."):
               Q.append((v[0]-1, v[1],v[2]+1))
               flag[v[0]-1][v[1]] = 1
         if v[0] != H-1: # down
            if (flag[v[0]+1][v[1]]==0)and(s[v[0]+1][v[1]]=="."):
               Q.append((v[0]+1, v[1], v[2]+1))
               flag[v[0]+1][v[1]] = 1
         if v[1] != 0: # left
            if (flag[v[0]][v[1]-1]==0)and(s[v[0]][v[1]-1]=="."):
               Q.append((v[0], v[1]-1, v[2]+1))
               flag[v[0]][v[1]-1] = 1
         if v[1] != W-1: # left
            if (flag[v[0]][v[1]+1]==0)and(s[v[0]][v[1]+1]=="."):
               Q.append((v[0], v[1]+1, v[2]+1))
               flag[v[0]][v[1]+1] = 1
   return -1

print(fanc())

Submission status: Accepted

Solution code:
from collections import deque

def bfs(field):
    q = deque([(0, 0, 1)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == ".":
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == ".":
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == ".":
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == ".":
            q.append((i, j + 1, d + 1))
        
    else:
        return -1

h, w = map(int, input().split())
field = [input() for _ in range(h)]
b = sum(r.count("#") for r in field)
res = bfs(field)
if res == -1:
    print(-1)
else:
    print(h * w - res - b)

Submission status: Accepted

Solution code:
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, v, q):
    if q.empty(): return -1
    k, i, j = q.get()
    if i == len(m) - 1 and j == len(m[i]) - 1: return k
    if i > 0 and m[i - 1][j] == '.' and (i - 1, j) not in v:
        q.put((k + 1, i - 1, j))
        v.add((i - 1, j))
    if i < len(m) - 1 and m[i + 1][j] == '.' and (i + 1, j) not in v:
        q.put((k + 1, i + 1, j))
        v.add((i + 1, j))
    if j > 0 and m[i][j - 1] == '.' and (i, j - 1) not in v:
        q.put((k + 1, i, j - 1))
        v.add((i, j - 1))
    if j < len(m[i]) - 1 and m[i][j + 1] == '.' and (i, j + 1) not in v:
        q.put((k + 1, i, j + 1))
        v.add((i, j + 1))
    return s(m, v, q)
     
h, w = map(int, raw_input().split())
m = [raw_input() for _ in range(h)]
q = Queue.PriorityQueue()
q.put((1, 0, 0))
v = set((0, 0))
c = s(m, v, q)
if c == -1: print -1
else: print h * w - c - sum([r.count('#') for r in m])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(list(e for e in line.strip()) for line in sys.stdin.readlines())
    nwhites = sum(si.count('.') for si in s)

    que = deque([(0, 0, 1)])
    d = (1, 0, -1)
    h -= 1
    w -= 1
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y > h or x < 0 or x > w or s[y][x] == '#':
            continue
        elif y == h and x == w:
            print(nwhites - nsteps)
            break
        s[y][x] = '#'
        nsteps += 1
        que.extend([(y + dy, x + dx, nsteps) for dy in d for dx in d
                    if (dy != 0 or dx != 0) and dy * dx == 0])
    else:
        print('-1')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(tuple(e for e in line.strip()) for line in sys.stdin.readlines())
    nwhites = sum(si.count('.') for si in s)

    que = deque([(0, 0, 1)])
    d = (1, 0, -1)
    visited = [[False] * w for _ in range(h)]
    h -= 1
    w -= 1
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y > h or x < 0 or x > w or visited[y][x] == True or s[y][x] == '#':
            continue
        elif y == h and x == w:
            print(nwhites - nsteps)
            break
        visited[y][x] = True
        nsteps += 1
        que.extend([(y + dy, x + dx, nsteps) for dy in d for dx in d
                    if (dy != 0 or dx != 0) and dy * dx == 0])
    else:
        print('-1')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# BFS version

#
H, W = list(map(int, input().split()))
M = []
for i in range(H):
    M.append(list(input().rstrip()))

#
def walk(pos):
    queue = [pos]

    while len(queue)>0:
        pos = queue.pop(0)
        x, y = pos
        val = M[y][x]
        #print(x,y,val)

        # up
        if y>0 and (M[y-1][x]=='.' or (isinstance(M[y-1][x], int) and val+1<M[y-1][x])):
            M[y-1][x] = val + 1
            queue += [(x, y-1)]
        # down
        if y<H-1 and (M[y+1][x]=='.' or (isinstance(M[y+1][x], int) and val+1<M[y+1][x])):
            M[y+1][x] = val + 1
            queue += [(x, y+1)]
        # left
        if x>0 and (M[y][x-1]=='.' or (isinstance(M[y][x-1], int) and val+1<M[y][x-1])):
            M[y][x-1] = val + 1
            queue += [(x-1, y)]
        # right
        if x<W-1 and (M[y][x+1]=='.' or (isinstance(M[y][x+1], int) and val+1<M[y][x+1])):
            M[y][x+1] = val + 1
            queue += [(x+1, y)]
        #print('B')

#
M[H-1][W-1] = 1
walk((W-1, H-1))
#print(M)
#exit()

#
if M[0][0]=='.':
    print(-1)
else:
    blocks = sum([m.count('#') for m in M])
    print(H*W - blocks - M[0][0])

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
from collections import defaultdict
G = defaultdict(list)

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret
 
def dijkstra(G, n, start):
    d = [float('inf')] * n
    d[start] = 0
    Q = set(range(n))
    preQ = None
    while len(Q) != 0:
        preQ = Q
        u = mind(Q, d)
        Q = Q - set([u])
        for v in G[u]:
            if d[v] > d[u] + 1:
                d[v] = d[u] + 1
        if Q == preQ:
            break
    return d
s = []

i2num = {}
count = 0
start = 0

for i in range(h):
    r = input()
    s.append([r[j] for j in range(w)])
    count += s[i].count('#')
num=-1
for i in range(h):
    r = s[i]
    for j in range(w):
        if r[j] != '1':
            num += 1
            i2num[(i,j)] = num
        if r[j] == 's':
            start = num
            r[j] = '0'
        elif r[j] == 'g':
            goal = num
            r[j] = '0'
G = defaultdict(list)
r = c = 1
for r in range(h):
    for c in range(w):
        t = s[r][c]
        if t == '#': continue
        num = i2num[(r,c)]
        if r - 1 >= 0 and s[r - 1][c] == '.':
            G[num].append(i2num[(r - 1, c)])
        if r + 1 < h and s[r+1][c] == '.':
            G[num].append(i2num[(r + 1, c)])
        if c - 1 >= 0 and s[r][c - 1] == '.':
            G[num].append(i2num[(r, c - 1)])
        if c + 1 < w and s[r][c + 1] == '.':
            G[num].append(i2num[(r, c + 1)])

d = dijkstra(G, h*w, start)
if d[-1] == float('inf'):
    print('-1')
else:
    print(h*w-(d[-1]+1)-count)