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;
}
}