[白俊]206号破壁移動/Java,Python
Baekjoon Online Judge
algorithm practice
-問題を逐次解く
24.DFSとBFS
グラフを巡るアルゴリズムを学びましょう.
Java/Python
9.破壁移動
2206号
[現在の状態](Current State)を頂点としてグラフィックを作成し、最短距離を求める問題
この問題は,記述プログラムがNxM中の行列で表されるマッピングで最短経路を求めることである.
BFSナビゲーションが正常に使用されました.
import java.io.*;
import java.util.*;
public class Main {
static class Point{
int x;
int y;
int dist; // 이동 거리
int drill; // 공사 횟수
public Point(int x, int y, int dist, int drill){
this.x = x;
this.y = y;
this.dist = dist;
this.drill = drill;
}
}
static int N, M;
static int result;
static int[][] map, check;
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
check = new int[N][M];
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++){
map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
check[i][j] = Integer.MAX_VALUE;
}
}
result = Integer.MAX_VALUE;
bfs(0,0);
if (result == Integer.MAX_VALUE) {
bw.write("-1\n");
} else {
bw.write(result + "\n");
}
bw.flush();
bw.close();
br.close();
}
public static void bfs(int x, int y) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y, 1, 0));
check[y][x] = 0;
while (!queue.isEmpty()) {
Point p = queue.poll();
if(p.x == M - 1 && p.y == N - 1){
result = p.dist;
break;
}
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
if (check[ny][nx] > p.drill) {
if (map[ny][nx] == 0) {
queue.add(new Point(nx, ny, p.dist + 1, p.drill));
check[ny][nx] = p.drill;
}else{
if(p.drill == 0){
queue.add(new Point(nx, ny, p.dist + 1, p.drill + 1));
check[ny][nx] = p.drill + 1;
}
}
}
}
}
}
}
}
from collections import deque
import sys
N, M = map(int, sys.stdin.readline().split())
place = [list(map(int, input())) for _ in range(N)]
check = [[[0]*2 for _ in range(M)] for _ in range(N)]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
# bfs 경로 탐색
def bfs():
queue = deque()
queue.append([0, 0, 1])
check[0][0][1] = 1
while queue:
a, b, w = queue.popleft()
if a == N - 1 and b == M - 1:
return check[a][b][w]
for i in range(4):
x = a + dx[i]
y = b + dy[i]
if 0 <= x < N and 0 <= y < M:
if place[x][y] == 1 and w == 1:
check[x][y][0] = check[a][b][1] + 1
queue.append([x, y, 0])
elif place[x][y] == 0 and check[x][y][w] == 0:
check[x][y][w] = check[a][b][w] + 1
queue.append([x, y, w])
return -1
print(bfs())
Reference
この問題について([白俊]206号破壁移動/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-2206번-벽-부수고-이동하기-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol