https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
분류 : BFS
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class Myscanner {
BufferedReader br;
StringTokenizer st;
public Myscanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
public static Myscanner sc = new Myscanner();
public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static int N, M, inf = Integer.MAX_VALUE / 2;
static char[][] adj;
static int[][][] map;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
public static void main(String[] args) throws IOException {
N = sc.nextInt();
M = sc.nextInt();
adj = new char[N + 1][M + 1];
map = new int[N + 1][M + 1][2];
for (int i = 1; i <= N; i++) {
String str = sc.next();
for (int j = 1; j <= M; j++) {
adj[i][j] = str.charAt(j - 1);
}
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
for (int k = 0; k <= 1; k++)
map[i][j][k] = inf;
Queue<Point> q = new LinkedList<>();
map[1][1][0] = 1;
q.offer(new Point(1, 1, 0));
while (!q.isEmpty()) {
int size = q.size();
for (int sz = 0; sz < size; sz++) {
Point p = q.poll();
int x = p.x;
int y = p.y;
int check = p.check;
for (int ar = 0; ar < 4; ar++) {
int cx = x + dx[ar];
int cy = y + dy[ar];
if (cx >= 1 && cx <= N && cy >= 1 && cy <= M) {
if (adj[cx][cy] == '0' && (map[cx][cy][check] > map[x][y][check] + 1)) {
map[cx][cy][check] = map[x][y][check] + 1;
q.offer(new Point(cx, cy, check));
} else if (adj[cx][cy] == '1' && check == 0 && (map[cx][cy][check] > map[x][y][check] + 1)) {
map[cx][cy][1] = map[x][y][0] + 1;
q.offer((new Point(cx, cy, 1)));
}
}
}
}
}
if (map[N][M][0] == inf && map[N][M][1] == inf)
out.println(-1);
else
out.println(Math.min(map[N][M][0], map[N][M][1]));
out.flush();
}
}
class Point {
int x;
int y;
int check;
Point(int x, int y, int check) {
this.x = x;
this.y = y;
this.check = check;
}
}
미로 문제나 탈출 하는 BFS 문제가 제일 재밌는 것 같다..
이 문제는 벽을 부수냐 마냐 의 경우를 추가해서 BFS를 돌려서 풀면 된다.
앞으로 더 열심히 많이 풀어야지
'PS' 카테고리의 다른 글
[BOJ]10422번 : 괄호 (0) | 2017.04.03 |
---|---|
[BOJ]11723번 : 집합 (0) | 2017.04.03 |
[BOJ]3055번: 탈출 (0) | 2017.04.02 |
[BOJ]1194번 : 달이 차오른다, 가자. (0) | 2017.03.31 |
[BOJ]5427번 : 불 (0) | 2017.03.31 |