Skip to content

Instantly share code, notes, and snippets.

@jimmitt
Created October 16, 2013 22:52
Show Gist options
  • Save jimmitt/7016380 to your computer and use it in GitHub Desktop.
Save jimmitt/7016380 to your computer and use it in GitHub Desktop.
Erratic Ants problem from ACM competition qualification
// Created by James Trimble (On Twitter @jamestrimble)
// Original problem can be found here, https://icpc-qual-13.contest.scrool.se/problems/erraticants
public class erraticants {
public static Room[][] map;
public static void main(String[] args) {
int problem = 2;
String path;
switch (problem) {
case 0:
path = "SEEENWSS";
break;
case 1:
path = "SEN";
break;
default:
path = "SENW";
break;
}
System.out.println("Solution = "+solveants(path));
}
public static Integer solveants(String path) {
map = new Room[path.length()][path.length()];
for (int i = 0; i < path.length(); i++) {
for (int j = 0; j < path.length(); j++) {
map[i][j] = new Room();
}
}
int x = 0, y = 0;
map[x][y].setValue(999);
for (int i = 0; i < path.length(); i++) {
String direction = path.substring(i,i+1);
if (direction.equals("N")) {
map[x][y].setWall(Room.North, 0);
map[x][y-1].setWall(Room.South, 0);
y = Math.max(y-1,0);
}
else if (direction.equals("S")) {
map[x][y].setWall(Room.South, 0);
map[x][y+1].setWall(Room.North, 0);
y = Math.min(y+1,path.length()-1);
}
else if (direction.equals("E")) {
map[x][y].setWall(Room.East, 0);
map[x+1][y].setWall(Room.West, 0);
x = Math.min(x+1,path.length()-1);
}
else if (direction.equals("W")) {
map[x][y].setWall(Room.West, 0);
map[x-1][y].setWall(Room.East, 0);
x = Math.max(x-1,0);
}
map[x][y].setValue(999);
}
int destX = x, destY = y;
update(destX, destY, -1);
return map[0][0].getValue();
}
public static void update(int x, int y, int value) {
if (x < 0 || y < 0 || x >= map[0].length || y >= map[0].length || map[x][y].getValue() <= value) { return; }
map[x][y].setValue(value+1);
if (map[x][y].northClear()) { update(x,y-1,map[x][y].getValue()); }
if (map[x][y].southClear()) { update(x,y+1,map[x][y].getValue()); }
if (map[x][y].eastClear()) { update(x+1,y,map[x][y].getValue()); }
if (map[x][y].westClear()) { update(x-1,y,map[x][y].getValue()); }
}
}
class Room {
public final static Integer North = 0, South = 1, East = 2, West = 3;
Integer walls[] = {1,1,1,1}; // North, South, East, West; All walls blocked by default
Integer value = 0;
boolean northClear() { return !walls[0].equals(1); }
boolean southClear() { return !walls[1].equals(1); }
boolean eastClear() { return !walls[2].equals(1); }
boolean westClear() { return !walls[3].equals(1); }
void setWall(Integer wall, Integer value) { walls[wall] = value; }
Integer getWall(Integer wall) { return walls[wall]; }
void setValue(Integer value) { this.value = value; }
Integer getValue() { return this.value; }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment