https://www.acmicpc.net/problem/13787
13787번: Infinity Maze
For each dataset, output in a line the final row, column and direction of the robot, separated by a single space. The direction should be one of the following: “N” (north), “E” (east), “S” (south) and “W” (west). No extra spaces or characte
www.acmicpc.net
미로가 주어졌을때 로봇의 최종 위치와 방향을 찾는 문제다.
로봇은 앞으로만 가며 앞이 벽이나 미로의 경계일때만 90도 방향 시계방향으로 회전한다.
DFS을 이용해서 풀어야하지만 이동횟수 L이 10^18까지 이므로 memoization 기법을 활용한다.
사이클을 찾기 위해 DFS로 한칸씩 이동하면서 그 칸에 최초로 도달한 이동횟수를 DP 배열에 기록한다.
(단 같은 칸이더라도 이동방향도 영향을 미치므로 dp배열에 방향까지 추가해준다. 크기 4* 100 *100)
그리고 최초로 DP 배열의 값이 -1이 아닌 값을 최초로 발견한 것은 사이클의 시작점이다. 그 지점에서 DFS를 멈추면 사이클의 주기를 구할 수 있다.)
이제 사이클의 시작지점과 주기를 찾았으므로 사이클 내에서 L일때의 위치와 방향을 구할수 있다.
(단 최종위치가 주기의 끝일 경우 예외사항이 있다. 이 예외사항만 처리해주면 끝)
3 3 16
E..
.*.
...
Answer : 1 1 N
Wrong : 1 1 E
package 백준;
import java.util.*;
import java.io.*;
public class InfinityMaze {
static class MyScanner{
BufferedReader bf;
StringTokenizer st;
MyScanner(){
bf = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
if(st==null||!st.hasMoreTokens()) {
try {
st = new StringTokenizer(bf.readLine());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
static class Point
{
int x;
int y;
int dir;
public Point(int x, int y,int dir) {
super();
this.x = x;
this.y = y;
this.dir = dir;
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + ", dir=" + dir + "]";
}
}
static long dp[][][];
static char map[][];
static int N,M;
static long L;
static int dx[] = {-1,0,1,0};
static int dy[] = {0,1,0,-1};
public static void main(String[] args) {
MyScanner sc = new MyScanner();
while(true) {
N = sc.nextInt();
M = sc.nextInt();
L = sc.nextLong();
if(N==0&&M==0&&L==0) break;
Point start = new Point(0,0,0);
map = new char[N][M];
dp = new long[4][N][M];
T = 0;
for(int i =0 ;i <4;i++) {
for(int j =0 ;j <N;j++)
Arrays.fill(dp[i][j], -1);
}
for(int i =0 ;i <N;i++) {
map[i] = sc.next().toCharArray();
for(int j =0 ;j<M;j++) {
if(map[i][j]=='E'||map[i][j]=='S'||map[i][j]=='N'||map[i][j]=='W') {
start.x = i;
start.y = j;
start.dir = toDir(map[i][j]);
}
}
}
dfs(start.x,start.y,start.dir,0);
if(T==0) { //사이클이 없는 경우
System.out.printf("%d %d %c\n",sx+1,sy+1,toChar(sd));
}
else {
int x = sx;
int y = sy;
int d = sd;
if((L-dp[sd][sx][sy])%T==0) { //사이클의 시작점인 경우
for(long i = 0; i < T;i++) {
int nx = x+dx[d];
int ny = y+dy[d];
int nd = d;
if(nx>=N||nx<0||ny<0||ny>=M||map[nx][ny]=='#') {
d = (nd+1)%4;
i--;
}else {
x = nx;
y = ny;
d = nd;
}
}
System.out.printf("%d %d %c\n",x+1,y+1,toChar(d));
continue;
}
for(long i =0 ;i <(L-dp[sd][sx][sy])%T;i++) { //사이클의 중간에서 끝난 경우
int nx = x+dx[d];
int ny = y+dy[d];
int nd = d;
if(nx>=N||nx<0||ny<0||ny>=M||map[nx][ny]=='#') {
d = (nd+1)%4;
i--;
}else {
x = nx;
y = ny;
d = nd;
}
}
System.out.printf("%d %d %c\n",x+1,y+1,toChar(d));
}
}
}
static long T;
static int sx,sy,sd;
private static void dfs(int x, int y, int dir, long t) {
if(dp[dir][x][y]!=-1) { //사이클 발견 시작지점 과 주기 저장
sx = x;
sy = y;
sd = dir;
T = t - dp[dir][x][y];
return;
}
dp[dir][x][y] = t;
if(t==L) { //사이클을 만나기전에 끝나는 경우
sx= x;
sy =y;
sd = dir;
return;
}
int nx = x+ dx[dir];
int ny = y+ dy[dir];
if(nx>=N||nx<0||ny<0||ny>=M||map[nx][ny]=='#') { //벽 만나서 회전
dir = (dir+1)%4;
dfs(x,y,dir,t);
}
else dfs(nx,ny,dir,t+1);
}
private static int toDir(char c) {
if(c=='N') return 0;
if(c=='E') return 1;
if(c=='S') return 2;
if(c=='W') return 3;
return 0;
}
private static char toChar(int d) {
if(d==0) return 'N';
if(d==1) return 'E';
if(d==2) return 'S';
if(d==3) return 'W';
return 'X';
}
}