[알고리즘] 최 단 통로 값 구하 기
하나의 성형 매트릭스 매트릭스 매트릭스 로 하나의 네트워크 를 표시 합 니 다. 1 은 길이 있다 는 것 을 의미 하고 0 은 길이 없다 는 것 을 의미 합 니 다. 모든 위 치 는 경 계 를 넘 지 않 으 면 상하 좌우 4 개의 방향 이 있 습 니 다. 가장 왼쪽 상단 에서 가장 오른쪽 하단 까지 의 최 단 통로 값 을 구 합 니 다.
예 를 들 면:
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
0 0 0 0 1
통 로 는 1 개 로 12 개 1 로 이 루어 져 있 기 때문에 12 로 돌아간다.
해답:
너비 우선 옮 겨 다 니 기 를 사용 하면 됩 니 다. 행렬 크기 가 N * M 이면 시간 복잡 도 는 O (N * M) 입 니 다.
1. 시작 할 때 맵 행렬 을 생 성 합 니 다. 맵 [i] [j] 의 의 미 는 (0, 0) 위치 에서 (i, j) 위치 로 가 는 가장 짧 은 경로 값 입 니 다.그리고 왼쪽 상단 위치 (0, 0) 의 줄 좌표 와 열 좌 표를 줄 대기 열 rQ, 열 에 넣 습 니 다. cQ。
2. 대기 열 에서 한 위치 (r, c) 를 계속 꺼 내 고 이 위치의 상하 좌우 네 개의 위치 가 매트릭스 에 있 는 값 이 1 인지 볼 수 있 는 위치 입 니 다.
3. 갈 수 있 는 위 치 를 각각 map 에 있 는 값, 즉 map [r] [c] + 1 로 설정 합 니 다.이 위 치 를 rQ 와 cQ 에 추가 하고 대기 열 로 너비 우선 옮 겨 다 닙 니 다.
4. 단계 3 에서 한 위치 가 지나 가면 반복 하지 마 세 요. 이 논 리 는 한 위치 가 map 에 있 는 값 에 따라 확정 할 수 있 습 니 다. 예 를 들 어 map [i] [j]! =0. 이 자 리 를 알 기 전에 지나 갑 니 다.
5. 계속 2 ~ 4 단 계 를 반복 한다.오른쪽 아래 에 있 는 위 치 를 만 날 때 까지 종점 을 찾 았 음 을 설명 합 니 다. 종점 이 map 에 있 는 값 으로 돌아 가면 됩 니 다. rQ 와 cQ 가 비어 있 으 면 종점 위 치 를 만 나 지 못 했 습 니 다. return 0.
public static int minPathValue(int[][] m) {
if (m == null || m.length == 0 || m[0].length == 0 || m[0][0] != 1
|| m[m.length - 1][m[0].length - 1] != 1) {
return 0;
}
int res = 0;
int[][] map = new int[m.length][m[0].length];
map[0][0] = 1;
Queue<Integer> rQ = new LinkedList<Integer>();
Queue<Integer> cQ = new LinkedList<Integer>();
rQ.add(0);
cQ.add(0);
int r = 0;
int c = 0;
while (!rQ.isEmpty()) {
r = rQ.poll();
c = cQ.poll();
if (r == m.length - 1 && c == m[0].length - 1) {
return map[r][c];
}
walkTo(map[r][c], r - 1, c, m, map, rQ, cQ); // up
walkTo(map[r][c], r + 1, c, m, map, rQ, cQ); // down
walkTo(map[r][c], r, c - 1, m, map, rQ, cQ); // left
walkTo(map[r][c], r, c + 1, m, map, rQ, cQ); // right
}
return res;
}
public static void walkTo(int pre, int toR, int toC, int[][] m,
int[][] map, Queue<Integer> rQ, Queue<Integer> cQ) {
if (toR < 0 || toR == m.length || toC < 0 || toC == m[0].length
|| m[toR][toC] != 1 || map[toR][toC] != 0) {
return;
}
map[toR][toC] = pre + 1;
rQ.add(toR);
cQ.add(toC);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
