[BOJ-JAVA]白俊2178迷宮を探る
リンク
https://www.acmicpc.net/problem/2178
質問する
N×Mサイズの配列として表現された迷路があります.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
迷路では、1は移動可能なセル、0は移動不可能なセルを表します.これらの迷路が与えられた場合、(1,1)から(N,M)の位置に移動する際に通過しなければならない最小セル数を求めるプログラムを作成します.1つのセルから別のセルに移動する場合は、隣接するセルにのみ移動できます.
上記の例では、(N,M)の位置に移動するには15格子を通過しなければならない.数欄には、開始位置と到達位置も含まれます.
入力
第1行は2つの整数N,M(2≦N,M≦100)を与える.次のN行には迷路としてM個の整数がある.各数を入力として加算します.
しゅつりょく
出力は最初の行の最小セル数を通過する必要があります.常に到着位置まで移動できる場合のみ、入力として使用されます.
に答える
答えは正しいと思いますが、なぜか分かりませんが、もう一度読んでみると、入力時にスペースがないことに気づきました.トマト問題と似ていて、ちょっと違うbfs問題です.
リファレンス
https://wiselog.tistory.com/163
https://www.acmicpc.net/problem/2178
質問する
N×Mサイズの配列として表現された迷路があります.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
迷路では、1は移動可能なセル、0は移動不可能なセルを表します.これらの迷路が与えられた場合、(1,1)から(N,M)の位置に移動する際に通過しなければならない最小セル数を求めるプログラムを作成します.1つのセルから別のセルに移動する場合は、隣接するセルにのみ移動できます.
上記の例では、(N,M)の位置に移動するには15格子を通過しなければならない.数欄には、開始位置と到達位置も含まれます.
入力
第1行は2つの整数N,M(2≦N,M≦100)を与える.次のN行には迷路としてM個の整数がある.各数を入力として加算します.
しゅつりょく
出力は最初の行の最小セル数を通過する必要があります.常に到着位置まで移動できる場合のみ、入力として使用されます.
に答える
import java.util.*;
import java.io.*;
class miro {
int x;
int y;
miro(int x, int y) {
this.x = x;
this.y = y;
}
}
public class boj_2178 {
static int M;
static int N;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int[][] board;
static boolean[][] visit;
static Queue<miro> que;
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 int[N][M];
visit = new boolean[N][M];
que = new LinkedList<>();
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = s.charAt(j) - '0';
}
}
que.add(new miro(0, 0));
visit[0][0] = true;
BFS();
System.out.println(board[N-1][M-1]);
}
public static void BFS() {
while (!que.isEmpty()) {
miro t = que.remove();
int x = t.x;
int y = t.y;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (!visit[nx][ny] && board[nx][ny] == 1) {
que.add(new miro(nx, ny));
visit[nx][ny] = true;
board[nx][ny] = board[x][y] + 1;
}
}
}
}
}
}
説明:答えは正しいと思いますが、なぜか分かりませんが、もう一度読んでみると、入力時にスペースがないことに気づきました.トマト問題と似ていて、ちょっと違うbfs問題です.
リファレンス
https://wiselog.tistory.com/163
Reference
この問題について([BOJ-JAVA]白俊2178迷宮を探る), 我々は、より多くの情報をここで見つけました https://velog.io/@booorim98/BOJ-2178テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol