結果

問題 No.611 Day of the Mountain
ユーザー zimphazimpha
提出日時 2017-12-11 21:50:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,068 ms / 2,017 ms
コード長 1,725 bytes
コンパイル時間 817 ms
コンパイル使用メモリ 87,432 KB
実行使用メモリ 259,712 KB
最終ジャッジ日時 2023-08-20 17:34:22
合計ジャッジ時間 5,065 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 378 ms
259,416 KB
testcase_01 AC 380 ms
259,712 KB
testcase_02 AC 376 ms
259,560 KB
testcase_03 AC 1,068 ms
134,152 KB
testcase_04 AC 69 ms
76,852 KB
testcase_05 AC 71 ms
76,656 KB
testcase_06 AC 65 ms
71,504 KB
testcase_07 AC 67 ms
71,444 KB
testcase_08 AC 73 ms
76,528 KB
testcase_09 AC 61 ms
71,592 KB
testcase_10 AC 63 ms
71,440 KB
testcase_11 AC 67 ms
76,516 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 201712111
h, w = list(map(int, input().split()))
g = [input() for i in range(h)]
if h < w:
  g = [[g[i][j] for i in range(h)] for j in range(w)]
  h, w = w, h
else:
  g = [list(g[i]) for i in range(h)]

if g[0][0] == '?': g[0][0] = '1'
if g[-1][-1] == '?': g[-1][-1] = '1'

dp = [[1e9] * w for i in range(h)]
uf = [[0] * w for i in range(h)]
lf = [[0] * w for i in range(h)]
for i in range(h):
  for j in range(w):
    if i: dp[i][j] = min(dp[i][j], dp[i - 1][j])
    if j: dp[i][j] = min(dp[i][j], dp[i][j - 1])
    uf[i][j] = 1 if i and dp[i][j] == dp[i - 1][j] else 0
    lf[i][j] = 1 if j and dp[i][j] == dp[i][j - 1] else 0
    dp[i][j] += int(g[i][j]) if g[i][j] != '?' else 1
    if not i and not j: dp[i][j] = int(g[i][j])
for i in range(h - 1, -1, -1):
  for j in range(w - 1, -1, -1):
    if i == h - 1 and j == w - 1: continue
    valid = 0
    if i + 1 < h: valid |= uf[i + 1][j]
    if j + 1 < w: valid |= lf[i][j + 1]
    uf[i][j] &= valid
    lf[i][j] &= valid
s = 1 << w
u = [0] * s
u[1] = 1
for i in range(1, h * w):
  x, y = divmod(i, w)
  v = [0] * s
  use = (s - 1) ^ (1 << y)
  for mask in range(s):
    u[mask] %= mod
    if not u[mask]: continue
    new_mask = mask & use
    from_left = (y > 0 and lf[x][y] and (mask >> (y - 1) & 1))
    from_up = (uf[x][y] and (mask >> y & 1))
    if g[x][y] == '?':
      if from_left or from_up:
        v[new_mask | (1 << y)] += u[mask]
        v[new_mask] += u[mask] * 8
      else:
        v[new_mask] += u[mask] * 9
    else:
      if from_left or from_up:
        v[new_mask | (1 << y)] += u[mask]
      else:
        v[new_mask] += u[mask]
  u = v

print(dp[-1][-1])
ret = 0
for mask in range(s // 2):
  ret += u[mask | (1 << (w - 1))]
print(ret % mod)
0