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: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
s = [list(input()) for x in range(H)]
d = [[None for y in range(W)] for x in range(H)]
q = []
white = 0
for x in range(H):
  for y in range(W):
    if s[x][y] == '.':
      white += 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append([0, 0, 0])

def Haba(x_now, y_now, d_now, s, d, q):
  s[x_now][y_now] = '#'
  d[x_now][y_now] = d_now
  for i in range(4):
    if 0 <= x_now + dx[i] and x_now + dx[i] < H and 0 <= y_now + dy[i] and y_now + dy[i] < W:
      if s[x_now + dx[i]][y_now + dy[i]] == '.':
        q.append([x_now+dx[i], y_now+dy[i], d_now + 1])
while(len(q) != 0):
  x_now, y_now, d_now = q.pop(0)
  Haba(x_now, y_now, d_now, s, d, q)
if d[H - 1][W - 1] is not None:
  ans = white - d[H - 1][W - 1]  - 1
else:
  ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x + dx, y + dy) for dx, dy in ((0, -1), (1, 0), (0, 1), (-1, 0))]
    return list(filter(lambda a: 0 <= a[0] < max_x and
                                 0 <= a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


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

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

p_grid = {(0, 0): 0, (H - 1, W - 1): -1}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    grid[here[0]][here[1]] = False
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        p_grid[a] = p_grid[here] + 1
    queue.extend(arounds)

if p_grid[H-1, W-1] == -1:
    print('-1')
else:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


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

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

p_grid = {(0, 0): 0, (H - 1, W - 1): -1}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    grid[here[0]][here[1]] = False
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        p_grid[a] = p_grid[here] + 1
    queue.extend(arounds)

if p_grid[H-1, W-1] == -1:
    print('-1')
else:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


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

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = []
for i in range(0, H):
    for j in range(0, W):
        if not grid[i][j]:
            black.append((i, j))

s_path = []
queue = deque([[(0, 0)]])
while not len(queue) == 0:
    path = queue.popleft()
    here = path[-1]
    if here == (H - 1, W - 1):
        s_path = path
        break;
    grid[here[0]][here[1]] = False
    arounds = get_arounds(here, grid, H, W)
    if len(arounds) == 0:
        continue;
    queue.extend(list(map(lambda a: path + [a], arounds)))
else:
    s_path = []

if len(s_path) == 0:
    print('-1')
else:
    print(H * W - len(s_path) - len(black))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


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

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = []
for i in range(0, H):
    for j in range(0, W):
        if not grid[i][j]:
            black.append((i, j))

s_path = []
queue = deque([[(0, 0)]])
while not len(queue) == 0:
    path = queue.popleft()
    here = path[-1]
    if here == (H - 1, W - 1):
        s_path = path
        break;
    grid[here[0]][here[1]] = False
    arounds = get_arounds(here, grid, H, W)
    queue.extend(list(map(lambda a: path + [a], arounds)))
else:
    s_path = []

if len(s_path) == 0:
    print('-1')
else:
    print(H * W - len(s_path) - len(black))

Submission status: Time Limit Exceeded

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

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

def get_arounds(x, y, max_x, max_y):
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y, arounds))

def find_path(point, path, ignore, H, W):
    x = point[0]
    y = point[1]
    arounds = get_arounds(x, y, H, W)
    targets = list(filter(lambda x: not x in ignore, arounds))

    if len(targets) == 0:
        return [(False, path, ignore)]
    else:
        return [(True, path + [target], ignore + arounds)
                for target in targets]


ignore = []
for i in range(0, H):
    for j in range(0, W):
        if not grid[i][j]:
            ignore.append((i, j))

paths = [(True, [(0, 0)], ignore)]
s_path = []
while any([p[0] for p in paths]):
    next_paths = []
    for p in filter(lambda p: p[0], paths):
        if p[1][-1] == (H - 1, W - 1):
            s_path = p[1]
            break

        next_paths.extend(find_path(p[1][-1], p[1], p[2], H, W))
    paths = next_paths

