[Algorithm] CHEEZE

[アルゴリズムジョブズ/CHHEEZE問題]

もんだいぶんせき

:チーズとチーズが入った皿.皿にチーズが置いてある情報(2次元配列)によると、チーズは1時間ごとに「空気に触れる」部分を除去し、チーズが全部消えるまで数時間かかり、最後に消える1時間前に皿のチーズが占める格数を戻せばよい.このとき、気をつけなければならないのは、空気に触れる側だけが溶けてしまうことです.チーズには穴があります.この穴に空気がないことを前提にしています.もちろん、チーズが溶けたら、穴と外に隙間があれば、その時から空気が入ってきて、この部分も溶けてしまいます.実は解答する時この部分と0の接触する部分がすべて溶けている設定を見落としました問題を解いたばかりで少し迷った.

問題の設計と解決

:チーズをかじる(?)空気をどう表現するかに焦点を当てると、表面からチーズを溶かすことに重点を置くべきだ.最初にチーズを基準に探索する方法はありますか?私はそう思っていましたが、私は観点を変えて、空気の立場に立って(?)私たちは中で探求すべきだと思います.空気の立場に立って、自分の周りのチーズを溶かして、その部分から、探索を止める方向に放します.言い換えれば、(1,1)ノード(空気の位置の1つ)を基準にBFSを行っていると思ったら、BFSですべての空気を探知します.探索の過程で、空気ノードのサブノードにはチーズノードがあるに違いない.そのチーズノードが見つかったら、無条件にクリアします.しかし、このチーズノードのサブノードは探索を停止しなければならない.チーズのサブノードを探索すると,空気に接触する面積の一部のみを1時間で除去するのは規則に反する.このように1時間おきにチーズの置物全体を探索(空気ノードから)し、空気に触れたチーズを1つ取り除き、その方向への探索を停止すれば、空気が1時間にチーズの表面だけを溶かすことができる.このようにすると表面が溶けて止まるだけなので、チーズに穴が開いていても中を探索することはないので問題ありません.

設計の実装

:私が作った論理に基づいて解くために、まず0を探します.すなわち,ルート空気ノードを特定するため,O(N)の時間的複雑さで0を探し,座標を保存して破る.そしてグルートエアノードを連れてBFSのブラウズを開始する.この時、条件は上記の通りです.

空気に遭遇すると、その空気にアクセスした記録が保存され、その空気のサブノードがキューに入れられ、さっき閲覧した空気はpop

であった.

チーズに遭遇した場合は、そこにアクセスできないため、対応する座標にアクセスしてポップアップ(キューに入れない)を記録します.

はこのようにBFSを行い、これらのBFSをチーズが全て溶けるまで行わなければならない.すなわち、BFSは、2番目のWhile文とともに2つ目のwhile文で実装される.そして最初のWhileゲートを計算して数時間が経ちました.この場合、BFS終了後にチーズ数をprev変数に保存してこそ、最後に残ったチーズが得られる.

上記の方法で、時間の複雑さは問題ありませんか?まず横方向、縦方向の最大値は100です.私の論理では、チーズが全部溶けるまでBFSを100*100=10000回実行します.しかし最悪なのは、チーズがバージョン全体を占め、接着剤(?)の使用を開始したことです.必要に応じて、一度に境界を除去して行うので、時間の複雑さに影響を与える大きな回収は行われない.
**従来のチーズの数は、試験終了時に数えるたびに効率が悪いようですが、最初に0を探していたときや、初めて板を作ったときに1つ数えて、チーズを削除するたびに計算して、その数から減算すればいいのです.

実装コード(1)

import copy n,m = map(int, input().split()) board = [] for i in range(n): board.append([-1] + list(map(int, input().split())) + [-1]) board = [[-1 for i in range(m+2)]] + board + [[-1 for i in range(m+2)]] cnt = 0 while True: cnt+= 1 copy_board = copy.deepcopy(board) path = {} queue = [(1,1)] path[(1,1)] = True deleted_count = 0 while len(queue) != 0 : top = queue.pop(0) up = (top[0]-1, top[1]) right = (top[0], top[1]+1) down = (top[0]+1, top[1]) left = (top[0], top[1]-1) arr = [] if board[up[0]][up[1]] == -1: pass elif board[up[0]][up[1]] == 0: try: if path[up]: pass except: path[up] = True arr.append(up) elif board[up[0]][up[1]] == 1: try: if path[up]: pass except: path[up] = True copy_board[up[0]][up[1]] = 0 deleted_count+=1 if board[right[0]][right[1]] == -1: pass elif board[right[0]][right[1]] == 0: try: if path[right]: pass except: path[right] = True arr.append(right) elif board[right[0]][right[1]] == 1: try: if path[right]: pass except: path[right] = True copy_board[right[0]][right[1]] = 0 deleted_count+=1 if board[down[0]][down[1]] == -1: pass elif board[down[0]][down[1]] == 0: try: if path[down]: pass except: path[down] = True arr.append(down) elif board[down[0]][down[1]] == 1 : try: if path[down]: pass except: path[down] = True copy_board[down[0]][down[1]] = 0 deleted_count+=1 if board[left[0]][left[1]] == -1: pass elif board[left[0]][left[1]] == 0: try: if path[left]: pass except: path[left] = True arr.append(left) elif board[left[0]][left[1]] == 1: try: if path[left]: pass except: path[left] = True copy_board[left[0]][left[1]] = 0 deleted_count+=1 queue+= arr flag = True for i,row in enumerate(copy_board): for j, col in enumerate(row): if col == 1 : flag = False board[i][j] = col if flag: print(cnt) print(deleted_count) break :上のコードは私がこのブログを発表する前に問題を解くときに書いたコードです.しかし、より効率的にコードを書くため(?)復習を兼ねて問題を書き直す.

実装コード(2)

n, m = map(int, input().split()) board = [] root = () cheese_cnt = 0 flag = True for i in range(n): input_list = list(map(int, input().split())) if 0 in input_list and flag: root = (i+1, input_list.index(0)+1) flag = False cheese_cnt += input_list.count(1) board.append([None] + input_list + [None]) limit_line = [[None for i in range(m+2)]] board = limit_line + board + limit_line hour = 0 if cheese_cnt == 0: print(hour) else: queue = [] prev_cnt = cheese_cnt while True: hour += 1 queue.append(root) visit = {} visit[root] = True while len(queue) != 0: top = queue.pop(0) ways = [(top[0]-1,top[1]),(top[0],top[1]+1),(top[0]+1,top[1]),(top[0],top[1]-1)] for dir in ways: if board[dir[0]][dir[1]] is None: continue else: try: if visit[dir]: continue except: visit[dir] = True if board[dir[0]][dir[1]] == 1: cheese_cnt -= 1 board[dir[0]][dir[1]] = 0 elif board[dir[0]][dir[1]] == 0: queue.append(dir) if cheese_cnt == 0: break prev_cnt = cheese_cnt print(hour) print(prev_cnt) より効率的なコードを書くよりも、以前より簡略化され、より簡単な論理で書かれています.確かに最初はdeepcopyでずっと板をコピーして確認していたのになぜそうしなければならなかったのか
また,1回目の試みでは,複数のif文が用いられ,コードの長さが余計になり,2回目の試みではかなり簡略化された.また,従来のコードでは,実行ごとに配列全体を遍歴し,チーズが溶けていることを確保していたが,今回はchees cntを用いてこの低効率を解消した.