結果
問題 | No.611 Day of the Mountain |
ユーザー |
|
提出日時 | 2017-12-11 21:50:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,174 ms / 2,017 ms |
コード長 | 1,725 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 247,296 KB |
最終ジャッジ日時 | 2024-11-30 21:03:12 |
合計ジャッジ時間 | 4,055 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 |
ソースコード
mod = 201712111h, 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, helse: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 0lf[i][j] = 1 if j and dp[i][j] == dp[i][j - 1] else 0dp[i][j] += int(g[i][j]) if g[i][j] != '?' else 1if 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: continuevalid = 0if i + 1 < h: valid |= uf[i + 1][j]if j + 1 < w: valid |= lf[i][j + 1]uf[i][j] &= validlf[i][j] &= valids = 1 << wu = [0] * su[1] = 1for i in range(1, h * w):x, y = divmod(i, w)v = [0] * suse = (s - 1) ^ (1 << y)for mask in range(s):u[mask] %= modif not u[mask]: continuenew_mask = mask & usefrom_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] * 8else:v[new_mask] += u[mask] * 9else:if from_left or from_up:v[new_mask | (1 << y)] += u[mask]else:v[new_mask] += u[mask]u = vprint(dp[-1][-1])ret = 0for mask in range(s // 2):ret += u[mask | (1 << (w - 1))]print(ret % mod)