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
def DFS(graph,start,end):
    #  深さ優先探索ではスタックを用いたが幅優先探索ではキューを用いる
    c,r = len(graph[0]),len(graph)
    que = deque([])
    que.append(start)
    visited = [[0 for _ in range(c)] for _ in range(r)]

    while visited[end[0]][end[1]]==0:
        if len(que)== 0:
            break
        now = que.popleft()
        y,x = now
        up,down,left,right = [y-1,x],[y+1,x],[y,x-1],[y,x+1]

        #up
        if visited[up[0]][up[1]]==0:
            if graph[up[0]][up[1]]==".":
                que.append(up)
                visited[up[0]][up[1]]= visited[y][x]+1
            
        #down
        if visited[down[0]][down[1]]==0:
            if graph[down[0]][down[1]]==".":
                que.append(down)
                visited[down[0]][down[1]]= visited[y][x]+1
        #left
        if visited[left[0]][left[1]]==0:
            if graph[left[0]][left[1]]==".":
                que.append(left)
                visited[left[0]][left[1]]= visited[y][x]+1
        #right
        if visited[right[0]][right[1]]==0:
            if graph[right[0]][right[1]]==".":
                que.append(right)
                visited[right[0]][right[1]]= visited[y][x]+1
    
    return visited[end[0]][end[1]]

