Created
October 16, 2013 22:52
-
-
Save jimmitt/7016380 to your computer and use it in GitHub Desktop.
Erratic Ants problem from ACM competition qualification
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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