Player.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


class Player {
    static class Pos {
        int x;
        int y;

        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Players {
        int x;
        int y;
        int remainIsWall;

        Players(int x, int y, int remainIsWall) {
            this.x = x;
            this.y = y;
            this.remainIsWall = remainIsWall;
        }
    }

    static class Wall {
        int x;
        int y;
        String v;

        Wall(int x, int y, String v) {
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }

    public static List<Pos> getGoals(int id) {
        List<Pos> goals = new ArrayList<>();
        if (id == 0) {
            for (int i = 0; i <= 8; i++) {
                goals.add(new Pos(8, i));
            }
        } else if (id == 1) {
            for (int i = 0; i <= 8; i++) {
                goals.add(new Pos(0, i));
            }
        }
        return goals;
    }

    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static String[] dirs = {"LEFT", "UP", "RIGHT", "DOWN"};


    public static int bfs(List<Wall> walls, int px, int py, List<Pos> goals) {
        int[][] fields = new int[9][9];
        for (int i = 0; i < fields.length; i++) {
            for (int j = 0; j < fields[i].length; j++) {
                fields[i][j] = 64;
            }
        }
        ArrayList<Pos> nextQueue = new ArrayList<>();

        for (Pos goal : goals) {
            fields[goal.y][goal.x] = 0;
            nextQueue.add(new Pos(goal.x, goal.y));
        }
        int l = 0;
        while (nextQueue.size() > 0) {
            ArrayList<Pos> queue = new ArrayList<>(nextQueue);

            nextQueue.clear();
            l += 1;

            while (queue.size() > 0) {

                final Pos pos = queue.get(0);
                queue.remove(0);
                for (int select = 0; select < 4; select++) {
                    int x = pos.x + dx[select];
                    int y = pos.y + dy[select];
                    if (!(0 <= x && x <= 8)) {
                        continue;
                    }
                    if (!(0 <= y && y <= 8)) {
                        continue;
                    }

                    if (fields[y][x] > l) {
                        if (checkWall(walls, pos.x, pos.y, dx[select], dy[select])) {
                            fields[y][x] = l;
                            if (x == px && y == py) {
                                return select;
                            }

                            nextQueue.add(new Pos(x, y));
                        }
                    }
                }

            }
        }
        return -1;
    }

    /**
     * 敵とあたっているかどうか判定する関数です
     *
     * @param walls カベのリスト
     * @param x     プレイヤーのx座標
     * @param y     プレイヤーのy座標
     * @param dx    次進むx方向の距離
     * @param dy    次進むy方向の距離
     * @return カベに当たらなければ true,当たるのならfalse
     */

    public static boolean checkWall(List<Wall> walls, int x, int y, int dx, int dy) {
        for (int i = 0; i < walls.size(); i++) {
            if (walls.get(i).v.equals("V") && dy == 0) {
                if (walls.get(i).x == x && dx == -1 ||
                        walls.get(i).x == x + 1 && dx == 1)
                    if (-1 <= walls.get(i).y - y && walls.get(i).y - y <= 0) {
                        return false;
                    }
            }
            if (walls.get(i).v.equals("H") && dx == 0) {
                if (walls.get(i).y == y && dy == -1 ||
                        walls.get(i).y == y + 1 && dy == 1)
                    if (-1 <= walls.get(i).x - x && walls.get(i).x - x <= 0) {
                        return false;
                    }
            }
        }
        return true;

    }

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int w = in.nextInt();
        int h = in.nextInt();
        int playerCount = in.nextInt();
        int myId = in.nextInt();

        while (true) {
            ArrayList<Players> players = new ArrayList<>();
            for (int i = 0; i < playerCount; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                int remain = in.nextInt();
                players.add(new Players(x, y, remain));
            }
            ArrayList<Wall> walls = new ArrayList<>();

            int wallCount = in.nextInt();
            for (int i = 0; i < wallCount; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                String v = in.next();
                walls.add(new Wall(x, y, v));
            }


            final int select = bfs(walls, players.get(myId).x, players.get(myId).y, getGoals(myId));
            System.out.println(dirs[select]);

        }

    }
}