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: Runtime Error

Solution code:
from collections import deque

class Map_input():

    def __init__(self):
        line = input().split(" ")
        self.H = int(line[0])
        self.W = int(line[1])
        Map = [[] for i in range(self.H)]
        for i in range(self.H):
            line = input()
            for j in range(self.W):
                if line[j] == ".":
                    Map[i].append(0)
                else:
                    Map[i].append(1)
        self.Map = Map

class Maze_min():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    def __init__(self, H, W, Map, start, goal):
        self.H = H
        self.W = W
        self.Map = Map
        self.goal = goal
        dist = [[-1]*W for i in range(H)]
        dist[0][0] = 0
        self.dist = dist
        self.queue = deque([start])

    def min_step(self):
        if len(self.queue) == 0:
            return -1 #例外は-1とする
        else:
            p = self.queue.popleft()
            if p == self.goal:
                return self.dist[p[0]][p[1]]
            else:
                for i in range(len(Maze_min.dx)):
                    (nx, ny) = (p[0] + Maze_min.dx[i], p[1] + Maze_min.dy[i])
                    if nx in range(self.H) and ny in range(self.W) and self.Map[nx][ny] == 0 and self.dist[nx][ny] == -1:
                        self.queue.append((nx, ny))
                        self.dist[nx][ny] = self.dist[p[0]][p[1]] + 1
                return self.min_step()


M = Map_input()
maze = Maze_min(M.H, M.W, M.Map, (0, 0), (M.H-1, M.W-1))
num_black = sum(list(map(sum, M.Map)))
d = maze.min_step()
if d == -1:
    print(-1)
else:
    print(M.H*M.W-d-num_black-1)

Submission status: Runtime Error

Solution code:
arr=[]
numbero=list(map(int, input().split()))
for i in range(numbero[0]):
    arr.append(input())
way=[[False for i in range(numbero[1])] for j in range(numbero[0])]
def waycon(i,j):
    way[i][j]=True
    if i>0:
        if not way[i-1][j] and arr[i-1][j]=='.':
            waycon(i-1,j)
    if j>0:
        if not way[i][j-1] and arr[i][j-1]=='.':
            waycon(i,j-1)
    if i<numbero[0]-1:
        if not way[i+1][j] and arr[i+1][j]=='.':
            waycon(i+1,j)
    if j<numbero[1]-1:
        if not way[i][j+1] and arr[i][j+1]=='.':
            waycon(i,j+1)
waycon(0,0)
if not way[numbero[0]-1][numbero[1]-1]:
    print(-1)
else:

Submission status: Runtime Error

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

grid=[]
S=""
for i in range(W+2):
    S = S+'#'
grid.append(S)
for i in range(H):
    grid.append('#'+input()+'#')
grid.append(S)

reached=[]
for i in range(H+2):
    reached.append([0*j for j in range(W+2)])

number_of_black_grid=0
for row in grid:
    number_of_black_grid += row.count('#')
s_x=1
s_y=1
g_x=W
g_y=H

def isGoal(x,y,g_x,g_y):
    if x==g_x and y==g_y:
        return True
    else:
        return False

def BFS_search(s_x, s_y, g_x, g_y):
    queue=[]
    queue.append([s_y, s_x, 0])
    reached[s_y][s_x]=0
    while len(queue)>0:
        v=queue.pop(0)
        if grid[v[0]+1][v[1]]=='.' and reached[v[0]+1][v[1]]==0 and [v[0]+1, v[1]]!=[s_y, s_x]:
            reached[v[0]+1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]+1, g_x, g_y):
                break
            else:
                queue.append([v[0]+1, v[1], v[2]+1])
        if grid[v[0]][v[1]+1]=='.' and reached[v[0]][v[1]+1]==0 and [v[0], v[1]+1]!=[s_y, s_x]:
            reached[v[0]][v[1]+1]=v[2]+1
            if isGoal(v[1]+1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]+1, v[2]+1])
        if grid[v[0]-1][v[1]]=='.' and reached[v[0]-1][v[1]]==0 and [v[0]-1, v[1]]!=[s_y, s_x]:
            reached[v[0]-1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]-1, g_x, g_y):
                break
            else:
                queue.append([v[0]-1, v[1], v[2]+1])
        if grid[v[0]][v[1]-1]=='.' and reached[v[0]][v[1]-1]==0 and [v[0], v[1]-1]!=[s_y, s_x]:
            reached[v[0]][v[1]-1]=v[2]+1
            if isGoal(v[1]-1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]-1, v[2]+1])

