表情記号

8218 ワード
DFS/BFS テキストリンク

白駿14226


英善が画面上でS個の表情を作るのに要する時間の最大値を求める.
  • 英善は喜んでいたので、孝彬にS個の微笑みの表情を送りたいと思っていました.英善はすでに画面に表情を入力した.現在、S個の表情を作成するには、以下の3つの演算のみを使用します.
  • 画面のすべての表情をクリップボードにコピーして保存します.
  • クリップボードのすべての表情を画面に貼り付けます.
  • 画面の1つの表情記号を削除します.
  • すべての演算には1秒かかります.また、表情をクリップボードにコピーすると、以前のクリップボードの内容が上書きされます.
  • クリップボードが空の場合は貼り付けられず、一部をクリップボードにコピーすることはできません.また、クリップボードの一部の表情は削除できません.
  • 画面に表情を貼り付けると、クリップボードの表情が画面に追加されます.
  • 第1行は、S(2≦S≦1000)を与える.

    • にゅうしゅつりょく


    入出力2244465188

    方法


    :bfsを用いて3つの状況を行う.すべての演算に同じ1秒を要するため,重みを付けずに追加する.

    知るところ


    画面上の表情は、クリップボード上の表情の数とともに2 D配列として表示されます.
    いずれの場合も、キューに配置して

    コード#コード#

    from collections import deque

def bfs(n, visited):
    visited[1][0] = 0
    q = deque()
    q.append((1,0))

    while q:
        u, c = q.popleft()
        if u==n:
            return visited[u][c]

        #화면 모두 복사 클립보드에 저장
        if 0<=u<=n and visited[u][u] == -1:
            visited[u][u] = visited[u][c]+1
            q.append((u,u))

        #클립보드 모두 화면으로 붙여넣기
        if 0<=u+c<=n and visited[u+c][c] == -1:
            visited[u+c][c] = visited[u][c]+1
            q.append((u+c, c))

        #화면에 있는 이모티콘 하나 삭제
        if 0<=u-1<=n and visited[u-1][c] == -1:
            visited[u-1][c] = visited[u][c]+1
            q.append((u-1,c))


n = int(input())

#화면, 클립보드
visited = [[-1]*(n+1) for _ in range(n+1)]
print(bfs(n, visited))
    【読書ノート】『JavaScriptデザインモード』を読むエージェントモード
    返信の確認