結果

問題 No.611 Day of the Mountain
ユーザー zimphazimpha
提出日時 2017-12-11 21:44:13
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,682 bytes
コンパイル時間 861 ms
コンパイル使用メモリ 87,232 KB
実行使用メモリ 79,348 KB
最終ジャッジ日時 2023-08-20 17:33:10
合計ジャッジ時間 3,168 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 AC 85 ms
76,800 KB
testcase_05 RE -
testcase_06 AC 77 ms
71,228 KB
testcase_07 AC 82 ms
71,476 KB
testcase_08 RE -
testcase_09 AC 76 ms
71,392 KB
testcase_10 AC 75 ms
71,120 KB
testcase_11 AC 83 ms
76,348 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

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