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())
S = [list(input()) for _ in range(H)]


def bfs():
    q = [(0, 0, 1)]
    m = []
    while len(q) > 0:
        x, y, c = q.pop(0)
        for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
            if (H, W) == (yy + 1, xx + 1):
                return c + 1
            if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                    (xx, yy) not in m:
                m.append((xx, yy))
                q.append((xx, yy, c + 1))
    return -1


def main():
    dc = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                dc += 1
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(dc - c)


main()

Submission status: Accepted

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


def bfs():
    q = [(0, 0, 1)]
    m = []
    while len(q) > 0:
        x, y, c = q.pop(0)
        for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
            if (H, W) == (yy + 1, xx + 1):
                return c + 1
            if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                    (xx, yy) not in m:
                m.append((xx, yy))
                q.append((xx, yy, c + 1))
    return -1


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(ans - c)


main()

Submission status: Accepted

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


def bfs():
    q = [(0, 0)]
    nq = []
    m = []
    c = 1
    while len(q) > 0:
        while len(q) > 0:
            x, y = q.pop(0)
            for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
                if (H, W) == (yy + 1, xx + 1):
                    return c + 1
                if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                        (xx, yy) not in m:
                    m.append((xx, yy))
                    nq.append((xx, yy))
        q = nq
        nq = []
        c += 1
    return -1


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(ans - c)


main()

Submission status: Accepted

Solution code:
from queue import Queue


def bfs(s):
    q = Queue()
    q.put(((0,0), 0))
    found = set()
    while q.qsize() > 0:
        x, nsteps = q.get()
        if x in found:
            continue
        found.add(x)
        for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = (x[0]+d[0], x[1]+d[1])
            if y[0] < 0 or y[0] >= H or y[1] < 0 or y[1] >= W:
                continue
            if s[y[0]][y[1]] == '#':
                continue
            if y == (H-1, W-1):
                return nsteps+1
            if y in found:
                continue
            q.put((y, nsteps+1))
    return -1




H, W = list(map(int, input().split(' ')))
s = []
nwhites = 0
for i in range(H):
    s.append([c for c in input()])

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

nsteps = bfs(s)

if nsteps == -1:
    print(-1)
else:
    print(nwhites - nsteps - 1)

Submission status: Accepted

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

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

D = [[-1] * W for i in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    Q = []
    Q.append([0, 0])
    D[0][0] = 0
    
    while Q != []:
        p = Q.pop(0)
        if p[0] == H - 1 and p[1] == W - 1:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '#' and D[nx][ny] == -1:
                Q.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
                
    return D[H - 1][W - 1]

x = bfs()

if x == -1:
    print(-1)
else:
    print(cnt - x - 1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])
    return -1

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    if path_area:
        print(H*W-path_area-black)
    else:
        print(-1)
                
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue

q = queue.Queue()
H,W = map(int, input().split())
memo = [[-1]*W for _ in range(H)]
board = [input() for _ in range(H)]
wall=0
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def bfs():
    memo[0][0] = 0
    q.put((0, 0))
    while not q.empty():
        y,x= q.get()
        for (dy, dx) in direction:
            if 0<=y+dy<=H-1 and 0<=x+dx<=W-1 and board[y+dy][x+dx] == '.' and memo[y+dy][x+dx] == -1:
                q.put((y + dy, x + dx))
                memo[y + dy][x + dx] = memo[y][x] + 1
                if (y+dy, x+dx) == (H-1, W-1):
                    return memo[H-1][W-1]
    return -1


for s in board:
    wall+=s.count('#')

min_dist=bfs()
print(H*W-wall-(min_dist+1) if min_dist>0 else -1)

Submission status: Accepted

