http://acm.pku.edu.cn/JudgeOnline/problem?id=1024

Код:
import java.util.*;
public class Main {
    static final int[] dis = { 0, 1, 0, -1 };
    static final int[] djs = { 1, 0, -1, 0 };
    static final int INF = Integer.MAX_VALUE / 4;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int casenum = sc.nextInt();
        for(int caseiter=0;caseiter<casenum;caseiter++){
            int w = sc.nextInt();
            int h = sc.nextInt();
            char[][] board = new char[2*h+1][2*w+1];
            Arrays.fill(board[0], '#');
            for(int i=1;i<=2*h-1;i++){
                board[i][0] = '#';
                for(int j=1;j<=2*w-1;j++) board[i][j] = ' ';
                board[i][2*w] = '#';
            }
            Arrays.fill(board[2*h], '#');
            for(int i=0;i<=2*h;i+=2){
                for(int j=0;j<=2*w;j+=2){
                    board[i][j] = '#';
                }
            }
            char[] path = sc.next().toCharArray();
            int m = sc.nextInt();
            int[] wx1s = new int[m];
            int[] wy1s = new int[m];
            int[] wx2s = new int[m];
            int[] wy2s = new int[m];
            for(int k=0;k<m;k++){
                wx1s[k] = sc.nextInt();
                wy1s[k] = sc.nextInt();
                wx2s[k] = sc.nextInt();
                wy2s[k] = sc.nextInt();
                int j1 = 2*wx1s[k] + 1;
                int i1 = 2*h - 1 - 2*wy1s[k];
                int j2 = 2*wx2s[k] + 1;
                int i2 = 2*h - 1 - 2*wy2s[k];
                board[(i1+i2)/2][(j1+j2)/2] = '#';
            }
            // check if the path intersects walls
            boolean[][] used = new boolean[2*h+1][2*w+1];
            int nowi = 2*h - 1, nowj = 1;
            used[nowi][nowj] = true;
            boolean valid = true;
            for(int k=0;k<path.length;k++){
                int nexti = nowi, nextj = nowj;
                switch(path[k]){
                case 'U':
                    nexti -= 2; break;
                case 'R':
                    nextj += 2; break;
                case 'D':
                    nexti += 2; break;
                case 'L':
                    nextj -= 2; break;
                default:
                    throw new RuntimeException();
                }
                if(board[(nowi+nexti)/2][(nowj+nextj)/2]=='#'){
                    valid = false;
                    break;
                }
                nowi = nexti;
                nowj = nextj;
                used[nowi][nowj] = true;
            }
            if(!valid){
                System.out.println("INCORRECT");
                continue;
            }
            int goalx = nowj / 2;
            int goaly = (2*h-nowi-1) / 2;
            // check if the path is shortest
            int pathlen = path.length * 2;
            int[][] fromstart = new int[2*h+1][2*w+1];
            int[][] fromgoal = new int[2*h+1][2*w+1];
            calcDist(board, w, h, 0, 0, fromstart);
            calcDist(board, w, h, goalx, goaly, fromgoal);
            if(fromgoal[2*h-1][1]<pathlen){
                System.out.println("INCORRECT");
                continue;
            }
            // check if the shortest path is unique
            for(int i=1;i<=2*h-1;i+=2){
                for(int j=1;j<=2*w-1;j+=2){
                    if(!used[i][j]&&fromstart[i][j]+fromgoal[i][j]==pathlen){
                        valid = false;
                        break;
                    }
                }
            }
            if(!valid){
                System.out.println("INCORRECT");
                continue;
            }
            // check if walls are necessary
            for(int k=0;k<m;k++){
                int j1 = 2*wx1s[k] + 1;
                int i1 = 2*h - 1 - 2*wy1s[k];
                int j2 = 2*wx2s[k] + 1;
                int i2 = 2*h - 1 - 2*wy2s[k];
                if( fromstart[i1][j1]+fromgoal[i2][j2]>pathlen &&
                    fromstart[i2][j2]+fromgoal[i1][j1]>pathlen){
                    valid = false;
                    break;
                }
            }
            if(valid) System.out.println("CORRECT");
            else System.out.println("INCORRECT");
        }
    }
    static void printBoard(char[][] board){
        for (char[] line : board)
            System.out.println(line);
    }
    static void calcDist(char[][] board, int w, int h, int fromx, int fromy,
            int[][] dist){
        int fromi = 2 * h - 1 - 2 * fromy;
        int fromj = 2 * fromx + 1;
        for (int i = 0; i <= 2 * h; i++)
            Arrays.fill(dist[i], INF);
        Queue<State> q = new LinkedList<State>();
        State from = new State(fromi, fromj, 0);
        q.offer(from);
        dist[from.i][from.j] = from.d;
        while (!q.isEmpty()) {
            State s = q.poll();
            for (int dir = 0; dir < 4; dir++) {
                int ni = s.i + dis[dir];
                int nj = s.j + djs[dir];
                int nd = s.d + 1;
                if (board[ni][nj] == ' ' && dist[ni][nj] == INF) {
                    q.offer(new State(ni, nj, nd));
                    dist[ni][nj] = nd;
                }
            }
        }
    }
}
class State {
    int i, j, d;
    State(int i, int j, int d){
        this.i = i;
        this.j = j;
        this.d = d;
    }
}