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:
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))







H,W=map(int,input().split())
black=0
field=[["#"]*(W+2)]
for i in range(H):
    field.append(["#"] + list(input()) + ["#"])

field.append(["#"]*(W+2))

adj=[[float("inf")]*W*H for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        if(field[i+1][j+1]=="#"):
            black+=1
            continue
        if(field[i+1][j+2]=="."):
            adj[W*i+j][W*i+j+1]=1
            adj[W*i+j+1][W*i+j]=1
        if(field[i+1][j]=="."):
            adj[W*i+j][W*i+j-1]=1
            adj[W*i+j-1][W*i+j]=1
        if(field[i][j+1]=="."):
            adj[W*i+j][W*(i-1)+j]=1
            adj[W*(i-1)+j][W*i+j]=1
        if(field[i+2][j+1]=="."):
            adj[W*i+j][W*(i+1)+j]=1
            adj[W*(i+1)+j][W*i+j]=1

d=Dijkstra()
kyori=d.dijkstra(adj,0)[-1]
if(kyori==-1):
    print(-1)
else:
    print(H*W-black-kyori-1)

Submission status: Wrong Answer

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

# 元々の黒マスの数を数える
black = 0
for g in G:
    black += g.count("#")

# コスト管理
C = [[-1] * W for i in range(H)]
C[0][0] = 0

# queue準備
que = deque()
que.append((0, 0))

# BFS
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        # 例外条件
        if not 0 <= nh + dh < H:
            continue
        if not 0 <= nw + dw < W:
            continue
        if G[nh + dh][nw + dw] == "#":
            continue
        if C[nh + dh][nw + dw] > 0:
            continue

        C[nh + dh][nw + dw] = C[nh][nw] + 1
        que.appendleft((nh + dh, nw + dw))

print(H * W - C[H - 1][W - 1] - black - 1)

Submission status: Wrong Answer

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

black = 0
for g in G:
    black += g.count("#")


que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

visited = set()
while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    visited.add((nw, nw))
    if G[H - 1][W - 1] != ".":
        print(H * W - black - int(G[H - 1][W - 1]) - 1)
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == "." and (nh + dh, nw + dw) not in visited:
                que.appendleft((nh + dh, nw + dw, cost + 1))
else:
    print(-1)

Submission status: Wrong Answer

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


ANS=0
for i in range(H):
    ANS+=MAP[i].count(".")

from collections import deque

QUE = deque()
QUE.append((0,0))
MAP[0][0]=0

while QUE:
    (x,y)=QUE.pop()

    for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if i<0 or j<0 or i>=H or j>=W:
            continue
        if MAP[i][j]==".":
            MAP[i][j]=MAP[x][y]+1
            QUE.append((i,j))
            
        
if MAP[H-1][W-1]==".":
    print(-1)
else:
    print(ANS-MAP[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
def ABC088D():
    H, W = map(int, input().split())
    s = [list(input()) for i in range(H)]
    visited = [[False for i in range(W)] for i in range(H)]
    black_cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                visited[i][j] = True
                black_cnt += 1
    will_visit = [[0, 0, 0]]
    def sarch(i, j, dist):
        visited[i][j] = True
        if 0 <= i - 1:
            if not visited[i - 1][j]:
                will_visit.append([i - 1, j, dist + 1])
        if 0 <= j - 1:
            if not visited[i][j - 1]:
                will_visit.append([i, j - 1, dist + 1])
        if j + 1 < W:
            if not visited[i][j + 1]:
                will_visit.append([i, j + 1, dist + 1])
        if i + 1 < H:
            if not visited[i + 1][j]:
                will_visit.append([i + 1, j, dist + 1])

    key = 0
    next = 0
    while len(will_visit) > next:
        #print(will_visit)
        next_i = will_visit[next][0]
        next_j = will_visit[next][1]
        next_dist = will_visit[next][2]
        if not visited[next_i][next_j]:
            if next_i == H - 1 and next_j == W - 1:
                key = next_dist
                break
            sarch(next_i, next_j, next_dist)
        if key != 0:
            break
        next += 1
    key += 1
    print(H * W - key - black_cnt)
ABC088D()

Submission status: Wrong Answer

Solution code:
def ABC088D():
    H, W = map(int, input().split())
    s = [list(input()) for i in range(H)]
    visited = [[False for i in range(W)] for i in range(H)]
    black_cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                visited[i][j] = True
                black_cnt += 1
    will_visit = [[0, 0, 0]]
    def sarch(i, j, dist):
        visited[i][j] = True
        if 0 <= i - 1:
            if not visited[i - 1][j]:
                will_visit.append([i - 1, j, dist + 1])
        if 0 <= j - 1:
            if not visited[i][j - 1]:
                will_visit.append([i, j - 1, dist + 1])
        if j + 1 < W:
            if not visited[i][j + 1]:
                will_visit.append([i, j + 1, dist + 1])
            if i == H - 1 and j + 1 == W - 1:
                return 0
        if i + 1 < H:
            if not visited[i + 1][j]:
                will_visit.append([i + 1, j, dist + 1])
            if i + 1 == H - 1 and j == W - 1:
                return 0

    key = 0
    next = 0
    while len(will_visit) > next:
        #print(will_visit)
        next_i = will_visit[next][0]
        next_j = will_visit[next][1]
        next_dist = will_visit[next][2]
        if not visited[next_i][next_j]:
            if next_i == H - 1 and next_j == W - 1:
                key = next_dist
                break
            sarch(next_i, next_j, next_dist)
        if key != 0:
            break
        next += 1
    key += 1
    print(H * W - key - black_cnt)
ABC088D()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
H, W = map(int, input().split())
s = [input() for _ in range(H)]
black = sum(x == '#' for row in s for x in row)
INF = 10 ** 9
sp = [[INF] * W for _ in range(H)]
sp[0][0] = 0
q = [(0, 0, 0)]
while q:
    dist, prev_x, prev_y = heappop(q)
    for dx, dy in zip([1, 0, -1, 0], [0, -1, 0, 1]):
        x = prev_x + dx
        y = prev_y + dy
        if (0 <= x < W and 0 <= y < H
                and s[y][x] == '.' and dist + 1 < sp[y][x]):
            sp[y][x] = dist + 1
            heappush(q, (dist + 1, x, y))

print(H * W - black - sp[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
black = 0
ma = []
maa = []
go = [[0, 0]]
for i in range(h):
    ma.append(list(input()))
    black += ma[i].count("#")
    maa.append([0] * w)
maa[0][0] = 1
while go != []:
    k = go.pop()
    if k[0] == h - 1 and k[1] == w - 1:
        print(h * w - black - maa[h - 1][w - 1])
        break
    if k[0] != 0:  # up
        if ma[k[0] - 1][k[1]] == "." and maa[k[0] - 1][k[1]] == 0:
            maa[k[0] - 1][k[1]] = maa[k[0]][k[1]] + 1
            go.append([k[0] - 1, k[1]])
    if k[0] != h-1:  # down
        if ma[k[0] + 1][k[1]] == "." and maa[k[0] + 1][k[1]] == 0:
            maa[k[0] + 1][k[1]] = maa[k[0]][k[1]] + 1
            go.append([k[0] + 1, k[1]])
    if k[1] != 0:  # left
        if ma[k[0]][k[1]-1] == "." and maa[k[0]][k[1]-1] == 0:
            maa[k[0]][k[1]-1] = maa[k[0]][k[1]] + 1
            go.append([k[0], k[1]-1])
    if k[1] != w-1:  # right
        if ma[k[0]][k[1]+1] == "." and maa[k[0]][k[1]+1] == 0:
            maa[k[0]][k[1]+1] = maa[k[0]][k[1]] + 1
            go.append([k[0], k[1] + 1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = [['#']*(W+2)]
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['#'] + li + ['#'])
maze.append(['#']*(W+2))



def check(x,y,n):
	if 1 <= x < W+1 and 1 <= y < H+1:
		if x == W-1 and y == H-1:
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return

q = queue.Queue()
q.put([1,1,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Submission status: Wrong Answer

Solution code:
R, C = list(map(int, input().split()))
sy, sx = 2, 2
gy, gx = R, C

meiro = ["#" + input() + "#" for _ in range(R)]
meiro = ["#"*(C+2)] + meiro + ["#"*(C+2)]

kyori = [[int(0) for x in range(C+2)] for _ in range(R+2)]
kyori[sy-1][sx-1] = 0

visited = [[sy-1,sx-1]]
que = [[sy-1,sx-1]]

while True:
    x = que[0][1]
    y = que[0][0]
    que.pop(0)
    try:
        if meiro[y][x+1] == "." and [y,x+1] not in visited:
            que.append([y,x+1])
            visited.append([y,x+1])
            kyori[y][x+1] = kyori[y][x] + 1
        if meiro[y+1][x] == "." and [y+1,x] not in visited:
            que.append([y+1,x])
            visited.append([y+1,x])
            kyori[y+1][x] = kyori[y][x] + 1
        if meiro[y][x-1] == "." and [y,x-1] not in visited:
            que.append([y,x-1])
            visited.append([y,x-1])
            kyori[y][x-1] = kyori[y][x] + 1
        if meiro[y-1][x] == "." and [y-1,x] not in visited:
            que.append([y-1,x])
            visited.append([y-1,x])
            kyori[y-1][x] = kyori[y][x] + 1
    except:
        IndexError
    if que == []:
        break

t = 0
for k in range(1,R+1):
    t += meiro[k].count("#")-2

print(R*C-kyori[R][C]-t-1)

Submission status: Wrong Answer

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

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

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[[] for _ in range(W)] for _ in range(H)]
    routes = [(0, 0)] 
    visited[0][0] = True

    hop_count = 0 
    while len(routes) > 0:
        x, y = routes.pop(0)
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '#' or visited[cy][cx]:
                continue
            if cx == W-1 and cy == H-1: 
                return sum([line.count('.')for line in c]) - len(dist[y][x]) - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] += dist[y][x] + [(x, y)] 
        print(routes)
    return -1

print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque
from itertools import product

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

dist = [[float('inf') for _ in range(W)] for _ in range(H)]
mx = [1, 0, -1, 0]
my = [0, 1, 0, -1]


def bfs():
    sx, sy = 0, 0
    gx, gy = W - 1, H - 1

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

    while que:
        x, y = que.popleft()
        if x == gx and y == gy:
            break

        for dx, dy in zip(mx, my):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H:
                if maze[ny][nx] != '#' and dist[ny][nx] == float('inf'):
                    que.append((nx, ny))
                    dist[ny][nx] = dist[y][x] + 1

    return dist


# BFSで最短路探索
res = bfs()

if res[H - 1][W - 1] == float('inf'):
    ans = -1
else:
    # 通ることができないマスで白色のマスは、黒色に変えることができる
    ans = 0
    for i, j in product(range(H), range(W)):
        if res[i][j] == float('inf') and maze[i][j] == '.':
            ans += 1

    # 同じ距離のマスは2つ以上あれば、黒色に変えることができる
    res = [x for l in res for x in l]
    for k, v in Counter(res).items():
        if k == float('inf'):
            continue
        ans += v - 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque
from itertools import product

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

dist = [[float('inf') for _ in range(W)] for _ in range(H)]
mx = [1, 0, -1, 0]
my = [0, 1, 0, -1]


def bfs():
    sx, sy = 0, 0
    gx, gy = W - 1, H - 1

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

    while que:
        x, y = que.popleft()
        if x == gx and y == gy:
            break

        for dx, dy in zip(mx, my):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H:
                if maze[ny][nx] != '#' and dist[ny][nx] == float('inf'):
                    que.append((nx, ny))
                    dist[ny][nx] = dist[y][x] + 1

    return dist


# BFSで最短路探索
res = bfs()

# 通ることができないマスで白色のマスは、黒色に変えることができる
ans = 0
for i, j in product(range(H), range(W)):
    if res[i][j] == float('inf') and maze[i][j] == '.':
        ans += 1

# 同じ距離のマスは2つ以上あれば、黒色に変えることができる
res = [item for sublist in res for item in sublist]
for k, v in Counter(res).items():
    if k == float('inf'):
        continue
    ans += v - 1

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
s = []
black = 0
for i in range(H):
    s.append(input())
    black += s[i].count('#')

# re = max(-1, H * W - (H + W - 1) - black)

queue = [[0,0]]
check = [[0,0]]
root = 0
hCurrent, wCurrent = 0, 0
while True:
    root += 1
#    print(queue)
    if hCurrent == H - 1 and wCurrent == W - 1:
        break
    if len(queue) == 0:
        root = -1
        break

    hCurrent, wCurrent = queue[0]
    queue.pop(0)

    if hCurrent < H - 1:
        if s[hCurrent + 1][wCurrent] != "#" and [hCurrent + 1, wCurrent] not in check:
            queue.append([hCurrent + 1, wCurrent])
            check.append([hCurrent + 1, wCurrent])
    if wCurrent < W - 1:
        if s[hCurrent][wCurrent+1] != "#" and [hCurrent, wCurrent + 1] not in check:
            queue.append([hCurrent, wCurrent + 1])
            check.append([hCurrent, wCurrent + 1])
    if hCurrent > 0:
        if s[hCurrent - 1][wCurrent] != "#" and [hCurrent - 1, wCurrent] not in check:
            queue.append([hCurrent - 1, wCurrent])
            check.append([hCurrent - 1, wCurrent])
    if wCurrent > 0:
        if s[hCurrent][wCurrent - 1] != "#" and [hCurrent, wCurrent - 1] not in check:
            queue.append([hCurrent, wCurrent-1])
            check.append([hCurrent, wCurrent-1])

if root == -1:
    re = -1
else:
    re = max(-1, H * W - (H + W - 1) - black)
    #re = H * W - black - root

print(re)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
s = []
black = 0
for i in range(H):
    s.append(input())
    black += s[i].count('#')

# re = max(-1, H * W - (H + W - 1) - black)

queue = [[0,0]]
check = [[0,0]]
root = 0
hCurrent, wCurrent = 0, 0
while True:
    root += 1
    print(queue)
    if hCurrent == H - 1 and wCurrent == W - 1:
        break
    if len(queue) == 0:
        root = -1
        break

    hCurrent, wCurrent = queue[0]
    queue.pop(0)

    if hCurrent < H - 1:
        if s[hCurrent + 1][wCurrent] != "#" and [hCurrent + 1, wCurrent] not in check:
            queue.append([hCurrent + 1, wCurrent])
            check.append([hCurrent + 1, wCurrent])
    if wCurrent < W - 1:
        if s[hCurrent][wCurrent+1] != "#" and [hCurrent, wCurrent + 1] not in check:
            queue.append([hCurrent, wCurrent + 1])
            check.append([hCurrent, wCurrent + 1])
    if hCurrent > 0:
        if s[hCurrent - 1][wCurrent] != "#" and [hCurrent - 1, wCurrent] not in check:
            queue.append([hCurrent - 1, wCurrent])
            check.append([hCurrent - 1, wCurrent])
    if wCurrent > 0:
        if s[hCurrent][wCurrent - 1] != "#" and [hCurrent, wCurrent - 1] not in check:
            queue.append([hCurrent, wCurrent-1])
            check.append([hCurrent, wCurrent-1])

if root == -1:
    re = -1
else:
    re = max(-1, H * W - (H + W - 1) - black)
    #re = H * W - black - root

print(re)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
s = []
black = 0
for i in range(H):
    s.append(input())
    black += s[i].count('#')

re = max(-1, H * W - (H + W - 1) - black)

print(re)

Submission status: Wrong Answer

Solution code:
class BFS():
    def __init__(self, H, W, maze):
        self.H = H
        self.W = W
        self.maze = maze
        self.distance = [[0 for i in range(self.W)] for j in range(self.H)]
        self.sx = 0
        self.sy = 0
        self.gx = W-1
        self.gy = H-1

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

        self.distance[self.sx][self.sy] = 0

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

            if x == self.gx and y == self.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 < self.W and 0 <= ny and ny < self.H and self.maze[ny][nx] != '#' and self.distance[ny][nx] == 0):
                    queue.insert(0, (nx, ny))
                    self.distance[ny][nx] = self.distance[y][x] + 1
        return self.distance[self.gy][self.gx]

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

bfs=BFS(H, W, sw)
distance=bfs.bfs()

print(distance)

init_white=0
for i in range(H):
    init_white+=sw[i].count('.')
print(init_white-(distance+1) if distance!=0 else -1)

Submission status: Wrong Answer

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
        self.queue = deque([start])
        self.dist = [[-1]*W for i in range(H)]
        self.dist[start[0]][start[1]] = 0

    def min_step(self):
        while len(self.queue) > 0:
            p = self.queue.popleft()
            if p == self.goal:
                break
            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.dist[self.goal[0]][self.goal[1]]

M = Map_input()
maze = Maze_min(M.H, M.W, M.Map, (0, 0), (M.H-1, M.W-1))
black_num = (sum(list(map(sum, M.Map))))
print(M.H*M.W - maze.min_step() - black_num -1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    # g = defaultdict(list)
    # for i, r in enumerate(S):
    #     for j, c in enumerate(r):
    #         if c == '.':
    #             if i > 0 and j > 0:
    #                 g[(i, j)].append((i-1, j-1))
    #     # g[u].append((v, (a, b)))
    #     # g[v].append((u, (a, b)))

    def d(s):
        dist = defaultdict(lambda : sys.maxsize)
        q =[]
        dist[s] = 0
        heapq.heappush(q, (dist[s], s))
        while q:
            c, u = heapq.heappop(q)
            if dist[u] > c:
                continue
            i, j = u
            g = []            
            if i > 0 and S[i-1][j] == '.':
                g.append((i-1, j))

            if j > 0 and S[i][j-1] == '.':
                g.append((i, j-1))

            if i < H-1 and S[i+1][j] == '.':
                g.append((i+1, j))

            if j < W-1 and S[i][j+1] == '.':
                g.append((i, j+1))
            
            for v in g:
                alt = dist[u] + 1
                if dist[v] > alt:
                    dist[v] = alt
                    heapq.heappush(q, (alt, v))
        return dist

    dist = d((0, 0))[(H-1, W-1)]
    return (H * W - sum(map(lambda x: x.count('#'), reduce(add, S)))) - dist - 1


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]

    
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for i in range(H)]
flag = [[-1 for i in range(W)] for j in range(H)]
whites = sum(grid[i].count('.') for i in range(H))
#BFS
q = deque()
q.append([0,0])
flag[0][0] = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while q:
    v = q.popleft()
    for j in range(4):
        if 0 <= v[0] + dx[j] < H and 0 <= v[1] + dy[j] < W and grid[v[0]+dx[j]][v[1]+dy[j]] == '.' and flag[v[0]+dx[j]][v[1]+dy[j]] == -1:
            flag[v[0]+dx[j]][v[1]+dy[j]] = flag[v[0]][v[1]] + 1
            q.append([v[0]+dx[j], v[1]+dy[j]])
print(whites - flag[H-1][W-1] - 1)

Submission status: Wrong Answer

Solution code:
import numpy
import re
import math
from collections import deque, defaultdict


def main():
	"""
	テストコード実行
	:return:
	"""
	"""
	BFS(幅優先探索) スタックでの実装
	"""
	h, w = map(int, input().split())
	maze = [list(input()) for _ in range(h)]
	visited = [[-1] * w for _ in range(h)]
	queue = deque()
	queue.append((0, 0))
	visited[0][0] = 0
	dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	blk = 0
	for i in range(h):
		for j in range(w):
			if maze[i][j] is "#":
				blk += 1
	while queue:
		y, x = queue.popleft()
		if y == h - 1 and x == w - 1:
			print(h * w - blk - visited[y][x] - 1)
			exit()
		for dx, dy in dxy:
			if 0 <= y + dy < h and 0 <= x + dx < w and maze[y + dy][x + dx] is not "#" and visited[y + dy][x + dx] == -1:
				visited[y + dy][x + dx] = visited[y][x] + 1
				queue.append((y + dy, x + dx))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import queue

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

temp = [[-1 for j in range(W+2)]]
B = temp+[[] for i in range(H)]+temp

dot = 0
for i in range(1,H+1):
    S = input()
    B[i].append(-1)
    for s in S:
        if s==".":
            B[i].append(H*W)
            dot += 1
        else:
            B[i].append(-1)
    B[i].append(-1)
    
Q = queue.Queue()
Q.put((1,1))
B[1][1]=1

min_root = dot
isok = False
while(not Q.empty()):
    x,y = Q.get()
    L = [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]
    move = B[x][y]+1
    for dx,dy in L:
        if move < B[dx][dy]:
            if dy==H and dx==W: isok=True
            Q.put((dx,dy))
            B[dx][dy] = move
    #print(B)

if isok:
    print(dot-B[H][W])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import queue

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

temp = [[-1 for j in range(W+2)]]
B = temp+[[] for i in range(H)]+temp

dot = 0
for i in range(1,H+1):
    S = input()
    B[i].append(-1)
    for s in S:
        if s==".":
            B[i].append(H*W)
            dot += 1
        else:
            B[i].append(-1)
    B[i].append(-1)
    
Q = queue.Queue()
Q.put((1,1))
B[1][1]=1

min_root = dot
while(not Q.empty()):
    x,y = Q.get()
    L = [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]
    move = B[x][y]+1
    for dx,dy in L:
        if move < B[dx][dy]:
            Q.put((dx,dy))
            B[dx][dy] = move
    #print(B)
            
print(dot-B[H][W])

Submission status: Wrong Answer

Solution code:
import queue

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

temp = [[-1 for j in range(W+2)]]
B = temp+[[] for i in range(H)]+temp

dot = 0
for i in range(1,H+1):
    S = input()
    B[i].append(-1)
    for s in S:
        if s==".":
            B[i].append(H*W)
            dot += 1
        else:
            B[i].append(-1)
    B[i].append(-1)
    
Q = queue.Queue()
Q.put((1,1))
B[1][1]=1

min_root = dot
while(not Q.empty()):
    x,y = Q.get()
    L = [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]
    move = B[x][y]+1
    for dx,dy in L:
        if move < B[dx][dy]:
            Q.put((dx,dy))
            B[dx][dy] = move
    #print(B)
            
print(B,dot-B[H][W])

Submission status: Wrong Answer

Solution code:
import numpy
import re
import math
from collections import deque, defaultdict


def main():
	"""
	テストコード実行
	:return:
	"""
	"""
	BFS(幅優先探索) スタックでの実装
	"""
	h, w = map(int, input().split())
	maze = [list(input()) for _ in range(h)]
	block = 0
	for i in range(h):
		for j in range(w):
			if maze[i][j] is "#":
				block += 1
	visited = [[-1] * w for _ in range(h)] #幅探索で行くことができる道数
	dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	queue = deque()
	queue.append((0, 0))
	visited[0][0] = 0 # 最初のマス
	while queue:
		y, x = queue.popleft()
		if y == h - 1 and x == w - 1: break
		for dx, dy in dxy:
			if 0 <= y + dy < h and 0 <= x + dx < w and maze[y + dy][x + dx] != "#" and visited[y + dy][x + dx] == -1:
				queue.append((y + dy, x + dx))
				visited[y + dy][x + dx] = visited[y][x] + 1
	if visited[y + dy][x + dx] == -1:
		print("-1")
	else:
		print(h * w - block - visited[h - 1][w - 1] - 1)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import numpy
import re
import math
from collections import deque, defaultdict


def main():
	"""
	テストコード実行
	:return:
	"""
	"""
	BFS(幅優先探索) スタックでの実装
	"""
	h, w = map(int, input().split())
	maze = [list(input()) for _ in range(h)]
	block = 0
	for i in range(h):
		for j in range(w):
			if maze[i][j] is "#":
				block += 1
	visited = [[-1] * w for _ in range(h)] #幅探索で行くことができる道数
	dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	queue = deque()
	queue.append((0, 0))
	visited[0][0] = 1 # 最初のマス
	while queue:
		y, x = queue.popleft()
		if y == h - 1 and x == w - 1: break
		for dx, dy in dxy:
			if 0 <= y + dy < h and 0 <= x + dx < w and maze[y + dy][x + dx] != "#" and visited[y + dy][x + dx] == -1:
				queue.append((y + dy, x + dx))
				visited[y + dy][x + dx] = visited[y][x] + 1
	if visited[y + dy][x + dx] == -1:
		print("-1")
	else:
		print(h * w - block - visited[h - 1][w - 1])


if __name__ == '__main__':
	main()