if len(s_path) == 0:
    print(-1)
else:
    print(H * W - len(s_path) - len(ignore))

Submission status: Time Limit Exceeded

Solution code:
import random
import numpy
import sys
import heapq
import copy

H,W = list(map(int, input().split(" ")))
S = []
for i in range(H):
  S.append(input())
class Node:
  def __init__(self,point,operation):
    self.point = point
    self.operation = operation
  def get_next_nodes(self):
    next_nodes = []
    if not(self.point[1]==0):#left
      if S[self.point[0]][self.point[1]-1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]-1))
        next_nodes.append(Node((self.point[0],self.point[1]-1),next_op))
    if not(self.point[1]==W-1):#right
      if S[self.point[0]][self.point[1]+1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]+1))
        next_nodes.append(Node((self.point[0],self.point[1]+1),next_op))
    if not(self.point[0]==0):#up
      if S[self.point[0]-1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]-1,self.point[1]))
        next_nodes.append(Node((self.point[0]-1,self.point[1]),next_op))
    if not(self.point[0]==H-1):#down
      if S[self.point[0]+1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]+1,self.point[1]))
        next_nodes.append(Node((self.point[0]+1,self.point[1]),next_op))
    return next_nodes
def distance(point):
  return abs((H-1)-point[0])+abs((W-1)-point[1])

q = []
checked = set()
ID = 0
heapq.heappush(q,(distance((0,0)),ID,Node((0,0),[(0,0)])))
while len(q):
  cost,looking_id,looking_node = heapq.heappop(q)
  if looking_node.point == (H-1,W-1):
    count=0
    for h in range(0,H):
      for w in range(0,W):
        if not((h,w) in looking_node.operation) and S[h][w]=='.':
          count+=1
    print(count)
    exit()
  checked.add(looking_node.point)
  next_nodes = looking_node.get_next_nodes()
  if ID>=100000:
    break
  for n in next_nodes:
    ID+=1
    if not(n.point in checked):
      heapq.heappush(q,(distance(n.point)+len(n.operation),ID,n))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import random
import numpy
import sys
import heapq
import copy

H,W = list(map(int, input().split(" ")))
S = []
for i in range(H):
  S.append(input())
class Node:
  def __init__(self,point,operation):
    self.point = point
    self.operation = operation
  def get_next_nodes(self):
    next_nodes = []
    if not(self.point[1]==0):#left
      if S[self.point[0]][self.point[1]-1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]-1))
        next_nodes.append(Node((self.point[0],self.point[1]-1),next_op))
    if not(self.point[1]==W-1):#right
      if S[self.point[0]][self.point[1]+1]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0],self.point[1]+1))
        next_nodes.append(Node((self.point[0],self.point[1]+1),next_op))
    if not(self.point[0]==0):#up
      if S[self.point[0]-1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]-1,self.point[1]))
        next_nodes.append(Node((self.point[0]-1,self.point[1]),next_op))
    if not(self.point[0]==H-1):#down
      if S[self.point[0]+1][self.point[1]]=='.':
        next_op = copy.deepcopy(self.operation)
        next_op.append((self.point[0]+1,self.point[1]))
        next_nodes.append(Node((self.point[0]+1,self.point[1]),next_op))
    return next_nodes
def distance(point):
  return abs((H-1)-point[0])+abs((W-1)-point[1])

q = []
checked = set()
ID = 0
heapq.heappush(q,(distance((0,0)),ID,Node((0,0),[(0,0)])))
while len(q):
  cost,looking_id,looking_node = heapq.heappop(q)
  if looking_node.point == (H-1,W-1):
    count=0
    for h in range(0,H):
      for w in range(0,W):
        if not((h,w) in looking_node.operation) and S[h][w]=='.':
          count+=1
    print(count)
    exit()
  checked.add(looking_node.point)
  next_nodes = looking_node.get_next_nodes()
  for n in next_nodes:
    ID+=1
    if not(n.point in checked):
      heapq.heappush(q,(distance(n.point)+len(n.operation),ID,n))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools
