하나의 N X N 행렬 M이 있고 이것이 1, 0, 2, 3으로 채워져 있다고 가정합니다. 소스 셀에서 대상 셀로 이동하는 데 필요한 최소 이동 횟수를 찾아야 합니다. . 빈 셀로만 방문할 때 위, 아래, 오른쪽, 왼쪽을 방문할 수 있습니다.
-
값이 1인 셀은 소스를 나타냅니다.
-
값이 2인 셀은 대상을 나타냅니다.
-
값이 3인 셀은 빈 셀을 나타냅니다.
-
값이 0인 셀은 빈 벽을 나타냅니다.
하나의 소스와 하나의 대상 셀만 있을 것입니다. 소스 셀에서 목적지에 도달하는 경로가 둘 이상 있을 수 있습니다. 이제 행렬의 각 이동은 '1'로 간주됩니다.
따라서 입력이 다음과 같으면
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
그러면 출력은 5가 됩니다.
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
시작에서 목적지까지 녹색 경로가 가장 짧습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
노드 :=주문 * 주문 + 2
-
g :='노드' 수의 정점이 있는 빈 그래프
-
k :=1
-
주문하려면 범위 0에 있는 i에 대해
-
범위 0의 j에 대해 주문하려면
-
mat[i, j]가 0과 같지 않으면
-
is_ok(i , j + 1 , mat)가 0이 아니면
-
k와 k + g의 1개 노드 사이에 간선 생성
-
-
is_ok (i , j - 1 , mat)가 0이 아니면
-
k, k - g의 1개 노드 사이에 간선 생성
-
-
j
-
k, k + g의 차수 노드 사이에 간선 생성
-
-
i> 0이고 is_ok(i - 1 , j , mat)가 0이 아닌 경우
-
k, k 사이에 에지 생성 - g
의 차수 노드
-
-
-
mat[i, j]가 1과 같으면
-
src :=k
-
-
mat[i, j]가 2와 같으면
-
목적지 :=k
-
-
k :=k + 1
-
-
-
src에서 g의 dest까지 수행 bfs를 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Graph: def __init__(self, nodes): self.nodes = nodes self.adj = [[] for i in range(nodes)] def insert_edge (self, src , dest): self.adj[src].append(dest) self.adj[dest].append(src) def BFS(self, src, dest): if (src == dest): return 0 level = [-1] * self.nodes queue = [] level[src] = 0 queue.append(src) while (len(queue) != 0): src = queue.pop() i = 0 while i < len(self.adj[src]): if (level[self.adj[src][i]] < 0 or level[self.adj[src][i]] > level[src] + 1 ): level[self.adj[src][i]] = level[src] + 1 queue.append(self.adj[src][i]) i += 1 return level[dest] def is_ok(i, j, mat): global order if ((i < 0 or i >= order) or (j < 0 or j >= order ) or mat[i][j] == 0): return False return True def get_min_math(mat): global order src , dest = None, None nodes = order * order + 2 g = Graph(nodes) k = 1 for i in range(order): for j in range(order): if (mat[i][j] != 0): if (is_ok (i , j + 1 , mat)): g.insert_edge (k , k + 1) if (is_ok (i , j - 1 , mat)): g.insert_edge (k , k - 1) if (j < order - 1 and is_ok (i + 1 , j , mat)): g.insert_edge (k , k + order) if (i > 0 and is_ok (i - 1 , j , mat)): g.insert_edge (k , k - order) if(mat[i][j] == 1): src = k if (mat[i][j] == 2): dest = k k += 1 return g.BFS (src, dest) order = 4 mat = [[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]] print(get_min_math(mat))
입력
[[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]
출력
0