# USACO 2017 January Contest, Gold Problem 3. Cow Navigation

USACO2017-JAN-G3

import java.io.*;
import java.util.*;
public class cownav {
static int[] dx = new int[]{-1,0,1,0};
static int[] dy = new int[]{0,1,0,-1};
static int n;
static char[][] grid;
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("cownav.out")));
grid = new char[n][];
for(int i = 0; i < n; i++) {
}
int[][][][][][] dp = new int[n][n][4][n][n][4];
dp[n-1][0][0][n-1][0][1] = 1;
q.add(new State(n-1, 0, 0, n-1, 0, 1));
while(!q.isEmpty()) {
State curr = q.removeFirst();
if(curr.ax == 0 && curr.bx == 0 && curr.ay == n-1 && curr.by == n-1) {
break;
}
for(State next: curr.genTransitions()) {
}
}
}
pw.close();
}
static class State {
int bx, by, bd;
public State(int ax, int ay, int ad, int bx, int by, int bd) {
this.ax = ax;
this.ay = ay;
this.bx = bx;
this.by = by;
this.bd = bd;
}
public State[] genTransitions() {
return new State[]{
turnLeft(),
turnRight(),
};
}
private State turnLeft() {
return new State(ax, ay, (ad+3)%4, bx, by, (bd+3)%4);
}
private State turnRight() {
return new State(ax, ay, (ad+1)%4, bx, by, (bd+1)%4);
}
int nax = ax;
int nay = ay;
if(nax != 0 || nay != n-1) {
if(nax + dx[ad] >= 0 && nax + dx[ad] < n) {
}
if(nay + dy[ad] >= 0 && nay + dy[ad] < n) {
}
if(grid[nax][nay] == 'H') {
nax = ax;
nay = ay;
}
}
int nbx = bx;
int nby = by;
if(nbx != 0 || nby != n-1) {
if(nbx + dx[bd] >= 0 && nbx + dx[bd] < n) {
nbx += dx[bd];
}
if(nby + dy[bd] >= 0 && nby + dy[bd] < n) {
nby += dy[bd];
}
if(grid[nbx][nby] == 'H') {
nbx = bx;
nby = by;
}
}
return new State(nax, nay, ad, nbx, nby, bd);
}
}
}