import itertools
import math
from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            visited[y][x] = True
            if S[y-1][x] != '#' and visited[y-1][x] == False:
                un.append((x, y-1))

            if S[y+1][x] != '#' and visited[y+1][x] == False:
                if y+1 == H and x == W:
                    return dist
                un.append((x, y+1))

            if S[y][x-1] != '#' and visited[y][x-1] == False:
                un.append((x-1, y))

            if S[y][x+1] != '#' and visited[y][x+1] == False:
                if y == H and x+1 == W:
                    return dist
                un.append((x+1, y))
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.append('#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools
import itertools
import math
from collections import deque

def bfs(H, W, S):
    visited = deque()
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            visited.append((x,y))
            if S[y-1][x] != '#' and (x, y-1) not in visited:
                un.append((x, y-1))

            if S[y+1][x] != '#' and (x, y+1) not in visited:
                if y+1 == H and x == W:
                    return dist
                un.append((x, y+1))

            if S[y][x-1] != '#' and (x-1, y) not in visited:
                un.append((x-1, y))

            if S[y][x+1] != '#' and (x+1, y) not in visited:
                if y == H and x+1 == W:
                    return dist
                un.append((x+1, y))
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = [list('#'+input()+'#') for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools
import itertools
import math
from collections import deque

def bfs(H, W, S):
    visited = deque()
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            visited.append((x,y))
            if S[y-1][x] != '#' and (x, y-1) not in visited:
                un.append((x, y-1))

            if S[y+1][x] != '#' and (x, y+1) not in visited:
                if y+1 == H and x == W:
                    return dist
                un.append((x, y+1))

            if S[y][x-1] != '#' and (x-1, y) not in visited:
                un.append((x-1, y))

            if S[y][x+1] != '#' and (x+1, y) not in visited:
                if y == H and x+1 == W:
                    return dist
                un.append((x+1, y))
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools
import itertools
import math
from collections import deque

def bfs(H, W, S):
    cost = [[0]*(W+2) for _ in range(H+2)]
    visited = deque([])
    unvisited = deque([(1,1)])
    cost[1][1] = 1
    while unvisited:
        now = unvisited.popleft()
        visited.append(now)
        if S[now[1]-1][now[0]] != '#' and (now[0], now[1]-1) not in visited:
            cost[now[1]-1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]-1))
        if S[now[1]+1][now[0]] != '#' and (now[0], now[1]+1) not in visited:
            if now[1]+1 == H and now[0] == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]+1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]+1))
        if S[now[1]][now[0]-1] != '#' and (now[0]-1, now[1]) not in visited:
            cost[now[1]][now[0]-1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]-1, now[1]))
        if S[now[1]][now[0]+1] != '#' and (now[0]+1, now[1]) not in visited:
            if now[1] == H and now[0]+1 == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]][now[0]+1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]+1, now[1]))
    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools
import itertools
import math

def bfs(H, W, S):
    cost = [[0]*(W+2) for _ in range(H+2)]
    visited = []
    unvisited = [(1,1)]
    cost[1][1] = 1
    while unvisited:
        now = unvisited[0]
        unvisited = unvisited[1:]
        visited.append(now)
        if S[now[1]-1][now[0]] != '#' and (now[0], now[1]-1) not in visited:
            cost[now[1]-1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]-1))
        if S[now[1]+1][now[0]] != '#' and (now[0], now[1]+1) not in visited:
            if now[1]+1 == H and now[0] == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]+1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]+1))
        if S[now[1]][now[0]-1] != '#' and (now[0]-1, now[1]) not in visited:
            cost[now[1]][now[0]-1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]-1, now[1]))
        if S[now[1]][now[0]+1] != '#' and (now[0]+1, now[1]) not in visited:
            if now[1] == H and now[0]+1 == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]][now[0]+1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]+1, now[1]))
    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(H,W,S):
    qu = deque([(0,0,1)])
    while(len(qu) != 0):
        p,q,r = qu.popleft()
        S[p][q] = '#'
        for d in [(-1,0), (0,-1), (1,0), (0,1)]:
            s = p+d[0]
            t = q+d[1]
            if (s < 0 or t < 0 or s >= H or t >= W):
                continue
            if (s == (H-1) and t == (W-1) and S[s][t] == '.'):
                return r+1
            if S[s][t] == '.':
                qu.append((s,t,r+1))
    return -1