Solution code:
H,W = (int(i) for i in input().split())
grid = ['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]
smap = [[-1 for i in range(W+2)] for i in range(H+2)]
q = []
dot = 0
angle = [[1,0],[-1,0],[0,1],[0,-1]]

for i in grid:
  dot += i.count('.')

smap[1][1] = 1
q.append([1,1])

while len(q) > 0:
  pos = q.pop(0)
  cnt = smap[pos[0]][pos[1]] + 1
  for a in angle:
    if grid[pos[0]+a[0]][pos[1]+a[1]] == '.' and smap[pos[0]+a[0]][pos[1]+a[1]] == -1:
      q.append([pos[0]+a[0],pos[1]+a[1]])
      smap[pos[0]+a[0]][pos[1]+a[1]] = cnt

print(-1) if smap[H][W] == -1 else print(dot - smap[H][W])

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0)])
dist = [[float('inf')]*W for _ in range(H)]
dist[0][0] = 1

while q:
    y,x = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - dist[y][x])
        break
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        nx,ny = x+dx, y+dy
        if not(0<=ny<H and 0<=nx<W):
            continue
        if maze[ny][nx]=="." and dist[ny][nx]==float('inf'):
            q.append((ny, nx))
            dist[ny][nx] = dist[y][x] + 1
else:
    print(-1)

Submission status: Accepted

Solution code:
from sys import exit
import queue
dxy = [[1,0],[-1,0],[0,1],[0,-1]]
INF = (1 << 21)
H,W = [int(n) for n in input().split()]
ans = 0
Map = [[0 for _ in range(W)] for __ in range(H)]
D = [[INF for _ in range(W)] for __ in range(H)]
for h in range(H):
    Map[h] = list(input())
    ans+=Map[h].count(".")
# print(Map)
# print(ans)

def bfs(s):
    q = queue.Queue()
    q.put(s)
    D[s[0]][s[1]] = 1
    while(not q.empty()):
        u = q.get()
        for d in dxy:
            v = [u[0] + d[0], u[1] + d[1]]
            if (v[0] < 0 or v[1] < 0 or v[0] >= H or v[1] >= W or Map[v[0]][v[1]] == "#"):continue
            if (D[v[0]][v[1]] != INF):continue
            D[v[0]][v[1]] = D[u[0]][u[1]] + 1
            q.put(v)
bfs([0,0])
# for th in range(H):
#     print(D[th])
print(ans - D[H-1][W-1]  if D[H-1][W-1] != INF else -1)

Submission status: Accepted

Solution code:
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append([s == '.' for s in input()])
 
inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = [(0, 0)]
p = []
for i in range(h):
    p.append([inf] * w)
p[0][0] = 1
 
while len(queue) > 0:
    x, y = queue.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h:
            if s[yy][xx] and p[yy][xx] > p[y][x] + 1:
                p[yy][xx] = p[y][x] + 1
                queue.insert(0, (xx, yy))
           
if p[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - p[h-1][w-1])

Submission status: Accepted

Solution code:
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append([s == '.' for s in input()])
 
inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = [(0, 0)]
p = []
for i in range(h):
    p.append([inf] * w)
p[0][0] = 1
 
while len(queue) > 0:
    x, y = queue.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h and s[yy][xx] and p[yy][xx] > p[y][x] + 1:
           p[yy][xx] = p[y][x] + 1
           queue.insert(0, (xx, yy))
           
if p[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - p[h-1][w-1])

Submission status: Accepted

Solution code:
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append([s == '.' for s in input()])

inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q = [(0, 0)]
p = []
for i in range(h):
    p.append([inf] * w)
p[0][0] = 1

while len(q) > 0:
    x, y = q.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h and s[yy][xx] and (p[yy][xx] > p[y][x] + 1):
           p[yy][xx] = p[y][x] + 1
           q.insert(0, (xx, yy))
if p[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - p[h-1][w-1])

Submission status: Accepted

