문제
https://www.acmicpc.net/problem/3055
3055호: 탈출
어둠의 마왕 이민혁은 마침내 마법의 보주를 손에 넣었고, 그 힘을 시험하기 위해 인근 거인의 숲을 범람시키려 한다. 이 숲에는 고슴도치가 산다. 고슴도치는 내 꺼야
www.acmicpc.net
설명
고슴도치는 매분 4개의 인접한 공간 중 하나로 이동할 수 있습니다.
물도 1분마다 빈 사각형으로 확장되며, 물 사각형에 인접한 빈 사각형은 물로 채워집니다.
고슴도치는 물로 채워진 공간으로 들어갈 수 없고 물은 비버의 굴로 들어갈 수 없습니다. 아무도 돌을 통과할 수 없습니다.
빈 사각형, 채워진 영역, 바위, 비버 굴 및 고슴도치의 위치를 저장하십시오. 지도()()생성 및 저장
고슴도치는 비버 굴로 간다 최대한 빨리 이동할 각 위치에 해당하는 시간을 저장 dp()()~할 것 같다
고슴도치는 다음에 물로 채워질 공간으로 이동할 수 없습니다.
위의 표현이 가장 주요 포인트그것이 의미하는 바입니다.
즉, 고슴도치가 1초가 지나도 움직이지 못하는 곳 물이 가득한 곳 + 물이 상하좌우 있는 곳 + 돌 오전.
이런 이유로 먼저 물이 이동할 영역을 결정합니다.하다 고슴도치가 나중에 이동할 영역 결정해야한다.
편리한 좌표 저장을 위해 가리키다 수업물과 고슴도치 좌표 입력 대기줄생성
생성된 대기열의 첫 번째 물의 좌표줄을 서다 마지막에게 고슴도치의 좌표세트 FSO계속하다
static class Point {
int x;
int y;
char type;
public Point(int x, int y, char type) {
this.x = x;
this.y = y;
this.type = type;
}
}
static Queue<Point> queue;Point start = null; // 시작점
for (int r = 0; r < R; r++) {
String line = br.readLine();
for (int c = 0; c < C; c++) {
map(r)(c) = line.charAt(c);
if (map(r)(c) == '*') {
// 물의 좌표를 큐에 넣는다
queue.add(new Point(r, c, '*'));
}
else if (map(r)(c) == 'S') {
start = new Point(r, c, 'S');
}
}
}
// 마지막에 고슴도치의 좌표를 큐에 넣는다
queue.add(start);
bfs();좌표는 위, 아래, 왼쪽 및 오른쪽으로 이동합니다.~을 위한 MX, 나의~할 것 같다
다른 방법이 있습니까?의 유무를 판단하기 위해 답을 찾았다~할 것 같다
대기열에서 하나를 가져옵니다. 물수업 고슴도치갈 수 있는 좌표를 결정 대기열에 넣다
물 -> 고슴도치가 있던 곳은 비어있다
고슴도치 -> 아직 가보지 못한 텅 빈 곳, 비버 동굴
위 과정을 반복하면,고슴도치가 비버 굴에 도착하면 dp()() 좌표 값출구하다.
모든 과정이 끝났다 대기열이 비어있을 때 고슴도치가 비버 동굴에 도달하지 않으면, “선인장”출구
static final int() MX = { -1, 1, 0, 0};
static final int() MY = { 0, 0, -1, 1};
static void bfs() {
boolean foundAnswer = false;
while (!queue.isEmpty()) {
// 1. 큐에서 꺼내옴
Point p = queue.poll();
// 2. 목적지인가? (고슴도치가 D에 도착)
if (p.type == 'D') {
System.out.println(dp(p.x)(p.y));
foundAnswer = true;
break;
}
// 3. 연결된 곳을 순회 (상하좌우로 이동)
for (int i = 0; i < 4; i++) {
int tx = p.x + MX(i);
int ty = p.y + MY(i);
// 4. 갈 수 있는가? (공통 -> 맵 벗어나지 않고)
if (0 <= tx && tx < R && 0 <= ty && ty < C) {
if (p.type == '.' || p.type == 'S') {
// 4. 갈 수 있는가? (고슴도치 -> '.', 'D')
if ((map(tx)(ty) == '.' || map(tx)(ty) == 'D') && dp(tx)(ty) == 0) {
// 5. 체크인 (고슴도치 -> dp)
dp(tx)(ty) = dp(p.x)(p.y) + 1;
// 6. 큐에 넣음
queue.add(new Point(tx, ty, map(tx)(ty)));
}
}
else if (p.type == '*') {
// 4. 갈 수 있는가? (물 -> '.', 'S')
if (map(tx)(ty) == '.' || map(tx)(ty) == 'S') {
// 5. 체크인 (물 -> map)
map(tx)(ty) = '*';
// 6. 큐에 넣음
queue.add(new Point(tx, ty, '*'));
}
}
}
}
}
// 더 이상 갈 수 있는 길이 없으면
if (!foundAnswer)
System.out.println("KAKTUS");
}
전체 코드
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final int() MX = { -1, 1, 0, 0};
static final int() MY = { 0, 0, -1, 1};
static int R, C;
static char()() map;
static int()() dp;
static Queue<Point> queue;
static class Point {
int x;
int y;
char type;
public Point(int x, int y, char type) {
this.x = x;
this.y = y;
this.type = type;
}
}
static void bfs() {
boolean foundAnswer = false;
while (!queue.isEmpty()) {
// 1. 큐에서 꺼내옴
Point p = queue.poll();
// 2. 목적지인가? (고슴도치가 D에 도착)
if (p.type == 'D') {
System.out.println(dp(p.x)(p.y));
foundAnswer = true;
break;
}
// 3. 연결된 곳을 순회 (상하좌우로 이동)
for (int i = 0; i < 4; i++) {
int tx = p.x + MX(i);
int ty = p.y + MY(i);
// 4. 갈 수 있는가? (공통 -> 맵 벗어나지 않고)
if (0 <= tx && tx < R && 0 <= ty && ty < C) {
if (p.type == '.' || p.type == 'S') {
// 4. 갈 수 있는가? (고슴도치 -> '.', 'D')
if ((map(tx)(ty) == '.' || map(tx)(ty) == 'D') && dp(tx)(ty) == 0) {
// 5. 체크인 (고슴도치 -> dp)
dp(tx)(ty) = dp(p.x)(p.y) + 1;
// 6. 큐에 넣음
queue.add(new Point(tx, ty, map(tx)(ty)));
}
}
else if (p.type == '*') {
// 4. 갈 수 있는가? (물 -> '.', 'S')
if (map(tx)(ty) == '.' || map(tx)(ty) == 'S') {
// 5. 체크인 (물 -> map)
map(tx)(ty) = '*';
// 6. 큐에 넣음
queue.add(new Point(tx, ty, '*'));
}
}
}
}
}
// 더 이상 갈 수 있는 길이 없으면
if (!foundAnswer)
System.out.println("KAKTUS");
}
public static void main(String() args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char(R)(C);
dp = new int(R)(C);
queue = new LinkedList<>();
Point start = null; // 시작점
for (int r = 0; r < R; r++) {
String line = br.readLine();
for (int c = 0; c < C; c++) {
map(r)(c) = line.charAt(c);
if (map(r)(c) == '*') {
queue.add(new Point(r, c, '*'));
}
else if (map(r)(c) == 'S') {
start = new Point(r, c, 'S');
}
}
}
queue.add(start);
bfs();
}
}