H, W = list(map(int, input().split()))
S = []

cnt = 0
for i in range(H):
    a = input()
    tmp = []
    for i in a:
        if (i == '.'):
            cnt += 1
        tmp.append(i)
    S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
    print(cnt - step)
else:
    print(step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(H,W,S):
    qu = deque([(0,0,1)])
    while(len(qu) != 0):
        p,q,r = qu.popleft()
        S[p][q] = '#'
        for d in [(-1,0), (0,-1), (1,0), (0,1)]:
            s = p+d[0]
            t = q+d[1]
            if (s < 0 or t < 0 or s >= H or t >= W):
                continue
            if (s == (H-1) and t == (W-1)):
                return r+1
            if S[s][t] == '.':
                qu.append((s,t,r+1))
    return -1

H, W = list(map(int, input().split()))
S = []

cnt = 0
for i in range(H):
    a = input()
    tmp = []
    for i in a:
        if (i == '.'):
            cnt += 1
        tmp.append(i)
    S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
    print(cnt - step)
else:
    print(step)

Submission status: Time Limit Exceeded

Solution code:
# BFS version

#
H, W = list(map(int, input().split()))
M = []
for i in range(H):
    M.append(list(input().rstrip()))

#
def walk(pos):
    queue = [pos]

    while len(queue)>0:
        pos = queue.pop(0)
        x, y = pos
        val = M[y][x]
        #print(x,y,val)

        # up
        if y>0 and (M[y-1][x]=='.' or (isinstance(M[y-1][x], int) and val<M[y-1][x])):
            M[y-1][x] = val + 1
            queue += [(x, y-1)]
        # down
        if y<H-1 and (M[y+1][x]=='.' or (isinstance(M[y+1][x], int) and val<M[y+1][x])):
            M[y+1][x] = val + 1
            queue += [(x, y+1)]
        # left
        if x>0 and (M[y][x-1]=='.' or (isinstance(M[y][x-1], int) and val<M[y][x-1])):
            M[y][x-1] = val + 1
            queue += [(x-1, y)]
        # right
        if x<W-1 and (M[y][x+1]=='.' or (isinstance(M[y][x+1], int) and val<M[y][x+1])):
            M[y][x+1] = val + 1
            queue += [(x+1, y)]
        #print('B')

#
M[H-1][W-1] = 1
walk((W-1, H-1))
#print(M)
#exit()

#
if M[0][0]=='.':
    print(-1)
else:
    blocks = sum([m.count('#') for m in M])
    print(H*W - blocks - M[0][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    """
    ゲームの開始時点ではマス (1,1)
    上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す
    白いマスだけを通って (H,W) にたどり着けばゲームクリア

    マス (i,j) 最初
    白で塗られている場合 .
    黒で塗られている場合 #

    いくつかの白いマス目の色を黒に変えることができる
    ただし, マス (1,1) と (H,W) の色を変えることはできず
    -> ルートの変更は不可能

    ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる
    最大のスコアを求めなさい
    → 最短距離を求め,必要ない白マスを黒に変えれば高スコア(BFS?)
    → 経路を覚えておかないといけない
    """
    H, W = map(int, input().split())
    S = [
        input()
        for _ in range(H)
    ]

    bfs(S, H, W)


def bfs(S, H, W):
    if S[0][0] == "#":
        print(-1)
        return

    n_pos = [(0, 1), (1, 0)]
    # 距離を追加, 経路情報は必要ない
    q = deque([(0, 1, 1), (1, 0, 1)])
    visited = [
        [False] * W
        for _ in range(H)
    ]
    visited[0][0] = True

    goal = False
    dist = 0
    while q:
        x, y, dist = q.pop()
        visited[y][x] = True
        if S[y][x] == "#":
            continue

        if (x, y) == (W-1, H-1):
            goal = True
            break

        for dx in (-1, 1):
            nx = x+dx
            if 0 <= nx < W:
                if S[y][nx] == "." and not visited[y][nx]:
                    q.appendleft((nx, y, dist+1))
        for dy in (-1, 1):
            ny = y+dy
            if 0 <= ny < H:
                if S[ny][x] == "." and not visited[ny][x]:
                    q.appendleft((x, ny, dist+1))

    if goal:
        w_count = 0
        for s in S:
            w_count += s.count(".")
        # startは通ってないので距離に含まれない
        print(w_count - dist - 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    """
    ゲームの開始時点ではマス (1,1)
    上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す
    白いマスだけを通って (H,W) にたどり着けばゲームクリア

    マス (i,j) 最初
    白で塗られている場合 .
    黒で塗られている場合 #

    いくつかの白いマス目の色を黒に変えることができる
    ただし, マス (1,1) と (H,W) の色を変えることはできず
    -> ルートの変更は不可能

    ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる
    最大のスコアを求めなさい
    → 最短距離を求め,必要ない白マスを黒に変えれば高スコア(BFS?)
    → 経路を覚えておかないといけない
    """
    H, W = map(int, input().split())
    S = [
        input()
        for _ in range(H)
    ]

    bfs(S, H, W)


def bfs(S, H, W):
    if S[0][0] == "#":
        print(-1)
        return

    n_pos = [(0, 1), (1, 0)]
    # 距離を追加, 経路情報は必要ない
    q = deque([(0, 1, 1), (1, 0, 1)])
    visited = [
        [False] * W
        for _ in range(H)
    ]
    visited[0][0] = True

    goal = False
    dist = 0
    while q:
        x, y, dist = q.pop()
        visited[y][x] = True
        if S[y][x] == "#":
            continue

        if (x, y) == (W-1, H-1):
            goal = True
            break

        for dx in (-1, 1):
            nx = x+dx
            if 0 <= nx < W:
                if not visited[y][nx]:
                    q.appendleft((nx, y, dist+1))
        for dy in (-1, 1):
            ny = y+dy
            if 0 <= ny < H:
                if not visited[ny][x]:
                    q.appendleft((x, ny, dist+1))

    if goal:
        w_count = 0
        for s in S:
            w_count += s.count(".")
        # startは通ってないので距離に含まれない
        print(w_count - dist - 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

h, w = map(int, input().strip().split(" "))
maze = [input().strip() for _ in range(h)]
checked = [[h * w + 1 for _ in range(w)] for _ in range(h)]
num_sharp = 0
for r in maze:
    num_sharp += r.count("#")


def search(x, y, count):
    if not (0 <= x < h) or not (0 <= y < w) or maze[x][y] == "#" or checked[x][y] <= count:
        return False
    else:
        checked[x][y] = count
        return search(x + 1, y, count + 1) or search(x, y + 1, count + 1) or search(
            x - 1, y, count + 1) or search(x, y - 1, count + 1)


search(0, 0, 1)
if checked[-1][-1] <= h * w:
    print(h * w - checked[-1][-1] - num_sharp)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(S):
    qu = deque([(0,0,1)])
    while(len(qu) != 0):
        a = qu.popleft()
        p,q,r = a
        S[p][q] = 'a'
        for d in [(-1,0), (0,-1), (1,0), (0,1)]:
            dp,dq = d
            s = p+dp
            t = q+dq
            if (s < 0 or t < 0 or s >= H or t >= W):
                continue

            if (s == (H-1) and t == (W-1)):
                return r+1
            if S[s][t] == '.':
                qu.append((s,t,r+1))
    return -1

H, W = list(map(int, input().split()))
S = []

cnt = 0
for i in range(H):
    a = input()
    tmp = []
    for i in a:
        if (i == '.'):
            cnt += 1
        tmp.append(i)
    S.append(tmp)

step = bfs(S)

if (step != -1):
    print(cnt - step)
else:
    print(step)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

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

d = {}
def walk(i, j, c):
	if i < 0 or i >= H or j < 0 or j >= W:
		return
	if s[i][j] != ".":
		return
	if (i, j) in d and c >= d[(i, j)]:
		return

	d[(i, j)] = c
	for z in range(i-1, i+2):
		walk(z, j, c+1)
	for z in range(j-1, j+2):
		walk(i, z, c+1)

walk(0, 0, 1)
if (H-1, W-1) in d:
	print("".join(map(lambda x: "".join(x), s)).count(".") - d[(H-1, W-1)])
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy as sp
import scipy.sparse.csgraph as sg

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

g = np.zeros((H*W,H*W))

v_edges = [((i,j), (i,j+1)) for i in range(H) for j in range(W-1) if ss[i][j] == "." and ss[i][j+1] == "."]
h_edges = [((i,j), (i+1,j)) for i in range(H-1) for j in range(W) if ss[i][j] == "." and ss[i+1][j] == "."]

for (si,sj), (di,dj) in v_edges + h_edges:
    g[si*W+sj][di*W+dj] = 1
    g[di*W+dj][si*W+sj] = 1

r = sg.dijkstra(g)
score = r[0,H*W-1]

if sp.isinf(score):
    print(-1)
    exit(0)
else:
    #print(r)
    #print(ss) 

    ss_ = "".join(ss)
    num = len([0 for c in ss_ if c == '.'])
    #print(num)
    #print(score)
    print("%d" % (num - (score+1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)

h, w = map(int, input().split())
route = [[] for j in range(w * h)]
prev = []
somes = 0
for e in range(h):
    a = list(input())
    for g in a:
        if g == ".":
            somes += 1
    for l in range(w - 1):
        if a[l:l+2] == [".", "."]:
            route[e*w + l].append(e*w + l + 1)
            route[e * w + l + 1].append(e * w + l)
    if not prev:
        prev = a
        continue
    for l in range(len(a)):
        if a[l] == prev[l] == ".":
            route[e*w + l].append(e*w+l-w)
            route[e * w + l - w].append(e * w + l)
    prev = a
start = 0
goal = h*w-1
routes = []
eachmin = [float("inf") for i in range(h*w)]
eachmin[0] = 0
queue = deque([start])
searched = []
def bfs(time = 0):
    global searched, queue

    while queue:
        now = queue.popleft()

        if now == goal:
            break

        for j in route[now]:
            if j not in searched:
                queue.append(j)
                eachmin[j] = eachmin[now] + 1
        searched.append(now)

bfs(start)
if eachmin[-1] > 500000:
    print("-1")
    exit()
print(somes - eachmin[-1] - 1)

Submission status: Time Limit Exceeded

Solution code:
import queue

def solve():
    h, w = map(int, input().split())

    field = [input() for _ in range(h)]

    dist = [[h*w*100 for i in range(w)] for j in range(h)]
    dist[0][0] = 1

    q = queue.Queue()
    q.put((0,0))

    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    while not q.empty() :
        (x,y) = q.get()
        for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)] :
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= h or ny < 0 or ny>= w :
                continue
            if field[nx][ny] == '#':
                continue
            if dist[nx][ny] > dist[x][y] :
                dist[nx][ny] = dist[x][y] + 1
                q.put((nx,ny))

    if dist[h-1][w-1] >= h*w :
        return -1

    # print(dist)

    ans = h*w - dist[h-1][w-1]
    for v in field:
        for c in v:
            if c == '#':
                ans -= 1

    return ans

print(solve())