Solution code:
def grid_repainting(H: int, W: int, S: int) -> int:
    # ルート探索用の行列。
    # R[h][w] は (0, 0) -> (h, w) の最短距離になる。
    INF = float('inf')
    R = [[INF] * W for _ in range(H)]
    R[0][0] = 1
    white_num = 0

    update = True
    while update:
        update = False
        white_num = 0
        for h in range(H):
            for w in range(W):
                if S[h][w] == '#':
                    # 黒いマス目は無視
                    continue
                white_num += 1

                before = R[h][w]
                if w > 0:
                    R[h][w] = min(R[h][w], R[h][w - 1] + 1)
                if h > 0:
                    R[h][w] = min(R[h][w], R[h - 1][w] + 1)
                if w < W - 1:
                    R[h][w] = min(R[h][w], R[h][w + 1] + 1)
                if h < H - 1:
                    R[h][w] = min(R[h][w], R[h + 1][w] + 1)

                if before != R[h][w]:
                    update = True

    if R[H - 1][W - 1] is INF:
        return - 1

    # R[H-1][W-1] は (0, 0) -> (H-1, W-1) に至るために必要な
    # 最小のマス数になっている。これ以外の全部の白ますは黒マスに変
    # えていいので、それが最大スコア。
    return white_num - R[H-1][W-1]


if __name__ == "__main__":
    H = 0
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = grid_repainting(H, W, S)
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h,w = (int(i) for i in input().split())
maze = [['#' for i in range(w+2)]]+[['#']+[x=='#' for x in input()]+['#'] for i in range(h)]+[['#' for i in range(w+2)]]
#print(maze)
f = 0
for i in range(1,h+1):
 for j in range(1,w+1):
  #　元から塗りつぶされている
  if maze[i][j]:f+=1
#print(f)
flag= 0
pos = deque([(1,1,0)])
while pos:
  x,y,c = pos.popleft()
  #ゴール
  if (x,y) == (h,w):
    print(h*w-f-c-1)
    exit()
  elif maze[x][y]:
    #行き止まり,探索済み
    continue
  #追加の4方向
  pos.append((x-1, y, c+1))
  pos.append((x+1, y, c+1))
  pos.append((x, y-1, c+1))
  pos.append((x, y+1, c+1))
  #print(pos)
  maze[x][y] = True
if flag == 0:
 print(-1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [[1]*(W+2)]
for _ in range(H):
    tmp = [1]
    [tmp.append(int(c=="#")) for c in input()]
    tmp.append(1)
    S.append(tmp)
S.append([1]*(W+2))
       
ans = 0
for w in range(W+2):
    for h in range(H+2):
        if S[h][w]==0:  
            ans += 1

Q = [[1,1,1]]
S[1][1] = 1

def Step():
    while Q:
        q = Q.pop(0)
        if q[0]==H and q[1]==W:
            return(q[2])
        else:
            for M in [[-1,0],[1,0],[0,-1],[0,1]]:
                if S[q[0]+M[0]][q[1]+M[1]] == 0:
                    S[q[0]+M[0]][q[1]+M[1]] = 1
                    Q.append([q[0]+M[0],q[1]+M[1],q[2]+1])
    else:           
        return(-1)
    
step = Step()
if(step==-1):  
    print(-1)
else:
    print(ans-step)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[['#' for i in range(w+2)]]+[['#']+[x=='#' for x in input()]+['#'] for i in range(h)]+[['#' for i in range(w+2)]]
f=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if maze[i][j]:
	    f+=1
z=0
pos=deque([(1,1,0)])
while pos:
    x,y,c=pos.popleft()
    if (x,y)==(h,w):
        print(h*w-f-c-1)
        z=1
        break
    elif maze[x][y]:
        continue
    pos.append((x-1, y, c+1))
    pos.append((x+1, y, c+1))
    pos.append((x, y-1, c+1))
    pos.append((x, y+1, c+1))
    maze[x][y] = True
if z==0:
	print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

nesw = [[0, 1], [0, -1], [1, 0], [-1, 0]]
height, width = map(int, input().split(" "))
root = []
black = 0
for i in range(height):
    temp = [n for n in input()]
    root.append(temp)
    black += temp.count("#")
start_y, start_x = 0, 0
end_y, end_x = height - 1, width - 1

queue = [(start_y, start_x)]
used_white = 1
flag = 0
while queue:
    new_queue = []
    used_white += 1
    for q in queue:
        h, w = q
        for t in nesw:
            new_h, new_w = h + t[0], w + t[1]
            if 0 <= new_h < height and 0 <= new_w < width:
                if new_h == end_y and new_w == end_x:
                    flag = 1
                    break
                elif root[new_h][new_w] != "#":
                    root[new_h][new_w] = "#"
                    new_queue.append((new_h, new_w))
    if flag:
        break
    queue = new_queue
if flag:
    print(height * width - black - used_white)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

def wfs(queue, S, step, goal):
    next_queue = set()
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.add((i+1, j))
        if S[i-1][j] == '.':
            next_queue.add((i-1, j))
        if S[i][j+1] == '.':
            next_queue.add((i, j+1))
        if S[i][j-1] == '.':
            next_queue.add((i, j-1))

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    black = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        black += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    init = set([(1, 1)])
    minstep = wfs(init, S, 0, (H, W))
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - black)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def wfs(queue, S, step, goal):
    next_queue = set()
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.add((i+1, j))
        if S[i-1][j] == '.':
            next_queue.add((i-1, j))
        if S[i][j+1] == '.':
            next_queue.add((i, j+1))
        if S[i][j-1] == '.':
            next_queue.add((i, j-1))

    if len(next_queue) == 0:
        return -1
    else:
        next_queue = list(set(next_queue))
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    black = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        black += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    init = set([(1, 1)])
    minstep = wfs(init, S, 0, (H, W))
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - black)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

