Submission #3233653
Source Code Expand
from collections import deque h, w = map(int, input().split()) s = [] white = 0 for y in range(h): s.append(input()) white += s[y].count('.') def gets(y, x): if 1 <= y <= h and 1 <= x <= w: return s[y - 1][x - 1] == '.' else: return False v = set() q = deque([(1, 1, 0)]) costMin = -1 while len(q) > 0: y, x, cost = q.popleft() if (y, x) == (h, w): costMin = cost break if (y, x) not in v: v.add((y, x)) if gets(y - 1, x): q.append((y - 1, x, cost + 1)) if gets(y + 1, x): q.append((y + 1, x, cost + 1)) if gets(y, x - 1): q.append((y, x - 1, cost + 1)) if gets(y, x + 1): q.append((y, x + 1, cost + 1)) if costMin < 0: print(-1) else: print(white - costMin - 1)
Submission Info
Submission Time | |
---|---|
Task | D - Grid Repainting |
User | shirodoni |
Language | Python (3.4.3) |
Score | 400 |
Code Size | 811 Byte |
Status | AC |
Exec Time | 32 ms |
Memory | 3700 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt |
All | in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, s1.txt, s2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in01.txt | AC | 20 ms | 3316 KB |
in02.txt | AC | 20 ms | 3316 KB |
in03.txt | AC | 20 ms | 3316 KB |
in04.txt | AC | 20 ms | 3316 KB |
in05.txt | AC | 20 ms | 3316 KB |
in06.txt | AC | 20 ms | 3316 KB |
in07.txt | AC | 20 ms | 3316 KB |
in08.txt | AC | 20 ms | 3316 KB |
in09.txt | AC | 20 ms | 3316 KB |
in10.txt | AC | 20 ms | 3316 KB |
in11.txt | AC | 20 ms | 3316 KB |
in12.txt | AC | 20 ms | 3316 KB |
in13.txt | AC | 21 ms | 3316 KB |
in14.txt | AC | 21 ms | 3316 KB |
in15.txt | AC | 29 ms | 3572 KB |
in16.txt | AC | 32 ms | 3700 KB |
in17.txt | AC | 29 ms | 3572 KB |
in18.txt | AC | 29 ms | 3572 KB |
s1.txt | AC | 20 ms | 3316 KB |
s2.txt | AC | 21 ms | 3316 KB |