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:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#"), destroy=False):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.destroy = destroy
        self.grid = grid
        self.parent = [[(-1,-1)] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        while next_set:
            p, t = next_set.popleft()
            h, w = p
            for dh, dw in self.move:
                q = (h + dh, w + dw)
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                #### (debug code) ######
                # self.debug(start, goal, q, t)
                ########################
                if q == goal:
                    return t + 1
                parent[q[0]][q[1]] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [[-1] * self.W for _ in range(self.H)]
        for h in range(self.H):
            for w in range(self.W):
                if self.parent[h][w] == -1:
                    cnt += 1
                    self.bfs(start=(h,w), save=True)
        return cnt

    def distance_list(self, start=(0,0), save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [[-1] * self.W for _ in range(self.H)]
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, 0
        parent[p[0]][p[1]] = -2
        dist[p[0]][p[1]] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            h, w = p
            for dh, dw in self.move:
                q = (h + dh, w + dw)
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                dist[q[0]][q[1]] = t + 1
                parent[q[0]][q[1]] = p
                next_set.append((q, t + 1))
        return dist

    def most_distant_point(self, start=(0, 0), save=False):
        """
        :param start:
        :return: start 地点から最も遠い点を ((h,w), 距離) として出力
        """
        res = (start, 0)
        temp = 0
        dist = self.distance_list(start, save=save)
        for h in range(self.H):
            for w in range(self.W):
                if dist[h][w] > temp:
                    temp = dist[h][w]
                    res = ((h, w), temp)
        return res

    def diameter(self, start=(0,0), save=False):
        """
        :return:　木の直系（最も離れた二頂点間の距離）を返す
        """
        p = self.most_distant_point(start, save=False)
        res = self.most_distant_point(start=p[0], save=save)
        return res[1]

    def diameter2(self):
        """
        :return:　連結ではない時に、最大の直系を返す
        """
        res = 0
        for h in range(self.H):
            for w in range(self.W):
                if self.grid[h][w] == self.road and self.parent[h][w] == -1:
                    temp = self.diameter(start=(h, w), save=False)
                    if temp > res:
                        res = temp
        return res

    def dfs(self, start=(0, 0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1。ループがある時は最短距離とは限らないため注意。
        """

        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        move2 = [[marshal.loads(marshal.dumps(self.move)) for _ in range(self.W)] for _ in range(self.H)]

        p, t = start, time
        parent[p[0]][p[1]] = -2
        while True:
            if move2[p[0]][p[1]]:
                h, w = p
                dh, dw = move2[p[0]][p[1]].pop()
                q = (h + dh, w + dw)
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                    continue
                if q == parent[p[0]][p[1]]:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if parent[q[0]][q[1]] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                #### (debug code) ######
                # self.debug(start, goal, q, t)
                # self.show_visited(start, goal, q, t, parent)
                ########################
                if q == goal:
                    """ ゴール時の処理"""
                    """"""""""""""""""""
                    return t + 1
                """ p から q への引継ぎ"""
                """"""""""""""""""""
                parent[q[0]][q[1]] = p
                p, t = q, t + 1
            else:
                if p == start and t == time:
                    break
                p_temp = p
                p, t = parent[p[0]][p[1]], t-1
                """ p から進める点がもう無い時の点 p における処理 """
                # parent[p_temp[0]][p_temp[1]] = -1
                # move2[p_temp[0]][p_temp[1]].extend(marshal.loads(marshal.dumps(self.move)))
                """"""""""""""""""""
                """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """
                """"""""""""""""""""
        return -1

    def dfs2(self, start=(0, 0), goal=-3, time=0):
        visited = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        res = 0
        def rec(p, past_p, t, visited, res):
            h, w = p
            visited[p[0]][p[1]] = 1
            for dh, dw in self.move:
                q = (h + dh, w + dw)
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if grid[q[0]][q[1]] == self.wall:
                    continue
                if q == past_p:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if visited[q[0]][q[1]] == 1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                """ (debug code) """
                # self.debug(start, goal, q, t)
                # self.show_visited(start, goal, q, t, visited)
                """"""""""""""""""""
                if q == goal:
                    """ ゴール時の処理"""
                    """"""""""""""""""""
                    return t+1
                res = max2(rec(q, p, t + 1, visited, res), t + 1)
            """ 帰り際の処置（壊した道を元に戻す等)"""
            # visited[p[0]][p[1]] = -1
            """"""""""""""""""""
            return res
        return rec(p, -1, t, visited, res)

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))

    def show_visited(self, start, goal, p, t, parent):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        for h in range(H):
            for w in range(W):
                if parent[h][w] != -1:
                    debug_grid[h][w] = "V"
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))

############################################################################################

from collections import deque
import sys
import marshal
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
cnt = 0
for h in range(H):
    grid.append(input().rstrip())
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)

g = Grid(H, W, grid, (road, wall), destroy=False)
res = g.bfs(start, goal, save=True)
if res == -1:
    print(-1)
else:
    print(cnt - res - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque 

R,W = map(int,input().split())
sy,sx = 1,1
gy,gx = R,W
C = [list(input()) for i in range(0,R,1)]

task_list = deque([])
ans = 0

siro = 0
for i in range(R):
    for j in range(W):
        if C[i][j]==".":
            siro += 1
def bfs(y,x,count):#関数にしない方がわかりやすいかも

    if x==gx-1 and y==gy-1:
        return True

    if x < 0 or  W <= x or y < 0 or R <= y:
        return False
    if C[y][x]=="#":
        return False#何もしない
    if C[y][x]==".":
        C[y][x]="#"
        task_list.append([y+1,x,count+1])
        task_list.append([y-1,x,count+1])
        task_list.append([y,x-1,count+1])
        task_list.append([y,x+1,count+1])
    

task_list.append([sy-1,sx-1,0])
while(len(task_list)):
    y,x,t = task_list.popleft()
    ans = t
    if bfs(y,x,t):
        break
print(siro-1-ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
vi=[ [-1 for _ in range(w)] for _ in range(h)]
st=deque()
st.append([0,0,1])
vi[0][0]=1
while st:
  h1,w1,i=st.popleft()
  d=[[0,1],[-1,0],[1,0],[0,-1]]
  for m in d:
    if h1+m[0]==h-1 and w1+m[1]==w-1:
      vi[h-1][w-1]=i+1
      st.clear()
    if 0<=h1+m[0]<h and 0<=w1+m[1]<w:
      if vi[h1+m[0]][w1+m[1]]==-1 and s[h1+m[0]][w1+m[1]]==".":
        st.append([h1+m[0],w1+m[1],i+1])
        vi[h1+m[0]][w1+m[1]]=i+1
print("".join(s).count(".")-vi[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import copy
h,w = map(int,input().split())
g = [[False]*(w+2) for _ in range(h+2)]
d = [[-1]*(w+2) for _ in range(h+2)]
ans = 0
for i in range(h):
    l = list(input())
    for j in range(w):
        if l[j] == ".":
            ans += 1
            g[i+1][j+1] = True
def f(i,j):
    return [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]
now = f(1,1)
d[1][1] = 0
nxt = []
cnt = 1
while now:
    for l in now:
        i,j = l[0],l[1]
        if d[i][j] == -1 and g[i][j]:
            d[i][j] = cnt
            for l2 in f(i,j):
                nxt.append(l2)
    cnt += 1
    now = copy.copy(nxt)
    nxt = []
print(ans-d[h][w]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    h,w = map(int,input().split())
    Map = []
    Visited = [[False for j in range(w)]for i in range(h)]
    DYDX = [[0,1],[1,0],[0,-1],[-1,0]]
    white = 0
    black = 0
    limit = 0
    for i in range(h):
        tmp = [i for i in input()]
        white += tmp.count('.')
        black += tmp.count('#')
        #print(tmp)
        Map.append(tmp)
    q = deque()
    q.append((0,0,0))
    ans = 0
    while q:
        if limit>=10**5:
            print('-1')
            exit()
        y,x,cnt = q.popleft()
        if y<0 or y>=h or x<0 or x>=w:
            continue
        if Visited[y][x]:
            continue
        if Map[y][x]=='#':
            continue
        if y==h-1 and x==w-1:
            ans = cnt
            break
        Visited[y][x] = True
        cnt += 1
        limit += 1
        for dy,dx in DYDX:
            q.append((y+dy,x+dx,cnt))
    
    print(white-ans-1) 

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from collections import deque
def cango(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
    
q = deque([(-1,-1,0,0,0)]) 
been = [[False]*W for _ in range(H)]

while q:
    x_old,y_old,x_now,y_now,time = q.popleft()
    been[x_now][y_now]=True
    cand = cango(x_now,y_now)
    
    if x_now==H-1 and y_now==W-1:
        break
    
    for x_new,y_new in cand:
        if not been[x_new][y_new] and s[x_new][y_new]==".":
            q.append((x_now,y_now,x_new,y_new,time+1))

print( sum(ss.count(".") for ss in s)-time-1 )

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def get_adj(pos):
    ans = []
    for v in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        adj = (pos[0] + v[0], pos[1] + v[1])
        if adj[0] >= 0 and adj[0] < H and adj[1] >= 0 and adj[1] < W:
            ans.append(adj)
    return ans

start = (0, 0)
goal = (H-1, W-1)

q = deque()
q.append((start, 1))
visited = {}

while q:
    pos, dist = q.popleft()
    if field[pos[0]][pos[1]] == '#':
        continue
    if pos in visited:
        continue
    visited[pos] = dist
    if pos == goal:
        break
    for adj in get_adj(pos):
        q.append((adj, dist+1))

count_walls = sum([row.count('#') for row in field])

print(H*W-dist-count_walls)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def get_adj(pos):
    ans = []
    for v in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        adj = (pos[0] + v[0], pos[1] + v[1])
        if adj[0] >= 0 and adj[0] < H and adj[1] >= 0 and adj[1] < W:
            ans.append(adj)
    return ans



start = (0, 0)
goal = (H-1, W-1)

q = deque()
q.append((start, 1))
visited = {}

while q:
    pos, dist = q.popleft()
    if pos in visited:
        continue
    visited[pos] = dist
    if pos == goal:
        break
    for adj in get_adj(pos):
        q.append((adj, dist+1))

count_walls = sum([row.count('#') for row in field])

print(H*W-dist-count_walls)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque
import sys

sys.setrecursionlimit(50000)

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

C = {'.': 0, '#': 0}
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            C['.'] += 1
        else:
            C['#'] += 1


direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = deque([(0, 0, 1)])
visited = set()
ans = float('inf')
def bfs(x, y, cnt):
    global ans
    if x == H-1 and y == W-1:
        ans = min(ans, cnt)
    for dx, dy in direction:
        nx = x + dx
        ny = y + dy
        if 0 <= nx <= H-1 and 0 <= ny <= W-1:
            if not (nx, ny) in visited:
                queue.append((nx, ny, cnt+1))
                visited.add((nx, ny))

while queue:
    x, y, cnt = queue.popleft()
    bfs(x, y, cnt)

if ans == float('inf'):
    print(-1)
else:
    print(C['.'] - ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
S = [[] for _ in range(h)]
cs = 0
for i in range(h):
    S[i] = list(input())
    cs += S[i].count('#')

direct = [[0,1],[0,-1],[1,0],[-1,0]]
ans = 0
# BFS
## 距離を初期化.
D = [[-1]*w for _ in range(h)]
D[0][0] = 0
## 現在地でキューを初期化.
que = deque([[0,0]])
## キューがなくなるまで探索を行う.
while que:
    ### キューを一つ取り出す.
    chi, cwi = que.pop()
    for (dh,dw) in direct:
        #### 迷路の範囲外なら探索しない.
        if not (0<=chi+dh<=h-1 and 0<=cwi+dw<=w-1): continue
        #### 探索済みや探索不可なところは探索しない.
        if D[chi+dh][cwi+dw]!=-1 or S[chi+dh][cwi+dw]=='#': continue
        #### 距離の計算.
        D[chi+dh][cwi+dw] = D[chi][cwi]+1
        #### 次に探索する場所の追加.
        que.appendleft([chi+dh, cwi+dw])
dist = D[-1][-1]
print(h*w-(dist+1)-cs)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int, input().split())
S = ["#"]*(W+2)
MAP=[]
MAP.append(S)
cnt = 0
for _ in range(H):
    tmp = ["#"]+list(input())+["#"]
    cnt += tmp.count(".")
    MAP.append(tmp)
MAP.append(S)

move=[[1,0],[-1,0],[0,1],[0,-1]]
start=[1,1]

cheak = [[-1]*(W+2) for _ in range(H+2)]
cheak[1][1] = 0

que = deque()
que.append(start)
while que:
    tmp = que.popleft()
    x = tmp[0]
    y = tmp[1]
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if MAP[nx][ny] == "." and cheak[nx][ny] == -1:
            que.append([nx,ny])
            cheak[nx][ny]=cheak[x][y]+1
if cheak[H][W] == 0:
    print(-1)
else:
    print(cnt-cheak[H][W]-1)#スタート地点も白くなくてはいけないので-1

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int, input().split())
S = ["#"]*(W+2)
MAP=[]
MAP.append(S)
cnt = 0
for _ in range(H):
    tmp = ["#"]+list(input())+["#"]
    cnt += tmp.count(".")
    MAP.append(tmp)
MAP.append(S)

move=[[1,0],[-1,0],[0,1],[0,-1]]
start=[1,1]

cheak = [[-1]*(W+2) for _ in range(H+2)]
cheak[1][1] = 0

que = deque()
que.append(start)
while que:
    tmp = que.popleft()
    x = tmp[0]
    y = tmp[1]
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if MAP[nx][ny] == "." and cheak[nx][ny] == -1:
            que.append([nx,ny])
            cheak[nx][ny]=cheak[x][y]+1
print(cnt-cheak[H][W]-1)#スタート地点も白くなくてはいけないので-1

Submission status: Wrong Answer

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

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_y_length)] for j in range(field_x_length)]
#	distance = [[INF]*field_y_length]*field_x_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

		return distance[gx][gy]
	return bfs()
print(white - clear_maze(0, 0, h-1, w-1, s) - 1)

Submission status: Wrong Answer

Solution code:
def MI(): return map(int, input().split())
from collections import deque
H,W=MI()
#Map=[[]*W for _ in range(H)]
Map=[]
INF=float('inf')
white=0
for _ in range(H):
  Map.append(list(input()))
def bfs():
  dx=[-1,0,1,0]
  dy=[0,-1,0,1]
  
  dist=[[INF]*W for _ in range(H)]
  dist[0][0]=0
  que=deque()
  que.append((0,(0,0)))

  while que:
    d,(x,y) =que.popleft()
    if x==H-1 and y==W-1:
      break
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='#':
          if dist[nx][ny]==INF:
            dist[nx][ny]=d+1
            que.append((d+1,(nx,ny)))
  return dist
res=bfs()  
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
ans=white-res[H-1][W-1]-1
if 0<ans<INF:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
def MI(): return map(int, input().split())
from collections import deque
H,W=MI()
#Map=[[]*W for _ in range(H)]
Map=[]
INF=float('inf')
white=0
for _ in range(H):
  Map.append(list(input()))
def bfs():
  dx=[-1,0,1,0]
  dy=[0,-1,0,1]
  
  dist=[[INF]*W for _ in range(H)]
  dist[0][0]=0
  que=deque([])
  que.append((0,(0,0)))

  while que:
    d,(x,y) =que.popleft()
    #if x==H-1 and y==W-1:
      #break
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='#':
          if dist[nx][ny]==INF:
            dist[nx][ny]=d+1
            que.append((d+1,(nx,ny)))
  return dist
res=bfs()  
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
ans=white-res[H-1][W-1]-1
if 0<ans<INF:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
def MI(): return map(int, input().split())
from collections import deque
H,W=MI()
#Map=[[]*W for _ in range(H)]
Map=[]
INF=float('inf')
white=0
for _ in range(H):
  Map.append(list(input()))
def bfs():
  dx=[-1,0,1,0]
  dy=[0,-1,0,1]
  
  dist=[[INF]*W for _ in range(H)]
  dist[0][0]=0
  que=deque([])
  que.append((0,(0,0)))

  while que:
    d,(x,y) =que.popleft()
    if x==H-1 and y==W-1:
      break
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='#':
          if dist[nx][ny]==INF:
            dist[nx][ny]=d+1
            que.append((d+1,(nx,ny)))
  return dist
res=bfs()  
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
ans=white-res[H-1][W-1]-1
if 0<ans<INF:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
def MI(): return map(int, input().split())
from collections import deque
H,W=MI()
#Map=[[]*W for _ in range(H)]
Map=[]
white=0
for _ in range(H):
  Map.append(list(input()))
def bfs():
  dx=[-1,0,1,0]
  dy=[0,-1,0,1]
  INF=float('inf')
  dist=[[INF]*W for _ in range(H)]
  dist[0][0]=0
  que=deque()
  que.append((0,(0,0)))

  while que:
    d,(x,y) =que.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='#':
          if dist[nx][ny]==INF:
            dist[nx][ny]=d+1
            que.append((d+1,(nx,ny)))
  return dist
res=bfs()  
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
ans=white-res[H-1][W-1]-1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
white = 0
maze = []
for _ in range(n):
  row = list(input())
  white += row.count(".")
  maze.append(row)
steps = [ [-1]*m for _ in range(n) ]
steps[0][0] = 0

q = deque([(0,0)])
while q:
  r,c = q.popleft()

  for x,y in [(1,0), (0,1), (-1,0), (0,-1)]:
    nr,nc = r+x,c+y
    if nr<0 or nc<0 or nr>=n or nc>=m: continue
    if steps[nr][nc] != -1: continue
    steps[nr][nc] = steps[r][c] + 1
    if nr==n-1 and nc==m-1:
      break
    else:
      q.append((nr,nc))

if steps[n-1][m-1] == -1:
  print(-1)
else:
  print( white - steps[n-1][m-1] - 1)

Submission status: Wrong Answer

Solution code:

h, w = map(int, input().split())
data = []
for _ in range(h):
    row = input()
    data.append(row)

all_black = 0
mark = [[0] * w for _ in range(h)]
short_step = [[9999] * w for _ in range(h)]
# print(data)
# print(mark)
# print(all_black)
for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

# print(data)
# print(mark)
# print(all_black)
step = 0


# res = 9999


def run(i, j):
    # print(i, j)
    global step
    # global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    if 0 <= i < h and 0 <= j < w:
        if i < h - 1 and j == w - 1:
            return
        step += 1
        mark[i][j] = 1
        if short_step[i][j] > step:
            short_step[i][j] = step
        # if i == h - 1 and j == w - 1:
        #     print(short_step[i][j])
        #     if res > step:
        #         res = step
        #         # print(res)
        #     step -= 1
        #     mark[i][j] = 0
        #     return

        if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
            # step += 1
            # mark[i + 1][j] = 1
            run(i + 1, j)
            # mark[i + 1][j] = 0
            # step -= 1

        if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
            # step += 1
            # mark[i][j + 1] = 1
            run(i, j + 1)
            # mark[i][j + 1] = 0
            # step -= 1

        if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
            # step += 1
            # mark[i - 1][j] = 1
            run(i - 1, j)
            # mark[i - 1][j] = 0
            # step -= 1

        if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
            #     step += 1
            # mark[i][j - 1] = 1
            run(i, j - 1)
            # mark[i][j - 1] = 0
            # step -= 1

        step -= 1
        mark[i][j] = 0

    if data[0][0] == '#' or data[h - 1][w - 1] == '#':
        print(-1)
    else:
        run(0, 0)
        # if res == 9999:
        #     print(-1)
        # else:
        if short_step[h - 1][w - 1] == 9999:
            print(-1)
        else:
            print(h * w - all_black - short_step[h - 1][w - 1])

Submission status: Wrong Answer

Solution code:
try:
    h, w = map(int, input().split())
    data = []
    for _ in range(h):
        row = input()
        data.append(row)

    all_black = 0
    mark = [[0] * w for _ in range(h)]
    short_step = [[9999] * w for _ in range(h)]
    # print(data)
    # print(mark)
    # print(all_black)
    for i in range(h):
        for j in range(w):
            if data[i][j] == '#':
                all_black += 1
                mark[i][j] = 1

    # print(data)
    # print(mark)
    # print(all_black)
    step = 0
    res = 9999


    def run(i, j):
        # print(i, j)
        global step
        global res
        # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
        #     return
        if i < h-1 and j == w-1:
            return
        step += 1
        mark[i][j] = 1
        if short_step[i][j] > step:
            short_step[i][j] = step
        if i == h - 1 and j == w - 1:
            # print(step)
            if res > step:
                res = step
                # print(res)
            step -= 1
            mark[i][j] = 0
            return

        if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
            # step += 1
            # mark[i + 1][j] = 1
            run(i + 1, j)
            # mark[i + 1][j] = 0
            # step -= 1

        if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
            # step += 1
            # mark[i][j + 1] = 1
            run(i, j + 1)
            # mark[i][j + 1] = 0
            # step -= 1

        if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
            # step += 1
            # mark[i - 1][j] = 1
            run(i - 1, j)
            # mark[i - 1][j] = 0
            # step -= 1

        if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
            #     step += 1
            # mark[i][j - 1] = 1
            run(i, j - 1)
            # mark[i][j - 1] = 0
            # step -= 1

        step -= 1
        mark[i][j] = 0


    run(0, 0)
    if res == 9999:
        print(-1)
    else:
        print(h * w - all_black - res)
except Exception as e:
    print(e)

Submission status: Wrong Answer

Solution code:

h, w = map(int, input().split())
data = []
for _ in range(h):
    row = input()
    data.append(row)

all_black = 0
mark = [[0] * w for _ in range(h)]
# print(data)
# print(mark)
# print(all_black)
for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

# print(data)
# print(mark)
# print(all_black)
step = 0
res = 99999999999999999999999999999999


def run(i, j):
    # print(i, j)
    global step
    global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    # step += 1
    if i == h - 1 and j == w - 1:
        # print(step)
        # print(step)
        # print(step)
        # print(step)
        if res > step:
            res = step
            # print(res)
        return
    # if i - 1 >= 0 and mark[i - 1][j] == 0:
    #     step += 1
    #     mark[i - 1][j] = 1
    #     run(i - 1, j)
    #     mark[i - 1][j] = 0
    #     step -= 1

    if i + 1 < h and mark[i + 1][j] == 0:
        step += 1
        mark[i + 1][j] = 1
        run(i + 1, j)
        mark[i + 1][j] = 0
        step -= 1

    # if j - 1 >= 0 and mark[i][j - 1] == 0:
    #     step += 1
    #     mark[i][j - 1] = 1
    #     run(i, j - 1)
    #     mark[i][j - 1] = 0
    #     step -= 1

    if j + 1 < w and mark[i][j + 1] == 0:
        step += 1
        mark[i][j + 1] = 1
        run(i, j + 1)
        mark[i][j + 1] = 0
        step -= 1
    # step -= 1

run(0, 0)
print(h * w - all_black - res - 1)