queue=deque()
sy,sx=(0,0)
gy,gx=(H-1,W-1)
reached=[[-1 for i in range(W)] for j in range(H)]
queue.append([sy,sx])
reached[sy][sx]=0
dx=[1,-1,0,0]
dy=[0,0,1,-1]
while(queue):
    p=queue.pop()
    for i in range(4):
        y=p[0]+dy[i]
        x=p[1]+dx[i]
        if x<0 or x>=W or y<0 or y>=H or s[y][x]=="#":
            continue
        if reached[y][x]!=-1:
            continue
        reached[y][x]=reached[p[0]][p[1]]+1
        queue.appendleft([y,x])
n=H*W
for i in range(H):
    for j in range(W):
        if s[i][j]=="#":
            n-=1
if reached[gy][gx]==-1:
  n=-1       
print(n-reached[gy][gx]-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
map = [['#'] + [s for s in input().strip()] + ['#'] for _ in range(h)]
n_white = sum(len([s for s in ss if s == '.']) for ss in map)
map = [['#' for _ in range(w+2)]] + map + [['#' for _ in range(w+2)]]

def wfs(next_xy, c):
  tmp_next = set()
  for x, y in next_xy:
    map[y][x] = '#'
    if x == w and y == h:
      return c + 1
    if map[y][x-1] == '.':
      tmp_next.add((x-1, y))
    if map[y][x+1] == '.':
      tmp_next.add((x+1, y))
    if map[y-1][x] == '.':
      tmp_next.add((x, y-1))
    if map[y+1][x] == '.':
      tmp_next.add((x, y+1))
  if len(tmp_next) == 0:
    return -1
  else:
    return wfs(tmp_next, c+1)

pathl = wfs([(1,1)], 0)
if pathl == -1:
  print(-1)
else:
  print(n_white - pathl)

Submission status: Accepted

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

visited = [[-1 for i in range(w)] for j in range(h)]

s = []
cnt = 0
for i in range(h):
    ss = input()
    s.append(ss)
    cnt += ss.count('#')

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

visited[0][0] = 1

while queue:
    a = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = a[1]+j,a[0]+k
        if (0 <= newy <h) and (0 <= newx < w):
            if (visited[newy][newx] == -1) and (s[newy][newx] == "."):
                visited[newy][newx] = visited[a[1]][a[0]] + 1
                queue.append((newx,newy))




if(visited[h-1][w-1] == -1): print("-1")
else:
    print(h*w-visited[h-1][w-1]-cnt)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
field = [input() for _ in range(h)]
direction = [(1,0), (0,1), (-1,0), (0,-1)]
def wfs(c, search, done):
    if search == set():
        return -1
    if (h-1, w-1) in search:
        return c
    newsearch = set()
    for x, y in search:
        for dx, dy in direction:
            xa = x + dx
            ya = y + dy
            if xa in range(h) and ya in range(w) and (xa, ya) not in done and field[xa][ya] == '.':
                newsearch.add((xa, ya))
        done.add((x, y))
    return wfs(c+1, newsearch, done)
ret = wfs(0, {(0,0)}, set())
if ret == -1:
    print(-1)
else:
    white = 0
    for i in range(h):
        for j in range(w):
            if field[i][j] == '.':
                white += 1
    print(white - ret - 1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split(' '))
s = [input() for _ in range(h)]
sy, sx = 0, 0
gy, gx = h - 1, w - 1

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que = [(sy, sx)]
d = [[float('inf') for _ in range(w)] for _ in range(h)]
d[sy][sx] = 0

while len(que) > 0:
    y, x = que.pop(0)

    for dy, dx in move:
        ny = y + dy
        nx = x + dx

        if ny >= 0 and ny < h and nx >= 0 and nx < w and s[ny][nx] != '#' and d[ny][nx] == float('inf'):
            que.append((ny, nx))
            d[ny][nx] = d[y][x] + 1

if d[gy][gx] == float('inf'):
    print(-1)
else:
    n_white = 0
    for i in s:
        n_white += i.count('.')
    print(n_white - d[gy][gx] - 1)

Submission status: Accepted

Solution code:
def BFS_one_search(map_,counts,y,x,wall):
    can_be_new_count = []
    new_ques = []
    for i in range(-1,2):
        for j in range(-1,2):
            if i * j == 0 and i != j:
                if counts[y + i][x + j] != -1:
                    can_be_new_count.append(counts[y + i][x + j] + 1)
                elif not(map_[y + i][x + j] in wall):
                    new_ques.append((y + i,x + j))
    new_count = min(can_be_new_count) if len(can_be_new_count) > 0 else 0
    return new_count,new_ques

def breadth_first_search(map_,s_y,s_x,wall = ['#']):
    ques = [(s_y,s_x)]
    counts = []
    for _ in range(len(map_)):
        counts.append([-1] * len(map_[0]))
    while(len(ques) > 0):
        here_count,new_que = BFS_one_search(map_,counts,ques[0][0],ques[0][1],wall)
        counts[ques[0][0]][ques[0][1]] = here_count
        for i in range(len(new_que)):
            if not new_que[i] in ques:
                ques.append(new_que[i])
        ques.pop(0)
    return counts

def make_map_data(H,W,wall = '#',make_wall = True):
    map_ = []
    if make_wall:
        map_.append([wall] * (W + 2))
        for _ in range(H):
            map_.append([wall] + list(input()) + [wall])
        map_.append([wall] * (W + 2))
    else:
        for _ in range(H):
            map_.append(list(input()))
    return map_
H,W= (int(i) for i in input().split())  
s_y = 1
s_x = 1
g_y = H 
g_x = W
map_ = make_map_data(H,W,make_wall = True)
min_counts = breadth_first_search(map_,s_y,s_x)[g_y][g_x]
if min_counts == -1:
    print(-1)
else:
    wall_count = 0
    for y in range(H + 2):
        for x in range(W + 2):
            if map_[y][x] == '#':
                wall_count += 1
    #print(min_counts)
    print((H + 2) * (W + 2) - wall_count - (min_counts + 1))

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

h,w = map(int,input().split())
white = 0
n = h*w
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
s = []
for i in range(h):
    p = list(input())
    s.append(p)

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white += 1
            if i != h-1 and s[i+1][j] == ".":
                edge[w*i+j].append([1,w*i+j+w])
                edge[w*i+j+w].append([1,w*i+j])
            if j != w-1 and s[i][j+1] == ".":
                edge[w*i+j].append([1,w*i+j+1])
                edge[w*i+j+1].append([1,w*i+j])
#for i in range(len(edge)):
#    print(i,edge[i])
d = dijkstra_heap(0)
#print(d)
if d[-1] == float("inf"):
    print(-1)
else:
    print(white-d[-1]-1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx and nx < h and 0 <= ny and ny < w and\
                maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 1

# 白いマスを数える
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            white += 1

res = bfs()
if 0 < res < float("inf"):
    # 白いマスの数から最短経路でかかるコスト分を引く
    # ゴールを黒いマスに変えることはできないためその分も引く
    print(white - res - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx and nx < h and 0 <= ny and ny < w and\
                maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 1

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

res = bfs()
if 0 < res < float("inf"):
    print(h * w - res - black - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import queue
import sys

write = sys.stdout.write

hoge = list(map(int, input().split()))
H = hoge[0]
W = hoge[1]

class Block:
    visited = False
    parent = None
    def __init__(self, c, x, y):
        self.color = c
        self.x = x
        self.y = y

def trace(A, blk):
    blk.color = "r"
    if blk.x == 1 and blk.y == 1:
        return
    trace(A, blk.parent)

def solve(A):
    global H
    global W

    #ゴールとスタートが黒ならむりぽ
    if A[1][1].color == "#" or A[H][W].color == "#":
        return -1

    q = queue.Queue()
    q.put(A[1][1])
    while not q.empty():
        blk = q.get()
        if blk.x == H and blk.y == W: #ゴールに到達したら通ってきた道を戻って関数を抜け出す
            trace(A, blk)
            return 1
        #上:A[blk.x - 1][blk.y]
        #下:A[blk.x + 1][blk.y]
        #右:A[blk.x][blk.y + 1]
        #左:A[blk.x][blk.y - 1]

        #上
        if A[blk.x - 1][blk.y].visited == False and A[blk.x - 1][blk.y].color == ".":
            A[blk.x - 1][blk.y].parent = blk
            A[blk.x - 1][blk.y].visited = True
            q.put(A[blk.x - 1][blk.y])

        #下
        if A[blk.x + 1][blk.y].visited == False and A[blk.x + 1][blk.y].color == ".":
            A[blk.x + 1][blk.y].parent = blk
            A[blk.x + 1][blk.y].visited = True
            q.put(A[blk.x + 1][blk.y])

        #右
        if A[blk.x][blk.y + 1].visited == False and A[blk.x][blk.y + 1].color == ".":
            A[blk.x][blk.y + 1].parent = blk
            A[blk.x][blk.y + 1].visited = True
            q.put(A[blk.x][blk.y + 1])

        #左
        if A[blk.x][blk.y - 1].visited == False and A[blk.x][blk.y - 1].color == ".":
            A[blk.x][blk.y - 1].parent = blk
            A[blk.x][blk.y - 1].visited = True
            q.put(A[blk.x][blk.y - 1])
    return -1



cnt = 0 #ゴール後の白カウント

maze = [[Block("d", i, j) for j in range(W+2)] for i in range(H+2)]
for i in range(1, H+1):
    row = input()
    for j in range(W):
        maze[i][j+1] = Block(row[j], i, j+1)

possible = solve(maze)

if possible == -1:
    print("-1")
else:
    for i in range(1, H+1):
        for j in range(1, W+1):
            if maze[i][j].color == ".":
                cnt += 1
    print(str(cnt))