반응형
[광고 누르면 오늘의 행운 상승!!]
1. 참고사항
- 신호체계(몇초마다 달라지는 장애물)문제
- 자신의 cnt값 (이동한 거리) % 3 == 2 일때만 지나가게 한다. (소용돌이가 잠잠해지는 시간)
- 소용돌이가 돌고있으면 제자리에 add한다.
2. 구현
- 4방향으로 bfs를 뻗어나간다.
- 소용돌이가 있다면 자신의 cnt값 (이동한 거리) % 3 == 2 일때만 지나간다.
- 소용돌이가 돌고있다면 제자리에 q.add를 한다(기다린다)
- 목적지에 도달하면 종료
package Study9;
import java.io.*;
import java.util.*;
public class 수영대회결승전 {
static class Player{
int row, col, cnt;
public Player(int row, int col, int cnt) {
this.row = row;
this.col = col;
this.cnt = cnt;
}
}
public static int[] dx = {-1,0,1,0};
public static int[] dy = {0,1,0,-1};
static int[][] map;
static boolean[][] visit;
static int N,ans;
static int SROW, SCOL, FROW, FCOL;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("test.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int tc = 1; tc <= T; tc++) {
ans = 0;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visit = new boolean[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
SROW = Integer.parseInt(st.nextToken());
SCOL = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
FROW = Integer.parseInt(st.nextToken());
FCOL = Integer.parseInt(st.nextToken());
if(SROW == FROW && SCOL == FCOL) {
System.out.println("#" + tc + " " + 0);
continue;
}
System.out.println("#" + tc + " " + (bfs() ? ans : -1));
}
}
private static boolean bfs() {
Queue<Player> q = new LinkedList<>();
q.add(new Player(SROW, SCOL,0));
visit[SROW][SCOL] = true;
while(!q.isEmpty()) {
Player player = q.poll();
for (int i = 0; i < 4; i++) {
int nx = player.row + dx[i];
int ny = player.col + dy[i];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if(nx == FROW && ny == FCOL) {
ans = player.cnt+1;
return true;
}
if(map[nx][ny] == 1 || visit[nx][ny]) continue;
if(map[nx][ny] == 2) {
if(player.cnt%3 == 2) {
visit[nx][ny] = true;
q.add(new Player(nx,ny,player.cnt+1));
}else {
visit[player.row][player.col] = true;
q.add(new Player(player.row,player.col,player.cnt+1));
}
}else {
visit[nx][ny] = true;
q.add(new Player(nx,ny,player.cnt+1));
}
}
}
return false;
}
}
반응형
'2. 알고리즘사이트 > 2. Swea' 카테고리의 다른 글
혁진이의 프로그램 검증 [SWEA 1824][BFS][Queue][시뮬레이션] (0) | 2020.06.05 |
---|---|
준환이의 양팔저울 [SWEA 3234][JAVA][DFS]D4] (0) | 2020.05.24 |
견우와 직녀 [SWEA 4727][JAVA][D4][BFS] (0) | 2020.05.20 |
이상한 피라미드 탐험 [SWEA 4112][JAVA][D5][BFS][List] (0) | 2020.05.04 |
정식이의 은행업무 [SWEA 4366][JAVA][D4][String] (0) | 2020.05.01 |