BFS_search(s_x, s_y, g_x, g_y)
if reached[g_y][g_x] == 0:
    print(-1)
else:
    maximum_score = ((H+2)*(W+2)-number_of_black_grid)-(reached[g_x][g_y]+1)
    print(maximum_score)

Submission status: Runtime Error

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

grid=[]
S=""
for i in range(W+2):
    S = S+'#'
grid.append(S)
for i in range(H):
    grid.append('#'+input()+'#')
grid.append(S)

reached=[]
for i in range(H+2):
    reached.append([0*j for j in range(W+2)])

number_of_black_grid=0
for row in grid:
    number_of_black_grid += row.count('#')
s_x=1
s_y=1
g_x=W
g_y=H

# for i in range(H+2):
#     print(grid[i])
# for i in range(H+2):
#     print(reached[i])


def isGoal(x,y,g_x,g_y):
    if x==g_x and y==g_y:
        return True
    else:
        return False

def BFS_search(s_x, s_y, g_x, g_y):
    queue=[]
    queue.append([s_y, s_x, 0])
    reached[s_y][s_x]=0
    while len(queue)>0:
        v=queue.pop(0)
        if grid[v[0]+1][v[1]]=='.' and reached[v[0]+1][v[1]]==0 and [v[0]+1, v[1]]!=[s_y, s_x]:
            reached[v[0]+1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]+1, g_x, g_y):
                break
            else:
                queue.append([v[0]+1, v[1], v[2]+1])
        if grid[v[0]][v[1]+1]=='.' and reached[v[0]][v[1]+1]==0 and [v[0], v[1]+1]!=[s_y, s_x]:
            reached[v[0]][v[1]+1]=v[2]+1
            if isGoal(v[1]+1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]+1, v[2]+1])
        if grid[v[0]-1][v[1]]=='.' and reached[v[0]-1][v[1]]==0 and [v[0]-1, v[1]]!=[s_y, s_x]:
            reached[v[0]-1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]-1, g_x, g_y):
                break
            else:
                queue.append([v[0]-1, v[1], v[2]+1])
        if grid[v[0]][v[1]-1]=='.' and reached[v[0]][v[1]-1]==0 and [v[0], v[1]-1]!=[s_y, s_x]:
            reached[v[0]][v[1]-1]=v[2]+1
            if isGoal(v[1]-1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]-1, v[2]+1])

BFS_search(s_x, s_y, g_x, g_y)
# print(reached[g_y][g_x])
maximum_score = ((H+2)*(W+2)-number_of_black_grid)-(reached[g_x][g_y]+1)
print(maximum_score)

Submission status: Runtime Error

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = {(i,j):c for i in range(h) for j, c in enumerate(input())}

blacks = sum(c == '#' for c in maze.values())

def bfs(i, j):
    dq = deque()
    dq.appendleft((1, (i, j)))
    while dq:
        steps, (i, j) = dq.pop()
        if (i, j) == (h-1, w-1):
            return steps
        if maze.get((i, j), '#') == '#':
            continue
        maze[(i, j)] = '#'
        dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
        dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs)

print(h*w - bfs(0, 0) - blacks)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
dot_cnt = 0
for g in grid:
    dot_cnt += g.count('.')
sy = 0
sx = 0
gy = H - 1
gx = W - 1

deq = deque()
deq.append((0, 0))
grid[0][0] = 0

y_list = [-1, 1, 0, 0]
x_list = [0, 0, -1, 1]

while deq:
    y, x = deq.popleft()
    if y == gy and x == gx:
        break
    for i in range(len(y_list)):
        dy = y + y_list[i]
        dx = x + x_list[i]
        if dy < 0 or H <= dy or dx < 0 or W <= dx:
            continue
        if grid[dy][dx] == '.':
            deq.append((dy, dx))
            grid[dy][dx] = grid[y][x] + 1
print(dot_cnt - (grid[gy][gx] + 1))

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))


def BFS():  # 幅優先探索
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        visited[p[0]][p[1]] = True
        if p == (H, W):  # ゴールを訪問したら全部終わってなくても打ち切る
            return white_num - D[H][W]
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and D[e[0]][e[1]] == inf:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[None] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([None] * (W + 2))
s.append(["#"] * (W + 2))
D.append([None] * (W + 2))


def search(i, j):  # (i,j)からの最短経路長を求める再帰関数
    #print("({},{})".format(i, j))
    if i == H and j == W:
        return 0
    if s[i][j] == "#":
        D[i][j] = inf
        return inf
    if D[i][j] is not None:
        return D[i][j]
    D[i][j] = inf
    D[i][j] = min(search(i - 1, j), search(i, j - 1),
                  search(i, j + 1), search(i + 1, j)) + 1
    return D[i][j]


