結果
問題 | No.460 裏表ちわーわ |
ユーザー |
![]() |
提出日時 | 2017-01-26 23:49:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 266 ms / 2,000 ms |
コード長 | 1,292 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 77,564 KB |
最終ジャッジ日時 | 2024-12-23 13:31:28 |
合計ジャッジ時間 | 4,861 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
INF = 10**9dx = [-1,-1,-1, 0, 1, 1, 1, 0]dy = [-1, 0, 1, 1, 1, 0,-1,-1]def dfs(y,x):if x == n:if y > 0:for j in range(n-2,n):if a[y-1][j]:return INFreturn dfs(y+1,0)elif y == m:for i in range(m-2,m):for j in range(n):if a[i][j]:return INFreturn 0if y > 0:ok = Truefor j in range(n):if a[y-1][j]:ok = Falseif ok:return dfs(y+1,0)ret = INFif x == 0 or y == 0 or a[y-1][x-1]:a[y][x] ^= 1for i in range(8):ny = y + dy[i]nx = x + dx[i]if ny < 0 or ny >= m or nx < 0 or nx >= n: continuea[ny][nx] ^= 1ret = min(ret,dfs(y,x+1)+1)a[y][x] ^= 1for i in range(8):ny = y + dy[i]nx = x + dx[i]if ny < 0 or ny >= m or nx < 0 or nx >= n: continuea[ny][nx] ^= 1if x == 0 or y == 0 or not a[y-1][x-1]:ret = min(ret,dfs(y,x+1))return retm,n = map(int,input().split(' '))a = [list(map(int,input().split(' '))) for i in range(m)]ans = dfs(0,0)if ans < INF:print(ans)else:print("Impossible")