B)13565

しんとう

質問する

仁済(インジェ)大学生化学研究室で働いている石教授は、電流が浸透する繊維物質を開発している.この繊維物質は二次元Mである× Nメッシュで表すことができます.便宜上、2 Dメッシュの上を外側(outherside)、下を内側(inner side)として想像します.また、各ゲートは黒または白であり、黒は電流を遮断する物質であり、白は電流が通過できる物質である.電流は繊維物質の最も外側の白色メッシュに供給され、その後、上下左右に隣接する白色メッシュに伝達される.
金教授が開発した繊維物質の情報が2次元メッシュで与えられた場合、外側から流れる電流が内側に浸透できるかどうかを判断するプログラムを作成してください.
の例

あり得ない例

入力

第1行は、メッシュサイズを表すM(2≦M≦1000)およびN(2≦N≦1000)を与える.M行の間には、N個の0または1にスペースがありません.0は電流が流れる白、1は電流が通じない黒の格子を表します.

しゅつりょく

外から流れ出た電流がうまく奥まで伝わるとYESが出力されます.
そうでなければNOを出力する.
DFS,BFS
N行M列が与えられた場合,最終的にN行に到達すると電流がうまく内向きに流れると仮定し,パターンの探索アルゴリズムを用いることで問題を解決できる.
実装(DFS)
1.最初のローの値が0の場所を最初に決定します.
2.0から4方向(東、西、南、北)のナビゲーションを行い、値が0の場合はその点からナビゲーションを開始します.
3.ナビゲーションポイントがN行に到達した場合は「YES」を出力します.

import sys
sys.setrecursionlimit(10**8) #재귀 리미트 설정

def dfs(x,y):
    global result
    global visited
    visited[x][y] = True
    if x == N-1: #N행에 도달할 경우 return True
        result = True
        return result
    graph[x][y]=2
    for i in range(4): #4방향 탐색
        a,b = x + dx[i],y + dy[i] 
        if 0 <= a < N and 0 <= b < M:
            if not visited[a][b] and graph[a][b]==0:
                visited[a][b] = True
                dfs(a,b)


N,M = map(int,sys.stdin.readline().split())

graph = [list(map(int,list(sys.stdin.readline().rstrip())))for _ in range(N)]
visited = [[False]*(M) for _ in range(N)]
result = False
dx = [0,1,0,-1]
dy = [1,0,-1,0]

for j in range(M): #첫 행에서, 0인 원소를 찾는 과정
    if graph[0][j] ==0:
        dfs(0,j)
        if result:
            print("YES")
            break
if not result:
    print("NO")

最終的には一番奥に入るので、最初の行で0(起点)を探して、すべて入ることができなければ、さらに上へ行って、起点ではなく他の起点で経路を探す方法です.
では、BFSをどのように使って実現するのでしょうか.
実施(BFS)
1.入力した行列を1行目1列目から同じ高さの「0」に移動します.
2.検索した「0」から4方向、「0」が存在する場合はキューに入れる
3.キューから前の「0」の位置を取り出し、その位置から四方向ナビゲーションを再開します.
4.上記手順を継続し、N行にある場合は「YES」を出力します.

import sys
from collections import deque #큐를 사용하기 위한 라이브러리

def bfs():
    while queue:
        a,b = queue.popleft() #왼쪽부터 뽑음 (왼쪽이 가장 먼저 들어간 정보)
        if a == N-1:
            print("YES")
            return
        for i in range(4):
            a , b = a+dx[i],b+dy[i]
            if 0 <= a < N and 0 <= b < M:
                if not visited[a][b] and graph[a][b] == 0:
                    visited[a][b] = True
                    queue.append((a,b))
    print("NO")





dx = [0,1,0,-1]
dy = [1,0,-1,0]
N,M = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().rstrip()))for _ in range(N)]
visited = [[False]*M for _ in range(N)]

queue = deque()
for i in range(M): #첫 열 "0"의 위치를 큐에 넣어둠(시작점)
    if graph[0][i]==0:
        queue.append((0,i))
        visited[0][i] = True
bfs()

DFSとBFSの概念を熟知すれば,これは解決可能な問題である.
しかしミスが多すぎて、運行時に何度も現れなかった.