240705 벽 부수고 이동하기

static StringBuilder sb = new StringBuilder();

static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, 1, 0, -1 };

static int n;
static int m;
static char[][] board;

static class Position {
	int x;
	int y;

	public Position(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());

	n = Integer.parseInt(st.nextToken());
	m = Integer.parseInt(st.nextToken());
	board = new char[n][m];
	for (int i = 0; i < n; i++) {
		board[i] = br.readLine().toCharArray();
	}

	int[][] distStart = bfs(0, 0);
	int[][] distEnd = bfs(n - 1, m - 1);

	int ans = distStart[n - 1][m - 1];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == '1') {
				ans = Math.min(ans, distStart[i][j] + distEnd[i][j]);
			}
		}
	}
	System.out.println(ans == 1000001 ? -1 : ans + 1);
}

static int[][] bfs(int startX, int startY) {
	int[][] dist = new int[n][m];
	for (int[] row : dist) {
		Arrays.fill(row, 1000001);
	}
	ArrayDeque<Position> queue = new ArrayDeque<>();
	queue.add(new Position(startX, startY));
	dist[startX][startY] = 0;

	while (!queue.isEmpty()) {
		Position pos = queue.poll();
		for (int i = 0; i < 4; i++) {
			int nx = pos.x + dx[i];
			int ny = pos.y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (dist[nx][ny] != 1000001)
				continue;
			dist[nx][ny] = dist[pos.x][pos.y] + 1;
			if (board[nx][ny] == '0')
				queue.add(new Position(nx, ny));
		}
	}
	return dist;
}

출처:https://www.acmicpc.net/problem/2206