[伯俊]206壁を破って移動

📌 質問する

N×Mのマトリックス表現のマッピングがあります.地図では、0は移動可能な位置、1は移動不可能な壁の位置を示す.(1,1)から(N,M)の位置に移動し、最短経路に移動します.最短パスとは、地図上の最小セルを通るパスで、開始セルと終了セルが含まれます.
移動中に壁を割ったり移動したりする経路がもっと短い場合は、壁を割って移動することができます.
1つのセルで移動できるセルは上下左右に隣接するセルです.
地図を指定すると、最短パスを解くプログラムが作成されます.

✔方法

最短距離を求める問題なのでBFSを使います.
BFSを使えば比較的簡単に問題を解決できると思いますが、想像以上に時間がかかる問題です.
アクセスをチェックするvisit配列の座標値と壁があるかどうかをチェックする値を一緒にすることに重点を置きます.
同じ座標に近づいても、壁を破るか否かによって次の座標に移動する経路が変わるからです.

✔コード

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class qnode {
	int x;
	int y;
	boolean check; // 벽 부셨는지
	int count;

	public qnode(int x, int y, boolean check, int count) {
		this.x = x;
		this.y = y;
		this.check = check;
		this.count = count;
	}
}

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] map = new int[n][m];
		boolean[][][] visit = new boolean[n][m][2];
		Queue<qnode> q = new LinkedList<>();
		int[] dx = { -1, 0, 1, 0 };
		int[] dy = { 0, 1, 0, -1 };
		for (int i = 0; i < n; i++) {
			String Line = sc.next();
			for (int j = 0; j < m; j++) {
				map[i][j] = Line.charAt(j);
			}
		}

		q.offer(new qnode(0, 0, false, 1));
		visit[0][0][0] = true;
		int answer = 1000000;
		while (!q.isEmpty()) {
			qnode cur = q.poll();
			int cx = cur.x;
			int cy = cur.y;
			int checkCount = 0;
			boolean check = cur.check;
			int curCount = cur.count + 1;

			if (check)
				checkCount = 1;

			if (cx == n - 1 && cy == m - 1) {
				answer = Math.min(answer, curCount - 1);
				continue;
			}
			

			// 방향 4개 이동
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];

				if (nx < 0 || nx >= n || ny < 0 || ny >= m)
					continue;
				if (visit[nx][ny][checkCount])
					continue;

				if (map[nx][ny] == '1' && !check) { // 벽이고 아직 벽을 안부셨으면
					visit[nx][ny][1] = true; // 방문표시
					q.offer(new qnode(nx, ny, true, curCount)); // 벽을 부시고 넣음
				}
				if (map[nx][ny] == '0') {
					visit[nx][ny][checkCount] = true;
					q.offer(new qnode(nx, ny, check, curCount));
				}
			}
		}

		if (answer == 1000000)
			answer = -1;
		System.out.println(answer);

	}
}

ソース:https://www.acmicpc.net/problem/2206