コード:口語のヒアリング能力は-5を書きます

実際,アルゴリズムは1ヶ月以内に閲覧でき,問題を迎えることができる程度に上昇することは不可能である.最近チームメンバーとBFS問題を深く検討しています.毎日1つの問題を作って、百俊のSilverとGold以上の問題を解答します.今日はこの2つの問題をして、またして、また考えて、また注釈をして、またして、またして、また聞いて、またしました.1つ目の問題はWalls and Gatesで,2つ目の問題は破壁移動である.この二つの問題はBFS問題で、一人で考えすぎて、愛が少なくなった.特に最初の質問は、BFSに対する理解力を高め、私の考えを変えました(?)に役立つ
by leetcode, https://leetcode.com/problems/walls-and-gates/solution/
私は通常多くの基礎のBFSをして、普通は訪問しますかそれとも最も短い距離の回数で、このような方式は多くの問題を出して、このような問題、私はどの位置で接近する情況を見つけることに慣れていません.実は考えなければなりませんが...つまり,ゲート位置を中心にDeckによりキューを解放する.

from collections import deque
def wallsAndGates(rooms):
    '''
    Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
    Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
    '''
    empty_room = 2**31 -1 # 2147483647
    m = len(rooms) #행 길이
    n = len(rooms[0]) #열 길이

    directions = [0, 1, 0, -1, 0] #네비게이션 준비: 위 아래 오른쪽 왼쪽 이렇게 표현하는것이 더 느낌있어보인다.
    q = deque() #BFS니까 큐 장착하고, 데크 준비합시다
    for i in range(m):
        for j in range(n):
            if rooms[i][j] == 0:
                q.append((i, j)) #예시 인풋일경우: deque([(0, 2), (3, 0)])
    while q:
        i, j = q.popleft() # q 상태: (0,2) (3,0)
        for k in range(4):
            x = i + directions[k]
            y = j + directions[k+1]
            #  (x, y) -> (0,2): (0, 3), (1, 2), (0, 1), (-1, 2)
            # (x, y) -> (3, 0): (3, 1), (4,0), (3, -1), (2, 0)
            if x < 0 or x >=m or y < 0 or y >=n:
                continue
            if rooms[x][y] != empty_room:
                continue
            rooms[x][y] = rooms[i][j] + 1 #게이트 근처에 있으면 1, 그리고 근처 1인 좌표를 저장해주고,
            q.append((x, y)) #나중에 큐를 이용해서 또 게이트와 얼마나 먼 좌표인지 계산하고 거리만큼 더하기 해준다.
    return rooms #좌표에 나와있는 빈칸에 게이트로부터 얼만틈 먼지 다 적어놓은 것을 반환해준다.

rooms = [[2147483647,-1,0,2147483647],
         [2147483647,2147483647,2147483647,-1],
         [2147483647,-1,2147483647,-1],
         [0,-1,2147483647,2147483647]]
print(wallsAndGates(rooms))

2番目の問題は、私たちが決めた問題で、白から出た問題です.私の実力の中で、この問題は最高級で、とても難しいです.これは一般的に二次配列を書く問題とは異なり,3回目を考慮しなければならない.実際、この問題に近づくと、2次元思考で壁を破る機能を増やすのは難しい.まず三次元配列方式でもカウントできるポケットを作成し,壁にぶつかったときに割るときと割らずにそのまま歩くときをmin()で最小の経路を印刷した.しかし失敗.結局、解けなかった・・・アイデアだけを残して...のりを見て研究に励む.選手たちも解けなかったのですが、エースが教えてくれたので上手に解けました.まず一番重要なのはifドアの下の状況です.
https://www.acmicpc.net/problem/2206

from collections import deque
import sys
#입력하자 인풋 확인하고, 문제 잘 읽어서 형식대로 절차 진행하자
#백준문제풀때 눈감고 import sys 써주고
input = sys. stdin.readline # 이것도 써주고
rows, cols = map(int, input().split()) #이것도 써주는데, map부터가 중요

matrix = [] #행렬 인풋 받아올준비합시다.

for _ in range(rows):#인풋받은 숫자들을 바탕으로 행렬을 만들어줍시다.
    matrix.append(list(map(int, input().strip()))) #정수로 받아오게 해준다.

visited = [[[0] * 2 for _ in range(cols)] for _ in range(rows)] #모든 구역을 0으로 깔아준다 -> 방문 안했다는뜻으로
visited[0][0][0] = 1 #3차원 배열로 벽을 부수는게 가능한지 불가능한지 입력해준다. visited[0][0][0]: 벽안부수고감 visited[0][0][1]:벽부수고감
directions = [0, 1, 0, -1, 0] #네비게이션기능이라고 내가 부른다. 위 아래 왼쪽 오른쪽 조건을 검사해서 이동

def bfs(x, y, z):
    q = deque() #bfs최단경로탐색을 위해서는 큐를 사용 해야하고, 그렇기때문에 데크를 사용한다.
    q.append((x, y, z)) #받아온 x, y, z로 시작! 여기선 0,0,0 에서 시작
    while q:
        a, b, c = q.popleft() # 맨처음에 들어간것부터 들어간다 (0, 0, 0) 시작
        if a == rows - 1 and b == cols - 1: #인풋값 좌표가 입력한 행렬의 끝좌표이면 / 도달한 경우
            return visited[a][b][c] #visited[5][3][c] 바로리턴해버려
        for k in range(4): #위 아래 왼쪽 오른쪽 검사실시!
            nx = a + directions[k] #위에 제시한 directions대로 x 한칸 옆에가서 검사하고
            ny = b + directions[k+1] #y한칸 가서 검사하기
            if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
                continue # 내가 입력한 행렬위에서 네비게이션이 움직이지 않으면 위로올라가.
            if matrix[nx][ny] == 1 and c == 0: # 벽이 있고 + 벽 아직 안부순상태
                visited[nx][ny][1] = visited[a][b][0] + 1 #이전상태 (벽 안부순상태) 에다가 부수고 갔다는 것을 말해준다
                q.append((nx, ny, 1)) #큐에다가 저장 #벽 부수고 간걸로 저장
            elif matrix[nx][ny] == 0 and visited[nx][ny][c] == 0: #네비했는데, 벽없고,  방문한적없으면
                visited[nx][ny][c] = visited[a][b][c] + 1 #한칸 이동시키고
                q.append((nx, ny, c)) #큐에다가 저장
    return -1 #목표지점 도달 못하면 -1 리턴
print(bfs(0, 0, 0))

(1)壁がある状態で壁が破られていない状態->壁が破られた後にキューを保存します(1つのグリッドを移動します).
(2)壁のない状態、アクセスされていない状態->キュー内を移動して1つのグリッドを保存します.
この部分が一番難しいです.最終的に3 D図を作成するとき、最後の部分は壁が破損しているかどうかを見ることです.今の白駿金の4級問題はこの程度で後でもっとこのような問題に直面することができます一般的にこのような等級問題の大部分はこのようなものだと言われています.まずこの二つの問題今日は一日中いろいろ考えてやっと解けた.満足する徹底的に復習する.