다오의 데이트


백준 [18188] 다오의 데이트

문제보기
Alt text

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int H, W, N;
	static char[][] map;
	static char[][] command;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		map = new char[H][W];
		int[] dao = new int[2];

		for (int i = 0; i < H; i++) {
			String str = br.readLine();
			for (int j = 0; j < W; j++) {
				map[i][j] = str.charAt(j);
				if (map[i][j] == 'D') {
					dao[0] = i;
					dao[1] = j;
				}
			}
		}

		N = Integer.parseInt(br.readLine());
		command = new char[N][2];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String one = st.nextToken();
			String two = st.nextToken();
			command[i][0] = one.charAt(0);
			command[i][1] = two.charAt(0);
		}

		goDate(0, dao[0], dao[1], new ArrayList<>());
		System.out.println("NO");
	}

	public static void goDate(int com, int r, int c, List<Character> load) {
		for (int i = com; i < N; i++) {
			boolean flag = false;
			for (int j = 0; j < 2; j++) {
				int dir = dirChk(command[i][j]);
				int x = r + dx[dir];
				int y = c + dy[dir];

				if (isRange(x, y) && map[x][y] != '@') {
					load.add(command[i][j]);
					flag = true;
					if (map[x][y] == 'Z') {
						System.out.println("YES");
						for (int k = 0; k < load.size(); k++) {
							System.out.print(load.get(k));
						}
						System.exit(0);
					} else {
						goDate(i + 1, x, y, load);
						load.remove(load.size() - 1);
						flag = false;
					}
				}
			}
			if(!flag)
				return;
		}
	}

	public static int dirChk(char dir) {
		int result = -1;
		if (dir == 'W') {
			result = 0;
		} else if (dir == 'A') {
			result = 2;
		} else if (dir == 'S') {
			result = 1;
		} else if (dir == 'D') {
			result = 3;
		}
		return result;
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < H && y < W;

	}
}