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: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
sy, sx, gy, gx = 0, 0, H-1, W-1

q = deque([[sy, sx]])
visited = [[-1]*W for _ in range(H)]
visited[sy][sx] = 0

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while q:
  y, x = q.popleft()
  if [y, x] == [gy, gx]:
    break
  for dy, dx in d:
    ny, nx = y+dy, x+dx
    if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
      continue
    if maze[ny][nx] == "." and visited[ny][nx] == -1:
      visited[ny][nx] = visited[y][x] + 1
      q.append([ny, nx])

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

print(H*W - black - visited[gy][gx] - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
total_block = h * w
h += 2
w += 2
area = []
explored = []

wall_num = 0

for i in range(h):
    if i == 0 or i == h-1:
        a = '#' * w
    else:
        a = input()
        for j in a:
            if j == '#':
                wall_num += 1
        a = '#' + a + '#'
    area.append(a)

distance = [[float('inf') for _ in range(w)] for _ in range(h)]
distance[1][1] = 0

q = deque()
if area[1][2] == '.':
    q.append([1, 2])
    distance[1][2] = 1
    explored.append([1, 2])
if area[2][1] == '.':
    q.append([2, 1])
    distance[2][1] = 1
    explored.append([2, 1])

explored.append([1, 1])

while len(q) != 0:
    now = q.popleft()
    a = now[0]
    b = now[1]
    d = distance[a][b]
    l = [[a+1, b], [a-1, b], [a, b+1], [a, b-1]]
    for x, y in l:
        if area[x][y] == '.' and [x, y] not in explored:
            q.append([x, y])
            distance[x][y] = d + 1
            explored.append([x, y])

print(total_block - wall_num - distance[h-2][w-2] - 1)

Submission status: Wrong Answer

Solution code:
import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
sx,sy,gx,gy = 0,0,h-1,w-1

def bfs(sy,sx):
    #頂点をINFで初期化
    d = [[INF]*w for i in range(h)]
    #移動４方向のベクトル
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    #スタート地点をキューにいれ、頂点を０にする
    que = collections.deque([])
    que.append((sy,sx))
    d[sy][sx] = 0
    #キューが空になるまでループ（行ける要素がなくなるまで）
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        # 移動4方向をループ
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            #壁との判定とすでに訪れたかどうかをチェック
            if 0<=nx and nx < w and 0 <= ny and ny < h:
                if li[ny][nx] != "#" and d[ny][nx] == INF:
                    #移動できる点なのでキューについか
                    que.append((ny,nx))
                    #前の点+1で移動できる
                    d[ny][nx] = d[p[0]][p[1]] + 1
    return d[-1][-1]
a = bfs(0,0)-1
if a + 1 == INF:
    print(-1) 
maxgrid = h*w
cnt = 0
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            cnt+=1
ans = maxgrid - cnt - a -2
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
sx,sy,gx,gy = 0,0,h-1,w-1

def bfs(sy,sx):
    #頂点をINFで初期化
    d = [[INF]*w for i in range(h)]
    #移動４方向のベクトル
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    #スタート地点をキューにいれ、頂点を０にする
    que = collections.deque([])
    que.append((sy,sx))
    d[sy][sx] = 0
    #キューが空になるまでループ（行ける要素がなくなるまで）
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        # 移動4方向をループ
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            #壁との判定とすでに訪れたかどうかをチェック
            if 0<=nx and nx < w and 0 <= ny and ny < h:
                if li[ny][nx] != "#" and d[ny][nx] == INF:
                    #移動できる点なのでキューについか
                    que.append((ny,nx))
                    #前の点+1で移動できる
                    d[ny][nx] = d[p[0]][p[1]] + 1
    return d[-1][-1]
a = bfs(0,0)-1
maxgrid = h*w
cnt = 0
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            cnt+=1
ans = maxgrid - cnt - a -2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

s=[list(input().strip()) for i in range(h)]

dis=[[0]*w for i in range(h)]
visited = [[0]*w for i in range(h)]

total_point=0
for i in range(h):
    for u in range(w):
        if s[i][u]==".":
            total_point+=1

def bfs(y, x):
    q = deque([])
    q.append((y, x, -1))
    while len(q):
        
        y, x, d = q.popleft()
        if visited[y][x]==0:
            dis[y][x] = d+1
            visited[y][x] = 1
            if y==h-1 and x==w-1:
                break
            
            dx = [0, -1 ,0 ,1]
            dy = [-1 ,0 ,1 ,0]
            for i in range(4):
                
                nx = x + dx[i]
                ny = y + dy[i]
                if nx<0 or ny<0 or nx>=w or ny>=h or visited[ny][nx]==1 or s[ny][nx]=="#":
                    continue
                q.append((ny, nx, dis[y][x]))
bfs(0,0)
print(total_point-dis[h-1][w-1]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(S,W,H):
    dx=(-1,0,1,0)
    dy=(0,1,0,-1)
    queue=deque([[0,0]])
    visited=[]
    goal=False
    cnt=deque([0])
    while queue and goal==False:
        exe=queue.popleft()
        C=cnt.popleft()
        visited.append(exe)
        for i in range(len(dx)):
            x=exe[0]+dx[i]
            y=exe[1]+dy[i]
            if [x,y]==[W-1,H-1]:
                goal=True
            elif 0<=x<=W-1 and 0<=y<=H-1 and S[y][x]==".":
                if [x,y] not in visited:
                    queue.append([x,y])
                    cnt.append(C+1)
    return C+1

def main():
    H,W=map(int,input().strip().split())
    S=[list(input()) for _ in range(H)]
    # number of dot
    num_sharp=0
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                num_sharp+=1
    return W*H-num_sharp-(bfs(S,W,H)+1)

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

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
maze = []
for _ in range(H):
    l = list(input())
    maze.append(l)
import collections as col
q = col.deque()
q.append((0,0))
maze[0][0] = 0
def bfs(maze):
    while True:
        try: nowx,nowy = q.popleft()
        except IndexError:
            print("-1")
            quit()
        if nowx == (H - 1) and nowy == (W - 1): return
        for x in [1,-1]: 
            if nowx + x == H or nowy == W: continue
            if maze[nowx + x][nowy] != '.' : continue
            if 0 <= nowx + x and nowx + x <= H - 1:
                q.append((nowx+x,nowy))
                maze[nowx + x][nowy] = maze[nowx][nowy] + 1
        for y in [1,-1]: 
            if nowx == H or nowy + y== W: continue
            if maze[nowx][nowy + y] != '.' : continue
            if 0 <= nowy + y and nowy + y <= W - 1:
                q.append((nowx,nowy+y))
                maze[nowx][nowy + y] = maze[nowx][nowy] + 1
bfs(maze)
cnt = 0
for x in maze:
    for y in x:
        if y == '#':
            cnt += 1
print(H*W - maze[H-1][W-1] - cnt - 1)

print(maze)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
black_cells = 0
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            black_cells += 1

dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
que = deque()
que.append((0, 0))
flag = False

while len(que) > 0:
    now_y, now_x = que.popleft()
    now_dist = dist[now_y][now_x]
    for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_dist + 1
        if dist[h - 1][w - 1] != -1:
            flag = True
            break
    if flag:
        break

if flag:
    print(h * w - black_cells - dist[h - 1][w - 1] - 1)
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
import queue
h, w = list(map(int, input().split()))
s = [[' ']*(w+1) for i in range(h+1)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            cnt += 1
def bfs():
    d =[[10**10]*(w) for i in range(h)]

    que = queue.Queue()

    que.put([0, 0])
    d[0][0] = 0

    while not que.empty():
        p = que.get()
        if p[0] == h and p[1] == w:
            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] == 10**10:
                que.put([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[h-1][w-1]

print(cnt - bfs() - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().split())
    total_cells = H * W
    existing_black_cells = 0

    grid = [['' for _ in range(W)] for _ in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            grid[i][j] = line[j]
            if line[j] == '#':
                existing_black_cells += 1

    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)): # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]

            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return

            for dx, dy in [(1, 0), (0, 1)]:
                X = x+dx
                Y = y+dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and adjacent not in visited and grid[Y][X] == '.':
                    queue.append(adjacent)
    print(-1)
    return
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().split())
    total_cells = H * W
    existing_black_cells = 0

    grid = [['' for _ in range(W)] for _ in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            grid[i][j] = line[j]
            if line[j] == '#':
                existing_black_cells += 1

    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    print(grid)
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)): # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]

            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return

            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x+dx
                Y = y+dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and adjacent not in visited and grid[Y][X] == '.':
                    queue.append(adjacent)
    print(-1)
    return

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

class Pos:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return 'Pos(' + str(self.x) + ', ' + str(self.y) + ')'
    
    def __add__(self, other):
        return Pos(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Pos(self.x - other.x, self.y - other.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __ne__(self, other):
        return not(self.x == other.x and self.y == other.y)

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

# もともとの黒マスの数を調べる
count = 0
for y in range(H):
    for x in range(W):
        count += 1 if s[y][x] == '#' else 0

# 訪問済みリスト
visited = [[-1 for _ in range(W)] for _ in range(H)]

# 訪問予定リスト
d = deque()

visited[0][0] = 0
d.appendleft(Pos(0, 0))

while d:
    now = d.pop()
    nexts = [now+Pos(0, 1), now+Pos(0, -1), now+Pos(1, 0), now+Pos(-1, 0)]
    for next in nexts:
        x, y = next.x, next.y
        if 0 <= x < W and 0 <= y < H:
            if s[y][x] == '.' and visited[y][x] == -1:
                visited[y][x] = visited[now.y][now.x] + 1
                d.appendleft(next)

print(H*W-(visited[H-1][W-1]+1)-count)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, Counter, defaultdict
import heapq


def resolve():
    n_rows, n_cols = map(int, sys.stdin.readline().strip().split())
    matrix = [[]] * n_rows
    n_whites = 0
    for i in range(n_rows):
        row = list(sys.stdin.readline().strip())
        for c in row:
            if c == '.':
                n_whites += 1
        matrix[i] = row

    shortest_path = 1
    queue = deque()
    queue.append((0, 0))
    while queue:
        shortest_path += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            nexts = (
                (x+1, y),
                (x-1, y),
                (x, y+1),
                (x, y-1),
            )
            for nx, ny in nexts:
                if (nx, ny) == (n_rows-1, n_cols-1):
                    break
                if 0 <= nx < n_rows and 0 <= ny < n_cols and matrix[nx][ny] == '.':
                    matrix[nx][ny] = '#'
                    queue.append((nx, ny))
            else:
                continue
            break
        else:
            continue
        break

    print(n_whites - shortest_path)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

s = ['1'*(W+2)]
cntw = 0

for i in range(H):
    a = input()
    a = a.replace('.', '0').replace('#', '1')
    cntw += a.count('0')
    s.append('1'+a+'1')
s.append('1'*(W+2))

visited = [[0] * (W+2) for _ in range(H+2)]
visited[1][1] = 1
temp = deque([[1, 1, 0]])
ans = 0

while temp:
    p = temp.popleft()
    if p[0:2] == [H, W]:
        ans= p[2]
        break
    else:
        for k in [[1, 0], [-1, 0], [0, 1],[0, -1]]:
            if s[p[0]+k[0]][p[1]+k[1]] == '0' and visited[p[0]+k[0]][p[1]+k[1]] == 0:
                temp.append([p[0]+k[0], p[1]+k[1], p[2]+1])
                visited[p[0]+k[0]][p[1]+k[1]] = 1
    
print(cntw- (ans + 1))

Submission status: Wrong Answer

Solution code:
from collections import deque
import pprint
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
d=deque()
dp=[[float("inf") for _ in range(W)] for _ in range(H)]
dp[0][0]=1
d.append([0,0])
seen=[[0 for _ in range(W)] for _ in range(H)]
seen[0][0]=1
blnum=0
for i in range(H):
    for j in range(W):
        if table[i][j]=="#":
            blnum=blnum+1
while len(d)!=0:
    v=d.popleft()
    x=v[0]
    y=v[1]
    if x!=0:
        if (table[x-1][y]==".")and(seen[x-1][y]==0):
            d.append([x-1,y])
            seen[x-1][y]=1
            dp[x-1][y]=min(dp[x-1][y],dp[x][y]+1)
    if x!=H-1:
        if (table[x+1][y]==".")and(seen[x+1][y]==0):
            d.append([x+1,y])
            seen[x+1][y]=1
            dp[x + 1][y] = min(dp[x + 1][y], dp[x][y] + 1)
    if y!=0:
        if (table[x][y-1]==".")and(seen[x][y-1]==0):
            d.append([x,y-1])
            seen[x][y-1]=1
            dp[x][y-1]=min(dp[x][y-1],dp[x][y]+1)
    if y!=W-1:
        if (table[x][y+1]==".")and(seen[x][y+1]==0):
            d.append([x,y+1])
            seen[x][y+1]=1
            dp[x][y+1]=min(dp[x][y+1],dp[x][y]+1)
    #pprint.pprint(dp)
    #print(d)
    #input()
print(H*W-dp[H-1][W-1]-blnum)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  row = list(input())
  blocks += row.count("#")
  matrix.append(row)

q = [(0,0,0)]
min_step = 0
visited = []

while q:
  r,c,step = q.pop(0)
  visited.append((r,c))

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    q.append((nr,nc,step+1))

print( H*W - blocks - min_step -1 )

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque
INF = 10 ** 10
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [readline().rstrip() for _ in range(H)]
    maze = [[INF] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([(0, 0)])
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            if 0 <= h+dh < H and 0 <= w+dw < W:
                if mat[h+dh][w+dw] == '.' and maze[h+dh][w+dw] > maze[h][w] + 1:
                    maze[h+dh][w+dw] = maze[h][w] + 1
                    que.append((h+dh, w+dw))

    cnt_b = sum([l.count('#') for l in mat])
    print(H * W - cnt_b - (maze[H-1][W-1] + 1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque
INF = 10 ** 10
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [readline().rstrip() for _ in range(H)]
    maze = [[INF] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([(0, 0)])
    flg = True
    while que and flg:
        h, w = que.popleft()
        for dh, dw in directions:
            if 0 <= h+dh < H and 0 <= w+dw < W:
                if mat[h+dh][w+dw] == '.' and maze[h+dh][w+dw] > maze[h][w] + 1:
                    maze[h+dh][w+dw] = maze[h][w] + 1
                    que.append((h+dh, w+dw))
                if h+dh == H-1 and w+dw == W-1:
                    flg = False

    cnt_b = sum([l.count('#') for l in mat])
    print(H * W - cnt_b - (maze[H-1][W-1] + 1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

d = [[0] * W for _ in range(H)]

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

que = deque([])
que.append((0, 0))
d[0][0] = 1
while que:
    x, y = que.popleft()
    
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and d[ny][nx] == 0 and s[ny][nx] == '.':
            que.append((nx, ny))
            d[ny][nx] = d[y][x] + 1

print(H * W - d[H-1][W-1] - block_count)

Submission status: Wrong Answer

Solution code:
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
    if s[i][j]=='#':
        black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() #位置[行,列]を入れておく
def bfs():
    seen[0][0] = 1
    queue.append([0,0])
    min_dist[0][0] = 1
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='#':
                continue
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
    return min_dist[H-1][W-1]
print(H*W-bfs()-black_count)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
maze = [[] for i in range(H)]
for i in range(H):
  maze[i] = list(input())
maze = [['#']*(W+2)]+maze+[['#']*(W+2)]
for i in range(1,H+1):
  maze[i] = ['#']+maze[i]+['#']
def Distance(maze, start, goal, distance):
  visited = set()
  frontier = set()
  visited.add(start)
  frontier.add(start)
  while goal not in visited:
    distance += 1
    newfrontier = set()
    for y,x in frontier:
      for gy,gx in [[y,x-1],[y-1,x],[y,x+1],[y+1,x]]:
        if (gy,gx) not in visited and maze[gy][gx] == '.':
          visited.add((gy,gx))
          newfrontier.add((gy,gx))
    frontier = newfrontier
  return distance
print(H*W-Distance(maze, (1,1), (H,W), 0)-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
area = [['#']*(W+2)]
space = 0
for i in range(H):
    temp = ['#']+list(input())+['#']
    for t in temp:
        if t=='.': space+=1 
    area.append(temp)
area.append(['#']*(W+2))
move = ((1, 0), (-1, 0), (0, 1), (0, -1))

dq = deque([(1,1)])
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 1

while dq:
    nowx, nowy = dq.popleft()
    # if (nowx, nowy) == (W, H): break
    for dx, dy in move:
        nxtx, nxty = nowx+dx, nowy+dy
        if not 0<=nxtx<W+2 and 0<=nxty<H+2: continue
        if dist[nxty][nxtx]>=0 or area[nxty][nxtx]=='#': continue
        dist[nxty][nxtx] = dist[nowy][nowx]+1
        dq.append((nxtx, nxty))
print(space-dist[H][W])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
area = [['#']*(W+2)]
space = 0
for i in range(H):
    temp = ['#']+list(input())+['#']
    for t in temp:
        if t=='.': space+=1 
    area.append(temp)
area.append(['#']*(W+2))
move = ((1, 0), (-1, 0), (0, 1), (0, -1))

dq = deque([(1,1)])
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 0

while dq:
    nowx, nowy = dq.popleft()
    if (nowx, nowy) == (W, H): break
    for dx, dy in move:
        nxtx, nxty = nowx+dx, nowy+dy
        if not 0<=nxtx<W+2 and 0<=nxty<H+2: continue
        if dist[nxty][nxtx]>=0 or area[nxty][nxtx]=='#': continue
        nxtd = dist[nowy][nowx]+1
        dist[nxty][nxtx] = nxtd
        dq.append((nxtx, nxty))
print(space-(dist[H][W]+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
area = [['#']*(W+2)]
space = 0
for i in range(H):
    temp = ['#']+list(input())+['#']
    for t in temp:
        if t=='.': space+=1 
    area.append(temp)
area.append(['#']*(W+2))
move = ((1, 0), (-1, 0), (0, 1), (0, -1))

dq = deque([(1,1)])
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 0

max_dist = 0
while dq:
    nowx, nowy = dq.popleft()
    if (nowx, nowy) == (W, H): break
    for dx, dy in move:
        nxtx, nxty = nowx+dx, nowy+dy
        if not 0<=nxtx<W+2 and 0<=nxty<H+2: continue
        if dist[nxty][nxtx]>=0 or area[nxty][nxtx]=='#': continue
        nxtd = dist[nowy][nowx]+1
        dist[nxty][nxtx] = nxtd
        max_dist = max(max_dist, nxtd)
        dq.append((nxtx, nxty))
print(space-(max_dist+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
bcnt=0
for i in range(h):
    bcnt+=s[i].count('#')
dist=[[-1]*w for _ in range(h)]
r=deque()
r.append([0,0])
dist[0][0]=0
while r:
    x,y=r.popleft()
    for dx,dy in d:
        nx=x+dx
        ny=y+dy
        nd=dist[y][x]
        if nx>=0 and nx<=w-1 and ny>=0 and ny<=h-1:
            if dist[ny][nx]>-1 or s[ny][nx]=='#':
                continue
            dist[ny][nx]=nd+1
            r.append([nx,ny])
if dist[h-1][w-1]==1000:
    print(-1)
else:
    print(h*w-dist[h-1][w-1]-1-bcnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
bcnt=0
for i in range(h):
    bcnt+=s[i].count('#')
dist=[[1000]*w for _ in range(h)]
chk=[[0]*w for _ in range(h)]
r=deque()
r.append([0,0])
dist[0][0]=0
while r:
    x,y=r.popleft()
    chk[y][x]=1
    for dx,dy in d:
        nx=x+dx
        ny=y+dy
        if nx>=0 and nx<=w-1 and ny>=0 and ny<=h-1:
            if chk[ny][nx]==1:
                continue
            if s[ny][nx]=='.':
                dist[ny][nx]=min(dist[ny][nx],dist[y][x]+1)
                r.append([nx,ny])
print(h*w-dist[h-1][w-1]-1-bcnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
bcnt=0
for i in range(h):
    bcnt+=s[i].count('#')
dist=[[1000]*w for _ in range(h)]
chk=[[0]*w for _ in range(h)]
r=deque()
r.append([0,0])
dist[0][0]=0
while r:
    x,y=r.popleft()
    chk[y][x]=1
    for dx,dy in d:
        nx=x+dx
        ny=y+dy
        if nx>=0 and nx<=w-1 and ny>=0 and ny<=h-1:
            if chk[ny][nx]==1:
                continue
            if s[ny][nx]=='.':
                dist[ny][nx]=min(dist[ny][nx],dist[y][x]+1)
                r.append([nx,ny])
print(dist)
print(h*w-dist[h-1][w-1]-1-bcnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 100000

# 入力
H, W = map(int, input().split())

maze = [input() for i in range(H)]

# 移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# (sx,sy)から(gx,gy)への最短距離を求める
# たどりつけないとINF

def bfs():
    que = deque([])
    # 全ての点をINFで初期化
    d = [[INF for j in range(W)] for i in range(H)]

    # スタート地点をキューに入れ、その点の距離を0にする
    que.append([0,0])
    d[0][0]= 0

    # キューが空になるまでループ
    while len(que) > 0:
        # キューの先頭を取り出す
        p = que.popleft()
        #取り出してきた状態がゴールなら探索をやめる
        if p[0] == H-1 and p[1] == W-1:
            break
        # 移動4方向をループ
        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] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[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 < INF:
    print(white - bfs() - 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 100000

# 入力
H, W = map(int, input().split())

maze = [input() for i in range(H)]

# 移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# (sx,sy)から(gx,gy)への最短距離を求める
# たどりつけないとINF

def bfs():
    que = deque([])
    # 全ての点をINFで初期化
    d = [[INF for j in range(W)] for i in range(H)]

    # スタート地点をキューに入れ、その点の距離を0にする
    que.append([0,0])
    d[0][0]= 0

    # キューが空になるまでループ
    while len(que) > 0:
        # キューの先頭を取り出す
        p = que.popleft()
        #取り出してきた状態がゴールなら探索をやめる
        if p[0] == H-1 and p[1] == W-1:
            break
        # 移動4方向をループ
        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] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[H-1][W-1]

white = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            white += 1
print(maze)
res = bfs()
if 0 < res < INF:
    print(white - bfs() - 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 100000000

# 入力
H, W = map(int, input().split())

maze = [input() for i in range(H)]

# 移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# (sx,sy)から(gx,gy)への最短距離を求める
# たどりつけないとINF

def bfs():
    que = deque([])
    # 全ての点をINFで初期化
    d = [[INF for j in range(W)] for i in range(H)]

    # スタート地点をキューに入れ、その点の距離を0にする
    que.append([0,0])
    d[0][0]= 0

    # キューが空になるまでループ
    while len(que) > 0:
        # キューの先頭を取り出す
        p = que.popleft()
        #取り出してきた状態がゴールなら探索をやめる
        if p[0] == H-1 and p[1] == W-1:
            break
        # 移動4方向をループ
        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] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[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 < INF:
    print(white - bfs() - 1)
else:
    print(-1)