white_min = search(1, 1) + 1
if white_min == inf:
    print(-1)
else:
    print(white_num - white_min)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[None] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([None] * (W + 2))
s.append(["#"] * (W + 2))
D.append([None] * (W + 2))


def search(i, j):  # (i,j)からの最短経路長を求める再帰関数
    #print("({},{})".format(i, j))
    if i == H and j == W:
        return 0
    if s[i][j] == "#":
        return inf
    if D[i][j] is not None:
        return D[i][j]
    D[i][j] = inf
    D[i][j] = min(search(i - 1, j), search(i, j - 1),
                  search(i, j + 1), search(i + 1, j)) + 1
    return D[i][j]


white_min = search(1, 1) + 1
if white_min == inf:
    print(-1)
else:
    print(white_num - white_min)

Submission status: Runtime Error

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

S = [list(input()) for _ in range(W)]

def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []
        queue2 = []
        
        queue.insert(0, (sx, sy))
        queue2.insert(0, (sx, sy))
        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()
            queue2.insert(0, (x, y))
            
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                
                if (nx, ny) == (gx, gy):
                    answer = distance[x][y] + 1
                    if answer <= distance[gx][gy]:
                        distance[gx][gy] = answer
                
                elif (nx, ny) in queue2:
                    answer = distance[x][y] + 1
                    if answer <= distance[nx][ny]:
                        queue.insert(0, (nx, ny))
                        distance[nx][ny] = answer
                
                elif (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#'):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
                    
        if distance[gx][gy] == INF:
            distance[gx][gy] = -1
        return distance[gx][gy]
    
    return bfs()


maze = S
sx, sy = 0, 0 # スタート地点の座標
gx, gy = H-1, W-1 # ゴール地点の座標
root = clear_maze(sx, sy, gx, gy, maze)

if root == -1:
    print(root)
    sys.exit()
    
block = 0
for i in S:
    block += i.count("#")

print(H*W - (root + 1) - block)

Submission status: Runtime Error

Solution code:
from collections import deque
h, w =map(int, input().split())
s = [input() for i in range(h)]
s_x, s_y = 0, 0
##ある場所を塗る。その上でBFS。最大値を求める。
#最短経路で辿り着く時、塗りつぶす手は最大になる。
#最短経路の時は、通るますが考えうる中で一番少ないからねえ。そりゃそうか。
max = 0
c = [[0] * w for i in range(h)]
#cを定義する時は、横に並べてからそれを縦に並べる。つまり、列数を指定してから、その外で
#行数を指定する。ただ、要素にアクセスするときは、c[行番号][列番号]
#外側ほど、左側の要素になる？
def BFS():
    q = deque()
    q.append((s_x, s_y))

    while len(q) > 0:
        y, x = q.popleft()
        if y == h - 1 and x == w - 1:
            return c[y][x]
        if x < w - 1:
            if s[y][x+1] == '.' and c[y][x+1] == 0:
                q.append((y, x+1))
                c[y][x+1] = c[y][x] + 1
        if x > 0:
            if s[y][x-1] == '.' and c[y][x-1] == 0:
                q.append((y, x-1))
                c[y][x-1] = c[y][x] + 1
        if y < h - 1:
            if s[y+1][x] == '.' and c[y+1][x] == 0:
                q.append((y+1, x))
                c[y+1][x] = c[y][x] + 1
        if y > 0:
            if s[y-1][x] == '.' and c[y-1][x] == 0:
                q.append((y-1, x))
                c[y-1][x] = c[y][x] + 1

area = h*w
blunk_num_origin = 0
for ch1 in s:
    for ch2 in ch1:
        if ch2 == '#':
            blunk_num_origin += 1

min_grid = BFS()
sol = area-blunk_num_origin-2-(min_grid-1)
#print(area,min_grid,blunk_num_origin)
print(sol)

Submission status: Runtime Error

Solution code:
from collections import deque
h, w =map(int, input().split())
s = [input() for i in range(h)]
s_x, s_y = 0, 0
##ある場所を塗る。その上でBFS。最大値を求める。
#最短経路で辿り着く時、塗りつぶす手は最大になる。
#最短経路の時は、通るますが考えうる中で一番少ないからねえ。そりゃそうか。
max = 0
c = [[0] * w for i in range(h)]
#cを定義する時は、横に並べてからそれを縦に並べる。つまり、列数を指定してから、その外で
#行数を指定する。ただ、要素にアクセスするときは、c[行番号][列番号]
#外側ほど、左側の要素になる？
def BFS():
    q = deque()
    q.append((s_x, s_y))

    while len(q) > 0:
        y, x = q.popleft()
        if y == h - 1 and x == w - 1:
            return c[y][x]
        if x < w - 1:
            if s[y][x+1] == '.' and c[y][x+1] == 0:
                q.append((y, x+1))
                c[y][x+1] = c[y][x] + 1
        if x > 0:
            if s[y][x-1] == '.' and c[y][x-1] == 0:
                q.append((y, x-1))
                c[y][x-1] = c[y][x] + 1
        if y < h - 1:
            if s[y+1][x] == '.' and c[y+1][x] == 0:
                q.append((y+1, x))
                c[y+1][x] = c[y][x] + 1
        if y > 0:
            if s[y-1][x] == '.' and c[y-1][x] == 0:
                q.append((y-1, x))
                c[y-1][x] = c[y][x] + 1

area = h*w
blunk_num_origin = 0
for ch1 in s:
    for ch2 in ch1:
        if ch2 == '#':
            blunk_num_origin += 1

min_grid = BFS()
sol = area-blunk_num_origin-2-(min_grid-1)
print(area,min_grid,blunk_num_origin)
print(sol)

Submission status: Runtime Error

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

S = [list(input()) for _ in range(W)]

def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

        if distance[gx][gy] == INF:
            distance[gx][gy] = -1
        return distance[gx][gy]
    
    return bfs()


maze = S
sx, sy = 0, 0 # スタート地点の座標
gx, gy = H-1, W-1 # ゴール地点の座標
root = clear_maze(sx, sy, gx, gy, maze)

if root == -1:
    print(root)
    sys.exit()
    
block = 0
for i in S:
    block += i.count("#")

print(H*W - (root + 1) - block)

Submission status: Runtime Error

Solution code:

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

S = [list(input()) for _ in range(W)]

def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

        if distance[gx][gy] == INF:
            distance[gx][gy] = -1
        return distance[gx][gy]
    
    return bfs()


maze = S
sx, sy = 0, 0 # スタート地点の座標
gx, gy = H-1, W-1 # ゴール地点の座標
root = clear_maze(sx, sy, gx, gy, maze)

block = 0
for i in S:
    block += i.count("#")

print(H*W - root + 1 - block)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[[] for j in range(h)]
t=[[0]*w for k in range(h)]
t[0][0]=1
q=0
u=[]
for i in range(h):
    s[i]+=list(input())
    q+=s[i].count("#")
u.append((0,0))
while t[h-1][w-1]==0:
    (x,y)=u[0]
    if x!=h-1:
        if t[x+1][y]==0 and s[x+1][y]==".":
            t[x+1][y]=t[x][y]+1
            u.append((x+1,y))
    if y!=w-1:        
        if t[x][y+1]==0 and s[x][y+1]==".":
            t[x][y+1]=t[x][y]+1
            u.append((x,y+1))
    if x!=0:        
        if t[x-1][y]==0 and s[x-1][y]==".":
            t[x-1][y]=t[x][y]+1
            u.append((x-1,y))
    if y!=0:        
        if t[x][y-1]==0 and s[x][y-1]==".":
            t[x][y-1]=t[x][y]+1
            u.append((x,y-1))
    u.pop(0)    
print((h*w-t[h-1][w-1])-q)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**8)

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

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[-1]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
Dis[0][0] = 0
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and (Dis[ny][nx] ==-1):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**8)

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

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[0]*W for i in range(H)]
X =[1, 0]
Y =[0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(2):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**8)

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

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[0]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

from collections import deque
H, W = map(int, input().split()) 
S = [list(input()) for i in range(H)]

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

Dis =[[0]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

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

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

Dis =[[0]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

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

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

Dis =[[0]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import deque
H, W = map(int, input().split()) 
S = [list(input()) for i in range(R)]

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

Dis =[[0]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

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

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

Dis =[[0]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
cell = []
for _ in range(h):
    temp = input()
    cell.append(temp[:-1])

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

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

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

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    # n = 5
    # a = [6, 9, 4, 2, 11]

    max_a = max(a)
    max_half = max_a / 2

    best_a_j = a[0] if a[0] != max_a else a[1]
    min_d = max_half
    for a_j in a:
        if a_j == max_a:
            continue

        d = abs(a_j - max_half)
        if d < min_d:
            best_a_j = a_j
            min_d = d

    print(max_a, best_a_j)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

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

Submission status: Runtime Error

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

from collections import Counter

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

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


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