def main():
    h,w = map(int,input().split())
    ls = [list(input()) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if ls[i][j]=="#":
                cnt += 1

    dummy = ["#" for _ in range(w+2)]
    for i in range(h):
        ls[i].append("#")
        ls[i].insert(0,"#")
    ls.insert(0,dummy)
    ls.append(dummy)

    step = DFS(ls,[1,1],[h,w])+1

    if step == 1:
        print(-1)
    else:
        print(h*w-step-cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
h, w = map(int, input().split())
queue = collections.deque()
maze = [list(input()) for _ in range(h)]

origin = 0
for i in maze:
    origin += i.count('#')
# print(origin)


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x):
        return
    if (maze[y][x] != '.'):
        return
    maze[y][x] = cnt
    if (y == h - 1 and x == w - 1):
        return cnt
    queue.append([y + 1, x, cnt + 1])
    queue.append([y - 1, x, cnt + 1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x-1, cnt+1])


queue.append([0, 0, 0])
while (len(queue) > 0):
    l = queue.popleft()
    bfs(l[0], l[1], l[2])
if (maze[h - 1][w - 1] == '.'):
    print(-1)
    exit()

# print(ans)
print(h*w-origin-maze[h-1][w-1]-1)

Submission status: Accepted

Solution code:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == H - 1 and w == W - 1:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                 visited[new_h][new_w] == -1:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
    
    return visited[H-1][W-1]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    sh, sw = 0, 0

    visited = [[-1] * W for _ in range(H)]
    
    step_cnt = bfs(maze, visited, sh, sw)

    white_cnt = sum([i.count(".") for i in maze])

    if step_cnt > 0:
        print(white_cnt - step_cnt)
    else:
        print(-1)

Submission status: Accepted

Solution code:
# ABC088D - Grid Repainting
def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = [(0, 0)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            # find unsearched grids of S and keep them in the queue
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and D[nx][ny] == 0:
                q.append((nx, ny))
                D[nx][ny] = D[x][y] + 1


def main():
    # shortest path needs to remain white, the rest can be black
    global H, W, S, D
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    D = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    D[0][0] = 1
    bfs()
    white, x = sum(s.count(".") for s in S), D[-1][-1]
    ans = white - x if x else -1  # x = 0 <-> can't make a path to goal
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC088D - Grid Repainting
from collections import deque

def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            # find unsearched grids of S and keep them in the queue
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and D[nx][ny] == 0:
                q.append((nx, ny))
                D[nx][ny] = D[x][y] + 1


def main():
    # shortest path needs to remain white, the rest can be black
    global H, W, S, D
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    D = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    D[0][0] = 1
    bfs()
    white, x = sum(s.count(".") for s in S), D[-1][-1]
    ans = white - x if x else -1  # x = 0 <-> can't make a path to goal
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


#input
lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]

def slv(lines):
    white = sum([r.count(".") for r in map])
    q=[[0,0]]
    memo[0][0]=1
    while q!=[]:
        x,y=q.pop(0)
        for pm1 in [1,-1]:
            if x+pm1>=0 and x+pm1<w:
                if map[y][x+pm1] == "." and memo[y][x+pm1]<0:
                    q.append([x+pm1,y])
                    memo[y][x+pm1]=memo[y][x]+1
            if y+pm1>=0 and y+pm1<h:
                if map[y+pm1][x] == "." and memo[y+pm1][x]<0:
                    q.append([x,y+pm1])
                    memo[y+pm1][x]=memo[y][x]+1

    goal=memo[h-1][w-1]

    if goal == -1:
        return -1
    else:
        return white - goal
    


if __name__ == "__main__":
    print(slv(lines))

Submission status: Accepted

Solution code:
import queue

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

maze = [0 for i in range(h)]
maze2 = [[10**5 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    li = []
    for j in s:
        li.append(j)
    maze[i] = li
 
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            cnt += 1

que = queue.Queue()
maze2[0][0] = 1
que.put([0,0])

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

while not que.empty():
    q = que.get()
    a = q[0]
    b = q[1]
    
    for i in range(4):
        c = a+dx[i]
        d = b+dy[i]
       
        
        if ((0<=c) and (c<h) and (0<=d) and (d<w) and (maze2[c][d]==100000) and (maze[c][d]=='.')):
            maze2[c][d] = maze2[a][b]+1
            que.put([c,d])
            

ans = maze2[h-1][w-1]

if maze2[h-1][w-1] == 100000:
    print(-1)
else:
    print(h*w - ans - cnt)

Submission status: Accepted

Solution code:
t,*g=open(0);h,w=map(int,t.split());v=[[0]*w for _ in range(h)];v[0][0]=1;q=[(0,0)]
while q:
	a,b=q.pop(0)
	for c,d in((-1,0),(0,-1),(1,0),(0,1)):
		x=a+c;y=b+d
		if w>x>=0<=y<h and v[y][x]<1 and g[y][x]==".":q+=[(x,y)];v[y][x]=v[b][a]+1
t=v[-1][-1];print((-1,h*w-sum(c.count("#")for c in g)-t)[t>0])

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
grid=[input() for _ in range(h)]
vis=[[0]*w for _ in range(h)]
vis[0][0]=1
que=deque([(0,0)])
while que:
	p,q=que.popleft()
	for x,y in ((-1,0),(0,-1),(1,0),(0,1)):
		if 0<=p+x<w and 0<=q+y<h and vis[q+y][p+x]<1 and grid[q+y][p+x]==".":
			vis[q+y][p+x]=vis[q][p]+1
			que.append((p+x,q+y))
if not vis[h-1][w-1]:
	print(-1)
else:
	print(h*w-sum(c.count("#")for c in grid)-vis[h-1][w-1])

Submission status: Accepted

Solution code:
from collections import deque, Counter
import sys
H, W = map(int, input().split())
count = 0
grid = ['s' for h in range(H)]
for h in range(H):
    grid[h] = list(input())
    tmp_count = Counter(grid[h])['#']
    if tmp_count == W:
        print(-1)
        sys.exit()
    count += tmp_count

deq = deque([(0, 0)])
visited = [[-1 for w in range(W)] for h in range(H)]
visited[0][0] = 0
route = 0
while deq:
    for _ in range(len(deq)):
        h, w = deq.popleft()
        #print(h, w)
        if (h, w) == (H - 1, W - 1):
            print(H * W - visited[h][w] - 1 - count)
            sys.exit()
        for j, k in ([-1, 0], [0, -1], [0, 1], [1, 0]):
            new_h, new_w = h + j, w + k
            if 0 <= new_h <= H - 1 and 0 <= new_w <= W - 1:
                if grid[new_h][new_w] != '#' and visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    deq.append((new_h, new_w))
print(-1)

Submission status: Accepted

Solution code:
class Queue:
    def __init__(self, data=[]):
        self.data = data

    def enqueue(self, x):
        self.data.append(x)  # 末尾に追加する

    def dequeue(self):
        return self.data.pop(0)  # 先頭を取り出す

    def is_Empty(self):  # 空であればTrueを返す
        if len(self.data) == 0:
            return True
        else:
            return False


H, W = map(int, input().split())  # H行, W列

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

black_count = 0
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == '#':
            black_count += 1

flag = [[False] * W for _ in range(H)]
counter = [[0] * W for _ in range(H)]
counter[0][0] = 1
flag[0][0] = True
q = Queue()

q.enqueue((0, 0))

adjacent = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 遷移先を網羅する
while not q.is_Empty():
    cy, cx = q.dequeue()
    for dy, dx in adjacent:
        if cy+dy >= H or cy+dy < 0 or cx+dx >= W or cx+dx < 0:
            continue
        if flag[cy+dy][cx+dx] or gridgraph[cy+dy][cx+dx] == '#':
            continue
        counter[cy+dy][cx+dx] = counter[cy][cx] + 1
        flag[cy+dy][cx+dx] = True
        q.enqueue((cy+dy, cx+dx))

# print(flag)
if flag[H-1][W-1]:
    print(H*W - counter[H-1][W-1] - black_count)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
sy, sx = 0, 0
gy, gx = H-1, W-1
field = [list(input()) for _ in range(H)]
step = [[-1]*W for _ in range(H)]
step[sy][sx] = 0
tovisit = deque()
tovisit.append([sy, sx])

while tovisit:
  y, x = tovisit.popleft()
  for next_y, next_x in [[y+1, x], [y-1, x], [y, x+1], [y, x-1]]:
    if 0 <= next_y < H and 0 <= next_x < W and field[next_y][next_x] != '#':
      if step[next_y][next_x] == -1:
        tovisit.append([next_y, next_x])
        step[next_y][next_x] = step[y][x] + 1

sum_block = sum([l.count('#') for l in field])
steps = step[gy][gx]
print(-1 if steps == -1 else H*W - sum_block - steps - 1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
INF = float('inf')

def main():
    def bfs(x, y):
        L = [[INF]*W for _ in range(H)]
        L[0][0] = 1
        Q = deque([[0,0]])
        while len(Q)!=0:
            x, y = Q.popleft()
            if x==W-1 and y==H-1:
                break
            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:
                    if M[ny][nx]=='.' and L[ny][nx]==INF:
                        Q.append([nx, ny])
                        L[ny][nx] = L[y][x] + 1
        return L[H-1][W-1]
    
    H, W = map(int, input().split())
    M = []
    cnt = 0
    for _ in range(H):
        m = list(input()[:-1])
        cnt += m.count('#')
        M.append(m)

    b = bfs(0, 0)
    if b==INF:
        print(-1)
    else:
        print(H*W - cnt - b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(x, y):
    for i in range(4):
        dx, dy = dxdy[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
            if ds[ny][nx] == float('inf'):
                ds[ny][nx] = ds[y][x] + 1
                q.append([nx, ny])


q = collections.deque([[0, 0]])
while q:
    x, y = q.popleft()
    bfs(x, y)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

q = [[0, 0]]


def bfs():
    while q:
        x, y = q.pop()
        for i in range(4):
            dx, dy = dxdy[i]
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
                if ds[ny][nx] > ds[y][x] + 1:
                    ds[ny][nx] = ds[y][x] + 1
                    q.append([nx, ny])


bfs()
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(q):
    while q:
        x, y = q.pop()
        for i in range(4):
            dx, dy = dxdy[i]
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
                if ds[ny][nx] > ds[y][x] + 1:
                    ds[ny][nx] = ds[y][x] + 1
                    q.append([nx, ny])


q = [[0, 0]]
bfs(q)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Submission status: Accepted

Solution code:
import collections
H,W = map(int,input().split())
Map = []
black_cnt = 0
for i in range(H):
    tmp = list(input())
    black_cnt += tmp.count('#')
    Map.append(tmp)

Counter = [[float('inf') for j in range(W)]for i in range(H)]
Visited = [[False for j in range(W)]for i in range(H)]
q = collections.deque()
q.append((0,0,0))
while q:
    y,x,cnt = q.popleft()
    if 0>y or H<=y or 0>x or W<=x:
        continue
    if Map[y][x] == '#':
        continue
    Counter[y][x] = min(Counter[y][x],cnt)
    if Visited[y][x]:
        continue
    Visited[y][x]=True
    
    cnt += 1
    q.append((y+1,x,cnt))
    q.append((y-1,x,cnt))
    q.append((y,x+1,cnt))
    q.append((y,x-1,cnt))
if Visited[H-1][W-1] == False:
    print('-1')
else:
    print(H*W-Counter[H-1][W-1]-black_cnt-1)

Submission status: Accepted

Solution code:
import collections
H,W = map(int,input().split())
Map = []
black_cnt = 0
for i in range(H):
    tmp = list(input())
    black_cnt += tmp.count('#')
    Map.append(tmp)

Counter = [[float('inf') for j in range(W)]for i in range(H)]
Visited = [[False for j in range(W)]for i in range(H)]
q = collections.deque()
q.append((0,0,0))
while q:
    y,x,cnt = q.popleft()
    if 0>y or H<=y or 0>x or W<=x:
        continue
    if Map[y][x] == '#':
        continue
    if cnt > Counter[y][x]:
        continue
    if Visited[y][x]:
        continue
    Visited[y][x]=True
    Map[y][x] = cnt
    cnt += 1
    q.append((y+1,x,cnt))
    q.append((y-1,x,cnt))
    q.append((y,x+1,cnt))
    q.append((y,x-1,cnt))
if Visited[H-1][W-1] == False:
    print('-1')
else:
    print(H*W-Map[H-1][W-1]-black_cnt-1)

Submission status: Accepted

Solution code:
import numpy as np
H, W = map(int,input().split())
S = []
maxval = 10000
blacknum = 0
for i in range(H):
    S.append(input())
board = np.zeros((H+2,W+2), dtype=np.int64)
dist = np.full((H+2,W+2), maxval, dtype=np.int64)
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i-1][j-1] == '#':
            board[i][j] = 1
            dist[i][j] = maxval
            blacknum += 1
        else:
            board[i][j] = 0
            dist[i][j] = maxval
dist[1][1] = 0
for iter in range(563):
    update_flag = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            if board[i][j] == 1:
                continue
            newdist = min([dist[i-1][j], dist[i+1][j], dist[i][j-1], dist[i][j+1]])+1
            if newdist < dist[i][j]:
                dist[i][j] = newdist
                update_flag = 1
    if update_flag == 0:
        break
pass_cell = dist[H][W] + 1
maxscore = H*W - pass_cell - blacknum
if pass_cell >= maxval:
    print(-1)
else:
    print(maxscore)


# 最長経路は1226マスなので1226回るーぷすればいい
# 1226*2500=3065000なのできついか？
# 下に49マス右に49マスは必須なのでこれはループ1回分
# 上や左に進んだ数と同じだけ下や右に進む必要があるので、
# (1226-98)/2 + 1 = 563ループでいけそう
# →563*2500 = 1407500. 大体半分になったけどまだつらそう
# ループのたびに走査方向を切り替えると速くなる…？
# (左から右、上から下)と(右から左、下から上)の2種類持つ感じで

# 1ループで変化がなければフラグ立てて終了させる

Submission status: Accepted

Solution code:
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    c_of_sharp = 0
    for i in range(h):
        line = list(input())
        for c in line:
            if c == '#':
                c_of_sharp += 1
        f.append(line)
    sy, sx = (0, 0)
    q = deque([[sy, sx]])
    BIG = 100000
    f2 = [[BIG for i in range(w)] for j in range(h)]
    f2[0][0] = 0
    s = True

    while q:
        y, x = q.pop()
        if (y, x) == (h-1, w-1):
            break
        for dy, dx in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= y+dy < h and 0 <= x+dx < w and f2[y+dy][x+dx] == BIG and \
                f[y+dy][x+dx] != '#':
                f2[y+dy][x+dx] = f2[y][x]+1
                q.appendleft([y+dy, x+dx])
    else:
        s = False
        print(-1)

    if s:
        print(h*w-f2[h-1][w-1]-c_of_sharp-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

maze = ['#'*(W+2)]
maze += ['#'+input().strip()+'#' for _ in range(H)]
maze.append('#'*(W+2))
maze_map = [[float('inf')]*(W+2) for _ in range(H+2)]
maze_map[1][1] = 1

# 幅優先
mem = [(1,1)]

while True:
  if len(mem) == 0: break
  x,y = mem.pop()
  for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
    if maze[y+dy][x+dx] == '.':
      if maze_map[y+dy][x+dx] > maze_map[y][x]+1:
        maze_map[y+dy][x+dx] = maze_map[y][x]+1
        mem.append((x+dx,y+dy))
        
if maze_map[H][W] == float('inf'):
  print(-1)
else:
  w = sum(m.count('.') for m in maze)
  print(w-maze_map[H][W])

Submission status: Accepted

Solution code:
import queue
Data = []
Path = []
H,W = map(int,input().split())

def bfs(sy,sx,R,C):
    q = queue.Queue()
    q.put([sy,sx])

    diff = [[1,0],[-1,0],[0,1],[0,-1]]
    Path[sy][sx] = 0
    Data[sy][sx] = 'x'

    count = 1 
    while not q.empty():
        x = q.get()
        r,c = x
        for di in diff:
            rr = r + di[0]
            cc = c + di[1]

            if rr >= 0 and cc >= 0 and rr < R and cc < C:
                if Data[rr][cc] == '.':
                    q.put([rr,cc])
                    Path[rr][cc] = Path[r][c]+1
                    Data[rr][cc] = 'x'

for _ in range(H):
    Data.append(list(input()))
block = 0
for d in Data:
    for x in d:
        if x == '#':
            block += 1

for _ in range(H):
    Path.append([-1]*W)
bfs(0,0,H,W)
n = Path[H-1][W-1]

if n == -1:
    print(-1)
else:
    ans = H*W-block-n-1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]


que = deque([(0, 0, 1)])


result = -1
while que:
    ci, cj, step = que.popleft()
    visited[ci][cj] = True
    if (ci, cj) == (H-1, W-1):
        result = step
        break

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
            continue
        if S[ni][nj] == '.':
            visited[ni][nj] = True
            que.append((ni, nj, step+1))

if result == -1:
    print(-1)
else:
    W = 0
    for s in S:
        W += s.count('.')
    print(W-result)

Submission status: Accepted

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

Q = [[0, 0, 0]]
V = [[0] * w for i in range(h)]
D = [[float("inf")] * w for i in range(h)]
st = 0
while st < len(Q):
    # print(Q)
    if Q[st] == [h-1, w-1]:
        D[-1][-1] = Q[st][2]
        break
    else:
        i = Q[st][0]
        j = Q[st][1]
        d = min(Q[st][2], D[i][j])
        D[i][j] = d

        if V[i][j] == 0:
            V[i][j] = 1
            for di, dj in [[-1,0], [1,0], [0,-1], [0,1]]:
                if 0 <= i+di <= h-1 and 0 <= j+dj <= w-1 and S[i+di][j+dj] == "." and V[i+di][j+dj] == 0:
                    Q.append([i+di, j+dj, d+1])
    st += 1

white = sum([S[i].count(".") for i in range(h)])
# print(white)

#print(D[-1][-1])

ans = white - D[-1][-1] - 1
if ans == -float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
dx = [1,0,-1,0]
dy = [0,1,0,-1]
field = []
for i in range(h):
    field.append(list(input()))

dist = [[-1 for i in range(w)] for j in range(h)]
dist[0][0] = 0
q = deque([[0,0]])
while q:
    v = q.popleft()
    for i in range(4):
        nh = v[0] + dx[i]
        nw = v[1] + dy[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w:
            continue
        if field[nh][nw] == '#':
            continue
        if dist[nh][nw] != -1:
            continue
        dist[nh][nw] = dist[v[0]][v[1]] + 1
        q.append([nh,nw])

if dist[h-1][w-1] == -1:
    print(-1)
else:
    black_cnt = 0
    for i in range(h):
        for j in range(w):
            if field[i][j] == '#':
                black_cnt += 1
    print(h*w - black_cnt - dist[h-1][w-1] - 1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = ["#"*(W+2)]
for i in range(H):
    s = input()
    S.append("#"+s+"#")
S.append("#"*(W+2))

white = 0
for i in range(H+2):
    for j in range(W+2):
        if S[i][j] == ".":
            white += 1
flag = 0 
visited = {}
import heapq
#[cost i j]
heap = []
heapq.heappush(heap, [0,1,1])
while heap != []:
    cost, i, j = heapq.heappop(heap)
    #print(cost,i,j)
    visited[(i,j)] = cost
    if i == H and j == W:
        flag = 1
        break
    else:
        for k in range(2):
            d = 2*k - 1
            if S[i+d][j] == ".":
                if (i+d,j) in visited:
                    if visited[(i+d,j)] > cost + 1:
                        visited[(i+d,j)] = cost + 1
                        heapq.heappush(heap, [cost+1,i+d,j])
                else:
                    visited[(i+d,j)] = cost + 1
                    heapq.heappush(heap, [cost+1,i+d,j])
            if S[i][j+d] == ".":
                if (i,j+d) in visited:
                    if visited[(i,j+d)] > cost + 1:
                        visited[(i,j+d)] = cost + 1
                        heapq.heappush(heap, [cost+1,i,j+d])
                else:
                    visited[(i,j+d)] = cost + 1
                    heapq.heappush(heap, [cost+1,i,j+d])

#print(white)
#print(visited)
if flag == 1:
    print(white - cost - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    black_cnt = 0
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#': black_cnt += 1

    q = deque([(0,0,0)])
    visited = [[False]*W for _ in range(H)]
    visited[0][0] = True
    while q:
        y,x,step = q.popleft()
        if y == H-1 and x == W-1:
            print(H*W-(step+1)-black_cnt)
            return 0
        for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
            ny = y+dy
            nx = x+dx
            if 0<=ny<H and 0<=nx<W and not visited[ny][nx] and grid[ny][nx] == '.':
                q.append((ny,nx,step+1))
                visited[ny][nx] = True

    print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
L = [list(input().strip()) for _ in range(N)]

m = [[10 ** 18 for _ in range(M)] for _ in range(N)]

def bfs(x, y, c):
    if L[x][y] == "#":
        return

    if m[x][y] <= c:
        return

    m[x][y] = c

    if x + 1 < N:
        bfs(x + 1, y, c + 1)

    if y + 1 < M:
        bfs(x, y + 1, c + 1)

    if x - 1 >= 0:
        bfs(x - 1, y, c + 1)

    if y - 1 >= 0:
        bfs(x, y - 1, c + 1)

bfs(0, 0, 0)

if m[-1][-1] == 10 ** 18:
    print(-1)
    exit()

def dfs(x, y, c):
    if x == 0 and y == 0:
        L[x][y] = "o"
        return True
    for (_x, _y) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if x + _x < N and x + _x >= 0 and y + _y < M and y + _y >= 0:
            if c - 1 == m[x + _x][y + _y]:
                if dfs(x + _x, y + _y, c - 1):
                    L[x][y] = "o"
                    return True
    return False

dfs(N - 1, M - 1, m[-1][-1])

ans = 0
for v in L:
    ans += len([0 for c in v if c == "."])

print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

from collections import deque

h, w = map(int, sys.stdin.readline().strip().split(" "))

field = []
for _ in range(h):
    field.append(list(sys.stdin.readline().strip()))

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

def bfs(field, h, w, sy, sx, gy, gx):
    q = deque()
    q.append((0, sy, sx))
    visited = set()
    while q:
        count, y, x = q.popleft()
        for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            if 0 <= y+dy < h and 0 <= x+dx < w:
                if field[y+dy][x+dx] == "#":
                    continue
                elif (y+dy, x+dx) in visited:
                    continue
                elif (y+dy, x+dx) == (h-1, w-1):
                    return count+1

                visited.add((y+dy, x+dx))
                q.append((count+1, y+dy, x+dx))
    return -1

shortest = bfs(field, h, w, 0, 0, h-1, w-1)
# print(shortest)
if shortest == -1:
    print(-1)
else:
    print(h*w - black - (shortest+1))

Submission status: Accepted

Solution code:
def main():

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

    # print(grid)
    white = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == ".":
                white += 1

    cur = [[0, 0]]
    goal = [H-1, W-1]
    turn = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    reached = False
    grid[0][0] = "#"
    while cur and not reached:
        temp = []
        for i, j in cur:
            if [i, j] == goal:
                reached = True
                break
            for di, dj in mv:
                i1 = i + di
                j1 = j + dj
                if 0 <= i1 < H and 0 <= j1 < W and grid[i1][j1] == ".":
                    grid[i1][j1] = "#"
                    temp.append([i1, j1])
        if not reached:
            cur = temp
            turn += 1
    if not reached:
        return -1
    return  white - (turn+1)


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