boj)2206 - 벽 부수고 이동하기
2020. 10. 24. 17:17ㆍPS/boj
import java.io.*;
import java.util.*;
public class boj_2206 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M, nx, ny;
static int[][] map;
static boolean[][][] v;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static Queue<int[]> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int ans = -1;
map = new int[N+1][M+1];
v = new boolean[N+1][M+1][2];
for (int i = 1; i <= N; i++) {
String str = br.readLine();
for (int j = 1; j <= M; j++) {
map[i][j] = str.charAt(j-1) - '0';
}
}
v[1][1][0] = true;
q.offer(new int[] {1, 1, 1, 0});
while (!q.isEmpty()) {
int[] now = q.poll();
if (now[0] == N && now[1] == M) {
ans = now[2];
break;
}
for (int i = 0; i < 4; i++) {
nx = now[0] + dx[i];
ny = now[1] + dy[i];
if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
if (map[nx][ny] == 0) {
if (v[nx][ny][now[3]]) continue;
v[nx][ny][now[3]] = true;
q.offer(new int[] {nx, ny, now[2] + 1, now[3]});
} else {
if (now[3] != 0 || v[nx][ny][now[3]+1]) continue;
v[nx][ny][now[3]+1] = true;
q.offer(new int[] {nx, ny, now[2] + 1, now[3] + 1});
}
}
}
System.out.println(ans);
}
}
- 실패
- 가지고 이동해야 하는 값 x, y, distance, 벽 부순 횟수
'PS > boj' 카테고리의 다른 글
boj)2146 - 다리 만들기 (0) | 2020.11.02 |
---|---|
boj)13023 - ABCDE (0) | 2020.10.29 |
boj)2573 - 빙산 (0) | 2020.10.24 |
boj)1629 - 곱셈 (0) | 2020.10.23 |
boj)2468 - 안전 영역 (0) | 2020.10.21 |